Tag: algorithm

Sudoku Solving Algorithms

Sudoku solved by bactrackingThere are 81 cells in a standard 9 X 9 Sudoku grid. There are also 9 boxes (blocks or regions). These are formed where the first, center or last rows cross the first, center and last columns and are outlined with thicker borders.

In general, the numbers 1 through 9 are used as the symbols to fill each of the 81 cells in the grid.

3 Rules
Each row may only contain a symbol once.
Each column may only contain a symbol once.
Each block or box may only contain a symbol once.

There must be no repeats in any row, column or blocks.

A Sudoku puzzle is presented with some cells containing numbers (or other symbols). These are clues that will enable you to use the 3 rules to solve the empty cells. A proper Sudoku has only one solution.

It is possible to use computer algorithms to solve Sudokus. These may also be used to study the properties of Sudokus and make new puzzles.

The animation above shows a Sudoku puzzle being solved with a “brute force” algorithm – one method of using computers to solve these puzzles. The red numbers are the ones that were provided when the puzzle was set and these are fixed. The empty cells fill with alternatives as the algorithm tests possible solutions.

If the algorithm finds that the path it has set out on does not follow the 3 rules as it gets further down the Sudoku, it may discard all the previously found numbers and start all over again. Sometimes, humans have to do that too!