Sudoku Solver

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s