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

Building A Helper Function

Next were going to write a helper function. The purpose of this function to test if we can place a number in a certain position by testing all the rules of the game. We'll create the function here.

bool UseDigit(int board[81], int digit, int i, int j)
{
 
}

Since this function is going to only be used in an if statement we'll simply return if it's legal to place a number at a specific location. board[81] is the current game board, digit is the number we want to place, i the y location, and j is the x location. Next we create some variables that will be used in this function.

int x, y;

These variables will be used for looping. Next we need to test for valid input

if(i < 0 || j < 0 || i > 8 || j > 8 || digit < 1 || digit > 9)
    return false;
if(board[i*9+j] != 0)
    return false;

First we need to test if i, and j are valid indexes, and the digit we want to use is valid as well. Next we test if the location we want to use is available. So we simply test is the value is zero. Next we test if our digit is already in our current row or column.

for(x = 0; x < 9; x++)
{
    if(board[x*9+j] == digit || board[i*9+x] == digit)
    return false;
}

In our test loop here we check to see if your digit is used already. The first part of the if checks all the row values in the current column and the second tests all the column values in the current row. If any matches occur we fail the test. The last check tests if the digit appears in its sub grid.

for(y = ((i / 3) * 3); y < ((i / 3) * 3) + 3; y++)
{
    for(x = ((j / 3) * 3); x < ((j / 3)) * 3 + 3; x++)
    {
        if(board[y*9+x] == digit)
            return false;
    }
}

First we need to determine what sub grid we are trying to insert in to. By dividing the column index by 3 we get which column sub set we are in. We multiply it by 3 to find the cells starting index. Adding 3 to this number will find the last index of the sub grid. We will do the same for the row index as well. Now we can sort thru each cell in the sub grid and test if we can place the digit here. The last thing we do is return true. We made it thru all of the tests. The functions complete code is as follows.

bool UseDigit(int board[81], int digit, int i, int j)
{
    int x, y;
 
    if(i < 0 || j < 0 || i > 8 || j > 8 || digit < 1 || digit > 9)
        return false;
    if(board[i*9+j] != 0)
        return false;
 
    for(x = 0; x < 9; x++)
    {
        if(board[x*9+j] == digit || board[i*9+x] == digit)
            return false;
    }
 
    for(y = ((i / 3) * 3); y < ((i / 3) * 3) + 3; y++)
    {
        for(x = ((j / 3) * 3); x < ((j / 3)) * 3 + 3; x++)
        {
            if(board[y*9+x] == digit)
                return false;
        }
    }
 
    return true;
}

<< Previous

Next >>