solveSudoku function is called from main() function.
I have written the following function for solving sudoku :
#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 Output
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
Input sudoku is given as argument when solveSudoku is called in the main() function. It consists of characters from 1 to 9 and . which represents empty character. solveSudoku function's job is to fill all the elements in sudoku correctly(change values in A in place). But I am getting wrong answer. It is given that the input sudoku given is solvable.
As told by Fezvez 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 a cell with a valid character this statement should check recursively if the block on the right, down and diagonal are also getting filled or not. If yes the sudoku is solved and it should return true but if any of the three fail it should backtrack. But why is it not doing so?
Re-done answer : sudoku(A, i, j) has the side effect of writing data in A.
When you call if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)), and you hit the second check sudoku(A, i, j+1), it is not the same A anymore and you are not testing what you thought. I fixed it by changing the two lines where your if appears and doing only one check instead : sudoku(A, (i+1)%9, j+(i+1)/9)
Old answer : Your code fails because sudoku doesn't behave like you thought. You are supposed to do backtracking with a depth first search exploration. But you are not doing that : if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) is neither a BFS nor a DFS and it makes your algorithm fail
Here is a slightly modified versionwhere I replace the offending part with 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 the offender for the following reason :
sudoku(A, i, j) is true if ANY rectangle from (i,j) to the bottom-right contains a valid filling. i.e you can input numbers and they don't violate sudoku rules. It is true that what you want to compute is sudoku(A,0,0)if(sudoku(A,1,0) && sudoku(A,0,1) && sudoku(A,1,1)). You start with sudoku(A, 1, 0) and returns true. You have now a filling of nearly all A (except the top row). You advance to computing sudoku(A,0,1) but if the nearly complete filling you made before is actually not valid (there is no way to fill the top row) your algorithm fails immediately sudoku(A, i, j) has a side effect (writing data in A) and when you hit the second of third boolean in your if you are not dealing with the correct AHere is the code updated with 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;
}
Output
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