Click here to Skip to main content
11,577,258 members (57,390 online)
Click here to Skip to main content

Tagged as

Sudoku Algorithm: Strategies to Avoid Backtracking

, 27 Jan 2008 CPOL 98.2K 2.5K 31
Rate this:
Please Sign up or sign in to vote.
A Sudoku algorithm with 4 deterministic strategies to avoid backtracking
Sudoku Solver Main App

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:

Sudoku Unique Solution Cell

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:

Sudoku Row Solution Cell

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.

Sudoku Strategy Details

History

  • 27th January, 2008: First publication

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

PeterMoon
Software Developer (Senior)
Ecuador Ecuador
No Biography provided

You may also be interested in...

Comments and Discussions

 
QuestionThis does not solve all unique sudokus Pin
Andrew Tristram11-Jan-13 9:59
memberAndrew Tristram11-Jan-13 9:59 
Generalmichael anwar Pin
michael azzar16-Feb-12 7:42
membermichael azzar16-Feb-12 7:42 
GeneralGood selution with great code Pin
Member 780973814-Apr-11 6:47
memberMember 780973814-Apr-11 6:47 
GeneralI'm not sure what you're talking about Pin
mwpowellnm7231-Mar-11 15:43
membermwpowellnm7231-Mar-11 15:43 
GeneralMy vote of 3 Pin
Ercan Ozgonul4-Aug-10 21:30
memberErcan Ozgonul4-Aug-10 21:30 
Generalproblem solving a grid Pin
Spirch24-Feb-09 11:24
memberSpirch24-Feb-09 11:24 
QuestionBitArray in SudokuSolver Pin
Member 394196628-Feb-08 7:46
memberMember 394196628-Feb-08 7:46 
GeneralRe: BitArray in SudokuSolver Pin
Member 394196628-Feb-08 8:08
memberMember 394196628-Feb-08 8:08 
GeneralMinimum Sudokus Pin
_cancer_28-Jan-08 9:18
member_cancer_28-Jan-08 9:18 
GeneralRe: Minimum Sudokus Pin
PeterMoon28-Jan-08 10:36
memberPeterMoon28-Jan-08 10:36 
GeneralRe: Minimum Sudokus Pin
Philippe Mori17-Jul-11 15:05
memberPhilippe Mori17-Jul-11 15:05 
GeneralSudoku's real problem Pin
Edward11128-Jan-08 8:14
memberEdward11128-Jan-08 8:14 
GeneralRe: Sudoku's real problem Pin
PeterMoon28-Jan-08 9:13
memberPeterMoon28-Jan-08 9:13 
GeneralRe: Sudoku's real problem Pin
Edward11128-Jan-08 12:51
memberEdward11128-Jan-08 12:51 
GeneralRe: Sudoku's real problem Pin
Syed Mehroz Alam28-Jan-08 19:00
memberSyed Mehroz Alam28-Jan-08 19:00 
GeneralRe: Sudoku's real problem Pin
Louwgi28-Jan-08 23:25
memberLouwgi28-Jan-08 23:25 
GeneralRe: Sudoku's real problem Pin
MartinXLord5-Feb-08 19:13
memberMartinXLord5-Feb-08 19:13 
GeneralRe: Sudoku's real problem Pin
Louwgi5-Feb-08 19:30
memberLouwgi5-Feb-08 19:30 
GeneralRe: Sudoku's real problem Pin
PeterMoon6-Feb-08 6:26
memberPeterMoon6-Feb-08 6:26 
GeneralRe: Sudoku's real problem Pin
languagedog14-Oct-09 8:31
memberlanguagedog14-Oct-09 8:31 
GeneralNice Solution but... [modified] Pin
megger8327-Jan-08 21:32
membermegger8327-Jan-08 21:32 
GeneralRe: Nice Solution but... Pin
PeterMoon28-Jan-08 4:02
memberPeterMoon28-Jan-08 4:02 
GeneralRe: Nice Solution but... Pin
MartinXLord5-Feb-08 19:25
memberMartinXLord5-Feb-08 19:25 
GeneralRe: Nice Solution but... Pin
PeterMoon6-Feb-08 6:20
memberPeterMoon6-Feb-08 6:20 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150603.1 | Last Updated 27 Jan 2008
Article Copyright 2008 by PeterMoon
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid