12,405,270 members (68,375 online)
alternative version

102.9K views
31 bookmarked
Posted

# Sudoku Algorithm: Strategies to Avoid Backtracking

, 27 Jan 2008 CPOL
 Rate this:
A Sudoku algorithm with 4 deterministic strategies to avoid backtracking

## 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

• 27th January, 2008: First publication

## About the Author

 Software Developer (Senior) Ecuador
No Biography provided

## Comments and Discussions

 First Prev Next
 This does not solve all unique sudokus Andrew Tristram11-Jan-13 9:59 Andrew Tristram 11-Jan-13 9:59
 michael anwar michael azzar16-Feb-12 7:42 michael azzar 16-Feb-12 7:42
 Good selution with great code Member 780973814-Apr-11 6:47 Member 7809738 14-Apr-11 6:47
 I'm not sure what you're talking about mwpowellnm7231-Mar-11 15:43 mwpowellnm72 31-Mar-11 15:43
 My vote of 3 Ercan Ozgonul4-Aug-10 21:30 Ercan Ozgonul 4-Aug-10 21:30
 problem solving a grid Spirch24-Feb-09 11:24 Spirch 24-Feb-09 11:24
 BitArray in SudokuSolver Member 394196628-Feb-08 7:46 Member 3941966 28-Feb-08 7:46
 Re: BitArray in SudokuSolver Member 394196628-Feb-08 8:08 Member 3941966 28-Feb-08 8:08
 Minimum Sudokus _cancer_28-Jan-08 9:18 _cancer_ 28-Jan-08 9:18
 Re: Minimum Sudokus PeterMoon28-Jan-08 10:36 PeterMoon 28-Jan-08 10:36
 Re: Minimum Sudokus Philippe Mori17-Jul-11 15:05 Philippe Mori 17-Jul-11 15:05
 Sudoku's real problem Edward11128-Jan-08 8:14 Edward111 28-Jan-08 8:14
 Re: Sudoku's real problem PeterMoon28-Jan-08 9:13 PeterMoon 28-Jan-08 9:13
 Re: Sudoku's real problem Edward11128-Jan-08 12:51 Edward111 28-Jan-08 12:51
 Re: Sudoku's real problem Syed Mehroz Alam28-Jan-08 19:00 Syed Mehroz Alam 28-Jan-08 19:00
 Re: Sudoku's real problem Louwgi28-Jan-08 23:25 Louwgi 28-Jan-08 23:25
 Re: Sudoku's real problem MartinXLord5-Feb-08 19:13 MartinXLord 5-Feb-08 19:13
 Re: Sudoku's real problem Louwgi5-Feb-08 19:30 Louwgi 5-Feb-08 19:30
 Re: Sudoku's real problem PeterMoon6-Feb-08 6:26 PeterMoon 6-Feb-08 6:26
 Re: Sudoku's real problem languagedog14-Oct-09 8:31 languagedog 14-Oct-09 8:31
 Nice Solution but... [modified] megger8327-Jan-08 21:32 megger83 27-Jan-08 21:32
 Re: Nice Solution but... PeterMoon28-Jan-08 4:02 PeterMoon 28-Jan-08 4:02
 Re: Nice Solution but... MartinXLord5-Feb-08 19:25 MartinXLord 5-Feb-08 19:25
 Re: Nice Solution but... PeterMoon6-Feb-08 6:20 PeterMoon 6-Feb-08 6:20
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Jul-16 3:23 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.