Sudoku Algorithm: Strategies to Avoid Backtracking

• Download executable - 8.25 KB
• Download source code (C#) - 19.03 KB

Introduction

First of all, I must confess that I'm not a fan of Sudoku. However, after seeing my wife spend 5 to 10 minutes every day solving the daily puzzle in the newspaper, I try to understand her strategy. Several friends like this puzzle, but they spend much more time, so my wife has something! A week after, I share her advices to solve this puzzle with all of you, but in a language I understand... C#...

What is Sudoku?

As shown in the image above, Sudoku consists in 81 cells, distributed in a 9x9 matrix. This matrix is composed of 9 rows and 9 columns, each with 9 cells. Additionally, there are 9 groups of 3x3-matrixes (as shown above), that we call "squares" in this article. The idea is to write a digit between 1 and 9 in each cell, but the game has some rules:

• You cannot write the same digit in two or more cells of the same row.
• You cannot write the same digit in two or more cells of the same column.
• You cannot write the same digit in two or more cells of the same "square"

Sudoku Strategies to Solve a Cell

The algorithm uses four strategies to determine a valid value for a cell in the Sudoku board. The strategies are the following:

• Search for cells with a unique solution possible.
• Search for rows with a unique cell for an specific digit.
• Search for columns with a unique cell for an specific digit.
• Search for "squares" with a unique cell for an specific digit.
• Pick a value randomly from the available valid values for a cell.

This programs applies the 4 first strategies into a loop. This 4 strategies have proven to be sufficient to solve any Sudoku puzzle with one solution. In other words, if a Sudoku puzzle has only one solution, these 4 strategies are enough to find this solution.

If the Sudoku puzzle has more than one solution, the last strategy is needed: Pick a Random value for the cell.

Searching for Cells with a Unique Solution Possible

This strategy consists of finding the list of all the possible values for a cell that don't have a conflict with the current values of the other cells. This means that a cell has only one possible value according to the rules of the puzzle. This is an example:

The grayed cell can only have one valid solution: 7. If you check, all the other values create a conflict with the cells with the red circles.

Searching for Rows, Columns and "Squares" with a Unique Cell for a Specific Digit

Each row must have all the digits between 1 and 9. This strategy consists of finding all the cells where each digit can be placed. If one of these values can only be placed into one cell in a specific row, then we have found a solution for that cell. This is an example:

The row marked can only host the value 2 in the grayed cell. All of the other cells in this row cannot have this value, because of the cells with the red circles. This concept can be applied as well for each column and "square" to find other solutions.

Details of the Application

The application shows in the main user interface a Sudoku board where you can place the initial values for the puzzle. If you don't write any initial value for any cell, the program will generate a random Sudoku board.

To solve the puzzle, the application applies the 4 deterministic strategies, in the same order as shown before. If any of those strategies produces a solution, then the first strategy will be run again, until the Sudoku board is solved. If the 4 strategies are applied, and no new solution for a cell is generated, and the Sudoku board is not complete, then this Sudoku has more than one solution, so we must use the random strategy.

First, we determinate which cell has the minimum of possible valid values. We do so, to avoid picking a random value to a cell with a high set of possible solutions, because this can cause cells with a short set of valid solutions to end up without any value. This is the strategy to avoid the need of a backtracking algorithm. After we pick a random value for the selected cell, we go back to execute the 4 basic strategies again. We do this until we have a valid solution for the board.

No Need for Backtracking?

As mentioned before, this application does not need a Backtracking Algorithm, because we don't depend only on random selections for the cells. And when the random strategy is needed, we pick a random value for the "more unfortunate cell", this is, the cell with the shortest set of valid values.

Solving Strategy Details

The application shows a detail of each strategy used, specifying the solved cell, and the selected value.

History

• 27^th January, 2008: First publication