#include #include #include #include #include #include using namespace std; /* Author: Paul Caron Date: November 2022 Special thanks to Prashanth Kumar for inspiring me to do this code. Quantum Class ============= Class of Quantum particle with the ability to have multi-state probabilities or a single collapsed state constructor =========== -Quantum() where nstates is the number of possible states. Upon contruction, the Quantum is in a multistate by default, "quantumized" methods ======= -Quantumize() -> void makes the particle into a multistate with equal probabilities for all states -Collapse() -> void makes the particle collapse into a single state -RemoveState(unsigned state) -> void forces the probability for that state to zero -SetState(unsigned state) -> void forces all probabilities to zero, except one state. consequently, the Quantum is collapsed after -GetEntropy() -> int return the number of states with non zero probabilities -GetState() -> int return the collapsed state if the particle has collapsed yet. else it returns -1. */ //let s solve this sudoku where cells with zeros are empty vector sudoku{ 3,0,4,2, 0,0,3,0, 0,0,1,0, 0,3,2,4, }; template class Quantum{ private: //random gen default_random_engine random_engine{}; function rand; //quantum object state bool collapsed {false}; vector states_probabilities{}; vector::size_type collapsed_state{}; //utility function void normalize_vector_sum_at_one(){ double sum = accumulate( states_probabilities.begin(), states_probabilities.end(), 0.0); for(auto & probability: states_probabilities) probability /= sum; } public: Quantum(){ //seeding the engine random_engine.seed( chrono::high_resolution_clock::now() .time_since_epoch().count() ); //more seeding into itself... for(int i=100;i--;) random_engine.seed(random_engine()); //uniform distribution uniform_real_distribution urd (0.0, 1.0); //random function that binds urd to random engine rand = bind(urd, random_engine); //allowing space for every possible state states_probabilities.resize(nstates); //init in quantum multistate Quantumize(); } void Quantumize(){ collapsed = false; for(auto & probability: states_probabilities){ probability = 1.0/nstates; } normalize_vector_sum_at_one(); } void RemoveState(vector::size_type state){ if(collapsed) return; states_probabilities.at(state) = 0.0; normalize_vector_sum_at_one(); } void SetState(vector::size_type state){ if(collapsed) return; fill(states_probabilities.begin(), states_probabilities.end(), 0.0); states_probabilities.at(state) = 1.0; collapsed = true; collapsed_state = state; } void Collapse(){ int state {0}; double sum_of_probabilities{0.0}; double r = rand(); for(const auto& probability: states_probabilities){ sum_of_probabilities += probability; if(r > sum_of_probabilities){ ++state; }else{ break; } } SetState(state); } [[gnu::pure]] int GetState() const{ if(collapsed) return collapsed_state; return -1; } [[gnu::pure]] int GetEntropy() const{ int entropy {0}; for(const auto & prob: states_probabilities){ entropy += (prob > 0.0); } return entropy; } [[gnu::pure]] bool IsCollapsed() const{ return collapsed; } }; void init_grid(vector>& quantum_grid){ quantum_grid.resize(sudoku.size()); size_t i{0}; for(auto & quantum_cell: quantum_grid){ const size_t state = sudoku.at(i); if(state){ //remove state from row const size_t start_of_row = i - (i%4); for(size_t j=0;j<4;++j){ quantum_grid.at(start_of_row + j).RemoveState(state - 1); } //remove state from column const size_t start_of_col = i%4; for(size_t j=0;j<4;++j){ quantum_grid.at(start_of_col + (j*4)).RemoveState(state - 1); } //remove state from 2x2 square const size_t greater_col = (i%4)/2; const size_t greater_row = (i/4)/2; for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ const size_t row = (greater_row*2) + j; const size_t col = (greater_col*2) + k; const size_t index = (row * 4) + col; quantum_grid.at(index).RemoveState(state - 1); } } //set cell quantum_cell.SetState(state-1); } i++; } } void print_grid(const vector>& quantum_grid){ int i=1; for(const auto & quantum_cell: quantum_grid){ cout << quantum_cell.GetState()+1 << (i++%4==0?"\n":" "); } cout << endl; } int collapse_lowest_entropy(vector>& quantum_grid){ int i=0; int j=0; int minimum=5; for(const auto & quantum_cell: quantum_grid){ if(!quantum_cell.IsCollapsed() && quantum_cell.GetEntropy() < minimum){ minimum = quantum_cell.GetEntropy(); i = j; } j++; } quantum_grid.at(i).Collapse(); unsigned state = quantum_grid.at(i).GetState(); //remove state from row const size_t start_of_row = i - (i%4); for(size_t j=0;j<4;++j){ quantum_grid.at(start_of_row + j) .RemoveState(state); } //remove state from column const size_t start_of_col = i%4; for(size_t j=0;j<4;++j){ quantum_grid.at(start_of_col + (j*4)) .RemoveState(state); } //remove state from 2x2 square const size_t greater_col = (i%4)/2; const size_t greater_row = (i/4)/2; for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ const size_t row = (greater_row*2) + j; const size_t col = (greater_col*2) + k; const size_t index = (row * 4) + col; quantum_grid.at(index).RemoveState(state); } } return i; } bool solved(const vector>& quantum_grid){ for(const auto& cell: quantum_grid){ if(!cell.IsCollapsed()) return false; } return true; } int main(){ //solving given sudoku above cout << "Solving this sudoku grid\n[\n" << endl; vector> quantum_grid; init_grid(quantum_grid); print_grid(quantum_grid); cout << "]\n" <> quantum_grid(16); while(!solved(quantum_grid)){ collapse_lowest_entropy(quantum_grid); } print_grid(quantum_grid); } return 0; }

Sudoku - Quantum Wave Function Collapse