// In this code we represent sudokus as a vector<vector<int> >, // where the value 0 means 'not yet known'. #include <vector> #include <iostream> #include <ostream> using namespace std; vector<int> check_sudoku_vector(vector<int> v); vector<vector<int> > check_sudoku(vector<vector<int> > sudoku); vector<vector<int> > read_sudoku(); void print_sudoku(vector<vector<int> > sudoku); void solve_sudoku(vector<vector<int> > sudoku); int main(void) { vector<vector<int> > v = read_sudoku(); solve_sudoku(v); } // Checks a vector does not contain any value twice // Attempts to fill in values where possible. // As a hack, we return the empty vector if there are // any repeated values. // This tries to fill in the blank value if it can. vector<int> check_sudoku_vector(vector<int> v) { // We need 10 because we want 1..9, and 0 for empty. vector<int> count(10); // Count up the occurrences of each value for(int i = 0; i < 9; ++i) count[v[i]]++; // Check if any value occurs twice for(int i = 1; i <= 9; ++i) { if(count[i] > 1) { // Some value occurs twice! vector<int> empty; return empty; } } if(count[0] == 1) { // There is exactly one value to fill in! int empty_place = -1; for(int i = 0; i < 9; ++i) { if(v[i] == 0) empty_place = i; } for(int i = 1; i <= 9; ++i) { if(count[i] == 0) { v[empty_place] = i; return v; } } } return v; } // Tries to fill in the sudoku. // returns the empty vector if a flaw is found. // Takes the return value of check_sudoku_vector and puts it back // in the sudoku. This might be a waste of time, or might fill in a value. // There are obviously other ways check_sudoku_vector could respond back, // this is just one example. vector<vector<int> > check_sudoku(vector<vector<int> > sudoku) { vector<vector<int> > empty_vector; // First check rows for(int i = 0; i < 9; ++i) { vector<int> v = check_sudoku_vector(sudoku[i]); if(v.empty()) { return empty_vector; } sudoku[i] = v; } // then columns for(int i = 0; i < 9; ++i) { vector<int> column; for(int j = 0; j < 9; ++j) column.push_back(sudoku[j][i]); vector<int> v = check_sudoku_vector(column); if(v.empty()) return empty_vector; for(int j = 0; j < 9; ++j) sudoku[j][i] = v[j]; } // then boxes. Notice we do some interesting // loop indexing! for(int i = 0; i < 9; i+=3) { for(int j = 0; j < 9; j+=3) { vector<int> box; for(int a = i; a < i + 3; ++a) for(int b = j; b < j + 3; ++b) box.push_back(sudoku[a][b]); vector<int> v = check_sudoku_vector(box); if(v.empty()) return empty_vector; // Put the values back in! int counter = 0; for(int a = i; a < i + 3; ++a) for(int b = j; b < j + 3; ++b) { sudoku[a][b] = v[counter]; counter++; } } } // The sudoku is fine! return sudoku; } vector<vector<int> > read_sudoku() { vector<vector<int> > v; for(int i = 0; i < 9; ++i) { vector<int> row; for(int j = 0; j < 9; ++j) { int val = 0; row.push_back(val); } v.push_back(row); } return v; } void print_sudoku(vector<vector<int> > sudoku) { for(int i = 0; i < 9; ++i) { for(int j = 0; j < 9; ++j) { cout << sudoku[i][j] << " "; } cout << endl; } cout << endl; exit(0); } int counter = 0; void solve_sudoku(vector<vector<int> > sudoku) { counter++; vector<vector<int> > sudoku_copy = check_sudoku(sudoku); // This means the sudoku is unsolvable if(sudoku_copy.empty()) return; // let's keep looping around until check_sudoku stops filling // in values! while(sudoku_copy != sudoku) { sudoku = sudoku_copy; sudoku_copy = check_sudoku(sudoku); if(sudoku_copy.empty()) return; } for(int i = 0; i < 9; ++i) { for(int j = 0; j < 9; ++j) { if(sudoku[i][j] == 0) { // We have found a value to branch on! for(int k = 1; k <= 9; ++k) { sudoku[i][j] = k; solve_sudoku(sudoku); } // No solution found here! return; } } } // if we get here, then the solution is complete! print_sudoku(sudoku); std::cout << "Search: " << counter << std::endl; }