Sudoku is a logic-based, combinatorial, number-placement puzzle. The objective is to fill a 9*9 grid with digits so that each column, each row and each of the nine 3*3 sub-grids contain all of the digits from 1 to 9.

Sudoku solvers employ backtracking to fill in the grid. Backtracking works by trying all the possible combinations of digits in the empty squares. If at any stage we have successfully filled all the empty cells the algorithm has found a solution and it stops. Here’s a visual aid.

My C++ code can be found here.

**Performance evaluation**

I put the code to test with some easy and hard Sudokus.

Easy Sudokus – http://magictour.free.fr/msk_009

Total number of Sudokus = 1011

Solved = 1011

Failed = 0

Total time taken = 42.8299s

Max time 2.96s taken for Sudoku number 45

Min time 0s taken for Sudoku number 12

Average time = 0.0423639s

All the solutions can be found here.

Hard Sudokus – http://magictour.free.fr/top1465

Total number of Sudokus = 1465

Solved = 1465

Failed = 0

Total time taken = 538.891s

Max time 46.63s taken for Sudoku number 230

Min time 0s taken for Sudoku number 42

Average time = 0.367843s

All the solutions can be found here.

Hard Sudokus – http://magictour.free.fr/topn87

Total number of Sudokus = 87

Solved = 87

Failed = 0

Total time taken = 27s

Max time 4.16s taken for Sudoku number 29

Min time 0s taken for Sudoku number 38

Average time = 0.310345s

All the solutions can be found here.

Hard Sudokus – http://magictour.free.fr/topn234

Total number of Sudokus = 234

Solved = 234

Failed = 0

Total time taken = 186.31s

Max time 46.11s taken for Sudoku number 220

Min time 0s taken for Sudoku number 44

Average time = 0.796197s

All the solutions can be found here.

Hard Sudokus – http://magictour.free.fr/top95

Total number of Sudokus = 95

Solved = 95

Failed = 0

Total time taken = 188.36s

Max time 49.11s taken for Sudoku number 1

Min time 0s taken for Sudoku number 19

Average time = 1.98274s

All the solutions can be found here.