Sudoku Solver Program

Question

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?

Answer 1

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)
• But I am going to give an example where it fails : let's suppose that you are computing 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
• In other words, your code fails because calling 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 A

Here 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

Answer 2

I rewrote your code and replaced some stuff to make it a bit easier to debug. It doesn't look like a typcial recursiv function, because only one parameter is passed as reference, but it is, because it is using the stack for y,x and k. (corrected)

This is the changed 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;
}

The output is:

I'm very sure 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 output, you will see that the bottom line is the only completly filled. This is an indicator for a broken feedback condition, but very hard to debug. That's why i chose to rewrite a lot and remove unnecessary code.