Why doesn't my Sudoku program return an output?

Question

So I have tried to implement a Sudoku via backtracking algorithm. I don't see why my code is not giving an expected output.

What I did was, I created a loop in which it checks for an empty cell (represented with 0) in the sudoku. As it finds it, the co-ordinates for it are passed to a function called possibleEntriescheck(). This function writes into a globally declared array called possibleEntries[9], the digits which can be possibly filled into the cell of which the co-ordinates are passed initially.

I learnt this algorithm from these videos: https://www.youtube.com/watch?v=NuodN41aK3g https://www.youtube.com/watch?v=QI0diwmx3OY

The expected output is a solved Sudoku. It doesn't perform expectedly. Rather, it freezes. A little help would mean a lot. Thank you.

#include <stdio.h>
#include <stdlib.h>
int board[9][9] = {
                  {3, 0, 6, 5, 0, 8, 4, 0, 0},
                  {5, 2, 0, 0, 0, 0, 0, 0, 0},
                  {0, 8, 7, 0, 0, 0, 0, 3, 1},
                  {0, 0, 3, 0, 1, 0, 0, 8, 0},
                  {9, 0, 0, 8, 6, 3, 0, 0, 5},
                  {0, 5, 0, 0, 9, 0, 6, 0, 0},
                  {1, 3, 0, 0, 0, 0, 2, 5, 0},
                  {0, 0, 0, 0, 0, 0, 0, 7, 4},
                  {0, 0, 5, 2, 0, 6, 3, 0, 0},
                  };
int possibleEntries[9];
void possibleEntriescheck(int i, int j)
{
    int x,a=0,k,l,y;
    for(x=0;x<9;x++)
        possibleEntries[x]=0;
    for(x=0;x<9;x++)
    {
        if(board[i][x]!=0)
            possibleEntries[board[i][x]-1]=1;
    }

    for(x=0;x<9;x++)
    {
        if(board[x][j]!=0)
            possibleEntries[board[x][j]-1]=1;
    }

    if(i==0 || i==1 || i==2)
        k=0;
    else if(i==3 || i==4 || i==5)
        k=3;
    else
        k=6;

    if(j==0 || j==1 || j==2)
        l=0;
    else if(j==3 || j==4 || j==5)
        l=3;
    else
        l=6;

    for(x=k;x<k+3;x++)
    {
        for(y=l;y<l+3;y++)
            if(board[x][y]!=0)
                possibleEntries[board[x][y]-1]=1;
    }
    for(x=0;x<9;x++)
    {
        if(possibleEntries[x]==0)
            possibleEntries[x]=x+1;
        else
            possibleEntries[x]=0;
    }
}
int isFull()
{
    int i,j;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(board[i][j]==0)
                return 0;
        }
    }
    return 1;
}
void solveSudoku()
{
    int i,j,x,b=0,k;
    if(isFull())
    {
        printf("The sudoku board is:\n");
        for(i=0;i<9;i++)
        {   
            for(j=0;j<9;j++)
                printf("\t%d",board[i][j]);
            printf("\n");
        }
    }
    else
    {
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                if(board[i][j]==0)
                {
                    possibleEntriescheck(i,j);
                    for(x=0;x<9;x++)
                    {
                        if(possibleEntries[x]!=0)
                        {
                            board[i][j]=possibleEntries[x];
                            solveSudoku();
                            board[i][j]=0;
                        }
                    }   
                }
            }
        }
    }
    return;
}
int main()
{
    solveSudoku();
}

Answer 1

You implemented backtracking incorrectly. As also explained in the video, the actual algorithm should look like this:

solve():
    if the sudoku is solved
        print field
        terminate

    x,y = the next vacant field

    for each possible value in that field
        assign value to x,y
        call solve() recursively to try with the assigned value

    clear vacant field

Now what your code does is

solve():
    if the sudoku is solved
        print field
        return

    for each field in the sudoku
        if field is vacant
            for each possible value
                assign value
                solve recursively
                reset field to unassigned

Now this actually does solve the sudoku. But there are two problems with this approach:
A: It won't terminate once it's solved the sudoku. Actually this mistake was also in the code presented in the video. A simple return in a recursive call will terminate the method on the current call and continue with the recursion "one call above". So basically the algorithm solves the sudoku in every possible way (provided there are multiple, otherwise it simply tries any possible way of assigning the values).
B: This one's way more serious. Your algorithm doesn't only generate all possible solutions, but it also tries every order of assigning the values it can possibly find. The overhead is gigantic and the reason why your code simply doesn't terminate. Solving the sudoku once already takes quite some time, but your code does so a bazillion times.

If you solve these problems, your code should work find, provided the rest is implemented correctly. I'd also recommend optimizing both the search for vacant fields and the test whether the field is empty, as these can be done fairly simple and will provide some speedup. Generate a list of vacant fields in the beginning, iterate over it (one field for each recursion-level) and terminate once the entire list was processed. E.g.:

solve(vacant, count):
    if count == 0
        print the field
        terminate

    x, y = vacant[count]
    count++

    for each possible value assignable to the field
        assign value to x, y
        call solve(vacant, count) recursively

    clear field

Another problem you will encounter, which will get rather ugly to debug is thanks to this line:

int possibleEntries[9];

Global variables that are used and overwritten in a recursion are a bad idea to say the least. Imagine a possible run of the program like this (ident indicates recursion-level, where no ident means the action is global):

solve
 |
 ---> board empty? Nope
      x,y <- next vacant field
possible values <- possible values for x, y
      field[x, y] <- first value from possible values
      solve
       |
       ---> board empty? Nope
            x, y <- next vacant field
possible values <- possible values for x, y (overwrites global variable!!!)
           field[x, y] <- first value from possible values
           solve
            |
            ---> ...
       <--- return
       field[x, y] <- second value from possible values (WRONG!!!)
       ... 

The last assignment won't use the list of possible values generated for the field you're currently working on, but of another one that you visited somewhere in the recursion before returning back. You can solve this in two ways:

• Iterate from 1 to 9 and check for each number separately whether it can be assigned to the field
• Keeping a separate list for each level of recursion