Soloku Solver Program

Question

Function

solveSudoku is called from the main() function.

I wrote the following function for the sudoku function:

 #include <iostream> #include <vector> using namespace std; int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box for(int t = 0; t < 9; t++) { if(A[t][j] == k) //Checking jth column return 0; if(A[i][t] == k) //Checking ith row return 0; if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box return 0; } return 1; } bool sudoku(vector<vector<char> > &A, int i, int j) { if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true return true; if(A[i][j] == '.') { for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it A[i][j] = k; if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block return true; else A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position) } } } else { if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) return true; } return false;//This should trigger backtracking } void solveSudoku(vector<vector<char> > &A) { sudoku(A, 0, 0); } int main() { vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'}, {'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'}, {'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku solveSudoku(A); for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { cout<<A[i][j]<<" "; } cout<<"\n"; } return 0; } 

OUTPUT

 5 3 . . 7 . . . . 6 . . 1 9 5 . . . . 9 8 . . . . 6 . 8 . . . 6 . . . 3 4 . . 8 . 3 . . 1 7 . . . 2 . . . 6 . 6 . . . . 2 8 . . . . 4 1 9 . . 5 3 1 4 5 8 2 6 7 9 

Expected Result

 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 

The sudoku input is given as an argument when solveSudoku is called in the main() function. It consists of characters from 1 to 9 and . which represents an empty character. solveSudoku The task of the function is to correctly fill in all the elements in Sudoku (change the values ​​in A in place). But I get the wrong answer. Indicated that the introduced sudoku is solvable.

As Fezves said, I also think that the problem in my algorithm lies in this statement if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) . I think that after filling the cell with a valid character, this statement should check recursively if the block on the right, down and the diagonal are also filled or not. If so, then sudoku is decided, and he must return the truth, but if any of the three failures, he must retreat. But why is this not so?

Answer 1

Repeated answer : sudoku(A, i, j) has the side effect of writing data to A When you call if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) and you press the second sudoku(A, i, j+1) check sudoku(A, i, j+1) , this is not the same A , and you do not check what you think. I fixed this by changing the two lines where your if appears, and instead only one check is performed: sudoku(A, (i+1)%9, j+(i+1)/9)

---

Old answer : your code does not work because sudoku does not behave the way you thought. You must roll back with the search depth of the first search. But you do not do this: if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) is neither BFS nor DFS and this causes your algorithm to crash

Here is a slightly modified version where I replace the violating part of sudoku(A, (i+1)%9, j+(i+1)/9) , and it works.

Edit: if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) is a violator for the following reason:

• sudoku(A, i, j) true if the ANY rectangle from (i, j) to the lower right contains a valid fill. that is, you can enter numbers, and they do not violate sudoku rules. It is true that you want to compute sudoku(A,0,0)
• But I will give an example where it fails: suppose you calculate if(sudoku(A,1,0) && sudoku(A,0,1) && sudoku(A,1,1)) . You start with sudoku(A, 1, 0) and return true. Now you have the filling of almost all A (except the top row). You move on to sudoku(A,0,1) calculations, but if the almost complete filling that you did earlier is actually invalid (there is no way to fill the top line), your algorithm will work immediately.
• In other words, your code crashes because calling sudoku(A, i, j) has a side effect (writing data to A), and when you click the second third logical element in if , you are not dealing with the correct A

Here is the code updated in your example

 #include <iostream> #include <vector> using namespace std; int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box for(int t = 0; t < 9; t++) { if(A[t][j] == k) //Checking jth column return 0; if(A[i][t] == k) //Checking ith row return 0; if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box return 0; } return 1; } bool sudoku(vector<vector<char> > &A, int i, int j) { if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true return true; if(A[i][j] == '.') { for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it A[i][j] = k; if(sudoku(A, (i+1)%9, j+(i+1)/9))// CHANGE ONE return true; else A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position) } } } else { if(sudoku(A, (i+1)%9, j+(i+1)/9)) // CHANGE TWO return true; } return false;//This should trigger backtracking } void solveSudoku(vector<vector<char> > &A) { sudoku(A, 0, 0); } int main() { vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'}, {'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'}, {'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku solveSudoku(A); for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { cout<<A[i][j]<<" "; } cout<<"\n"; } return 0; } 

Exit

 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 

Answer 2

I rewrote your code and replaced some things to make it a little easier to debug. This does not look like a typical recursive function, because only one parameter is passed as a reference, but that is because it uses the stack for y, x, and k. (Adjusted)

This is a modified function:

 bool sudoku(vector<vector<char> > &A) { //Test full sudoku field to see if all fields can be filled with valid numbers: for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) { if (A[x][y] == '.') //Startpoint to find a valid replacement: { for (char k = '1'; k <= '9'; k++)//At least one character has to be possible { if (isvalid(k, A, x, y)) //If putting character `k` doesn't makes the sudoku invaild put it in: { A[x][y] = k; //Try solving sudoku with new value: if (sudoku(A)) return true; } } //Reset to unsolved: A[x][y] = '.'; return false; } } } //Reachable, if all fields are filled. [Corrected] //Assumption: Initialized with a valid field. //So a valid start field + valid adds ->always valid filled field //Otherwise you will have to test the complete field here. return true; } 

Output:

I am very sure that your problem is this code:

 if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block return true; 

If you look at your output and your desired result, you will see that the final line is completely filled. This is an indicator for a condition with broken feedback, but it is very difficult to debug. This is why I decided to rewrite a lot and delete unnecessary code.

Answer 3

You need a stack. Then you need to completely try 1-9 and relax if everyone is invalid. If all are invalid, you need to continue the previous level and relax again, if 1-9 are all unacceptable.

But this is a hopeless algorithm. Although it will ultimately work for easy sudoku, it just takes too much time to complete.