Sudoku Solver – Backtracking & deduction

/

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9. The rules are simple: each number can only appear once in a row, column or subgrid. Sugolver is a Sudoku solver written in Go.

In this article is describing the data structures and the algorithms used in this project hosted on Github at this following URL: https://github.com/lunatikub/sugolver. Enjoy the read !

Terminology

In this sudoku solver post and github code we will use a specific terminology to describe the different aspects of the Sudoku solver. Firstly 9 lines, 9 columns and 81 cells composed the grid. Secondly a cell contains a digit from 1 to 9 at coordinates (x,y).

Lines,Columns and Cells

For instance, a grid is subdivided with 9 regions called blocks, each block is identified by an integer called BlockID. So a block is composed of 3 lines, 3 columns and 3×3 (9) cells.

Blocks

We can deduce a number of constants sufficient to describe the whole problem to be solved

const (
	nrLine      = 9
	nrCol       = 9
	nrBlock     = 9
	nrVal       = 9
	nrBlockLine = 3
	nrBlockCol  = 3
)

And the two main data structures used in this project are: solver and cell.

type cell struct { }
type Solver struct { }

Candidates

One of the first things to do is to determinate the potential candidates for each cell. The algorithm is:

for  each empty cell of the grid {
    for each value from 0 to 9 {
        if the value is not on the cell's line, column and block {
            add it to the set of the cell candidates
        }
    }
} 

The number of candidates can be considered as the scale of complexity for the Sudoku to resolve from 0 (solved grid) to 9x9x9 = 729 (no initial value).

// File: solver.go
func (s *Solver) setCandidates() 
Example of simple Sudoku grid
Candidates for the previous example grid

Another useful method is when we set a value V to a cell, we have to update the candidates of all cells of the same linecolumn and block, by removing the value V of the respective set of candidates.

// File: solver.go
func (s *Solver) updateCandidates(line int, col int, v int) 

Deductive rules

The rules of the game allow us to deduce other deductive rules named which will be applied for the resolution of the problem and which can be sufficient to resolve the whole problem when the complexity of the grid is not too high.

Exclusivity

If we have found the value V of a cell C then this value is removed from all cases in the same block as C, in other words we update the lines, the cols and the block Boolean vectors.

// File: exclusivity.go
func (s *Solver) Exclusivity()

In the previous example (Candidates), we can see that the candidate at coordinate (y:2, x:3) can be set as the value 1. Consequently we have to update all candidates for the cells on the line:2, the column:3 and the block:1 by removing the value 1 from the respective set.

Exclusivity for the cell (y:2, x:3)

On the previous grid we have 195 candidates. After having updated the candidates, we have removed 13 candidates, so we lower the complexity of the grid and have found a new value.

Remove the value 1 of the candidates for the line 2, the col 3 and the block 1

After the candidates updates, we notice that the cells (y:1,x:3) and (y:2,x:5) became exclusivity cells also. Then we do the same process by updating candidates. So the value 2 (y:2, x:5) removes 7 candidates. So the value 9 (y:1,x:3) removes 3 candidates.

Candidates has been updated

We notice that we have more exclusivity cells at each iteration
[ (y:2,x:2), (y:0,x:3), (y:1,x:4) ]. Certainly this Grid can be resolved entirely by this rule.

Take a look on at resulting grid after we have set the three new values deduced from the Exclusivity rule.

Three new values has been found with the exclusivity rule

Uniqueness

If a cell C can contain several values, but one of these values ​​V is not possible in any other cell of its line or columns or block, then cell C contains the value V

// File: uniqueness.go
func (s *Solver) Uniqueness()

In the previous example (Candidates), we can see that the following candidates are respecting this rule:

  • 4 in cell (y:0,x:3)
  • 8 in cell (y:2,x:1)
  • 7 in cell (y:2,x:4)
  • 5 in cell (y:2,x:6)
  • 5 in cell (y:3,x:1)
  • 4 in cell (y:3,x:2)
  • 5 in cell (y:4,x:3)
  • 4 in cell (y:5,x:5)
  • 3 in cell (y:7,x:3)
  • 5 in cell (y:7,x:7)
