Solving Soduku Using Backtracking

Written By: Byron Heads

- 17 Apr 2006 -

Description: We will use a simple backtracking algorithm to quickly solve a Soduku puzzle. This article will try to give a useful example in recursive programming and in backtracking algorithms in general.

  1. The Beginnings
  2. Building A Helper Function
  3. The Solver

The Solver

Now on to the brains of the operation. In order to solve our soduku puzzle we need to create a solver. For this problem it will simply be a recursive backtracking algorithm. The basic idea of backtracking to simply try each value until you get a solution. Backtrack does not find the best solution it just finds the first solution. Back tracking is often done thru recursion.

A more detailed explanation of backtracking can be found here
http://en.wikipedia.org/wiki/Backtrack
http://en.wikipedia.org/wiki/Recursion
First we create the basic shell of the solver

int* Solver(int board[81])
{
 
}

Our solver will pass us a pointer to a solved integer array, and requires that we pass it an array the needs to be solved.

First we declare the variables that will be used.

int i, j, k;
bool solved = true;
int* ans;

The first three variables are used for looping. The variable solved will be used in our test to see if the puzzle has been solved. The last viable is used for testing if that function call above us has solved the puzzle.

Now we must test if we have solved the puzzle. Basically this means that there are no more zeros in the array.

for(i = 0; i < 81; i++)
{
    if(board[i] == 0)
    {
        solved = false;
        break;
    }
}
if(solved)
    return board;

We loop thru all 81 elements in the array and check for zeros. If we have a zero we set our solved flag to false and break out of the loop. We then test the solved flag, and if we have a solved puzzle we return it to the function calls below us.

Now we enter the heart of the solver. Here we loop thru all elements of the puzzle until we find a zero. When we find a zero we enter a third loop in which we test every possible value that can go into the position. We test this with our helper function. If we have a valid number we add it to the grid and call the solver again. Now we test if we get a solved puzzle back if not we set our position back to zero and try the next valid number. We again recall the solver and tests if it found a solution. If we find a solution we simply return the value. If we don't find a solution and we test all possible values we return NULL to the call below us. This is how we will back track to previous tests.

for(i = 0; i < 9; i++)
{
    for(j = 0; j < 9; j++)
    {
        if(board[i*9+j] == 0)
        {
            for(k = 1; k<= 9; k++)
            {
                if(UseDigit(board,k,i,j))
                {
                    board[i*9+j] = k;
                    ans = Solver(board);
                    if (ans != NULL)
                        return ans;
                }
                board[i*9+j] = 0;
            }
            return NULL;
        }
    }
}
return NULL;

Putting it all Together

The last thing remaining is the write the main function. All we need to do is make a basic board, load the puzzle, solve it, and the display the solution.

int main()
{
    int* board = new int[81];
        
    LoadFile("soduku.txt",board);
    board = Solver(board);
    PrintBoard("output.txt", board);
        
    system("pause");   //omit if not using windows
    return 0;
}

<< Previous