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?

Configurationism

Please post a minimal reproducible example. – Storey

Please, can you tell me how your algorhtym should work in general, because all these variables i,j,d make me a bit crazy. – Pitchman

@Florianp.i. I have added some more comments in the code. i, j is the current coordinate of the sudoku in consideration and there is no variable d in my code. – Configurationism

fairly minimal and straightforward solver – Whitewash

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

Bisulcate

What I think this statement if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) should do is after filling a cell with a valid character it is checking 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. Can you explicitly tell the error in my algorithm here please? – Configurationism

I updated my answer with an edit that answers your question and the code now solves the example you gave in your OP – Bisulcate

Thanks a lot sir. – Configurationism

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.

Pitchman

Your program is well and good but you didn't answer my question. Still +1 for changing my code to provide correct program. – Configurationism

Thanks, the main question to me is how this right block, down block and bottom block checking should work out. Can you draw an info grafic or something like this? I can read the code but i don't get the idea behind. – Pitchman

Your 'not reachable' is reachable, it will be reached when sudoku is called with a fully filled grid. Also, there is no control path that returns true, without calling itself first. This implies that the only possible outputs are false and infinite recursion. – Whitewash

Oh yeah your right, thank you! I didn't thought of this possiblility. I will try to fix it. – Pitchman

Answer 3

You need a stack. Then you need to exhaustively try 1-9, and unwind if all are invalid. If all are invalid, you need to continue the previous level, and unwind again if 1-9 are all invalid.

But it's a hopeless algorithm. Whilst it will eventually work for an easy sudoku, it simply takes too long to execute.

Ondrej

Instead of stack I am putting values from 1 to 9 in ascending order checking one by one recursively. Is it wrong? – Configurationism

Yes, you need to have a position i, and fill all squares up to that position. If you can't fill a square, subtract one from i, fill it with the next valid position, and try again at i+1. But it's a hopeless algorithm. You need to idenitify squares with only 1 or 2 possibilities, and that's much more fiddly . – Ondrej