All candidates respecting the uniqueness rule
The result grid

Parity

If a couple of cells (C,C’) on the same line or on the same column or in the same block can only contain the same pair of values {U,V} then we remove these two values of the candidates from lines, cols and blocks of C and C’ cells candidates.

// File: parity.go
func (b *Board) Parity()

In the previous example (Candidates), we can see that the following cells are respecting this rule:

  • Couple (C,C’): (y:0,x:7), (y:5,x:7) with {U,V} = {1,7}
  • Couple (C,C’): (y:3,x:4), (y:5,x:5) with {U,V} = {1,4}
Two couples has been detected for the rule Parity

We respectively remove both values {U,V} from all the cells of the block and the column. As you can see, the block 4 has a new exclusivity cell (y:3, x:5), that will create an other exclusivity cell (y:4,x:3) and so on. So the two couples we removed 11 candidates.

Candidates has been updated

Locked

This rule is not implemented yet

If in a block all candidates of a certain value are confined to a row or column, then the value cannot appear outside of that block in that row or column.

In the following example of candidates, we can see that the candidate 5 of the cell (y:2,x:6) can be removed.

This previous rule is named locked pointing. Moreover an other variant exists, and it is named lock claiming. This one works exactly the other way round:

If in a row or a column all candidates of a certain value are confined to one block, then the candidate can be eliminated from all other cells in that block.

Backtracking

Sometimes, when the complexity of the grid is to higher, we have to finish the solving of the Sudoku by trying all possibilities with the candidates. Therefore we use backtracking as the algorithm.

// File: backtracking.go
func (s *Solver) backtracking() bool

Note that the backtracking itself is enough to resolve any grid, if at least one solution exists, but it is less performant.

Take one of the simplest example of grid in order to explain how we process the backtracking.

Simple Sudoku Grid
Candidates of the simple grid

Following algorithm is applied (backtracking) on the previous example grid. For instance, we have isolated the sub block 5 and 8 to simplified the demonstration.

backtracking() {
    for each empty cell C {
        for each candidates V {
            if set V is valid {
                set V
                backtracking()
                reset C
            }
            return // no set available for this cell so backtrack !
        }
    }
    // A solution has been found here !
}

Step by step backtracking algorithm, we find a solution !

Solve

Now we have all the keys to have a sudoku solver !

Solve(initialValues [9][9]int) {
    var G grid = init(initialValues)
    do {
        nrExclu = exclusivity(G)
        nrUniq = uniqueness(G)
        nrParity = parity(G)
    } while (nrExlcu != 0 or nrUniq != 0 or nrParity != 0)

    if G is not completed {
        backtracking(G)
    }
}

For practical reasons (benchmark purpose), we can disable each of the three EUP rules when we solve a Sudoku.

// File: solver.go
func (s *Solver) Solve(doExclu bool, doUniq bool, doParity bool)

BenchMark

I have made a benchmark of the sudoku solver in order to compare performance on the resolution of a grid with and without the EUP rules applied.

Hardware which has been used:

  • Latitude E7450 (062E)
  • Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz
  • 2x8GiB SODIMM DDR3 Synchronous 1600 MHz

Kernel/distribution which has been used:

❯ uname -a
Linux dune 4.15.0-115-generic #116-Ubuntu SMP Wed Aug 26 14:04:49 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
❯ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04.4 LTS"

Command which has been used:

perf stat -e cycles

The following table summarizes the results. So each line is an average of 1000 iterations on 10 different grids.

difficultyrules enabledcyclestime (us)
simpleno41899368 13493437
simpleyes2423307924195
easy no279893679115144
easy yes33036631235379
intermediateno9715597930944644
intermediateyes33892701275257
expertno9625717730630902
expertyes52363181855740

We notice two important things:

  • The performance resolution is always better with the EUP rules applied
  • The more complex the grid is the higher the gain will be.

Feel free to leave a message for any questions or suggestions, I’ll be more than happy to answer or can contact me at: [email protected]

[bws_google_captcha]