MATLAB Examples

Sudoku Solver Benchmarking

Solving a Sudoku puzzle in MATLAB may not be a challenge, but to solve it quickly is not so easy. More than 20 Sudoku solvers have been submitted in MATLAB File Exchange. Most of them use recursive approaches, which, without non-recursive algorithm support, could be very inefficient. In this package, an efficient Sudoku solver, YASS (Yet Another Sudoku Solver) is developed as a benchmark for comparison of various sudoku solvers.

Contents

YASS - Yet Another Sudoku Solver

YASS is an intelligent Sudoku solver. It maintains a Candidate Map (C, a 81 x 9 logical array) to discover the solution. Initially, without any number on the Board (B, 9 x 9 array), all elements of C is true, indicating that at any position, there are 9 candidates. Each of 9 x 9 grids belongs to a row, a column and a block, marked as (r,c,b). Let 81 x 1 vectors I, J and K represent row, column and block indices of all grids respectively. When a specific number, n is put into the grid (r,c,b), i.e. B(r,c)=n, then all grids in L=(I==r | J==c | K==b) should not have candidate n, hence C(L,n)=false. If a row of C has only one candidate, i.e. L=sum(C,2)==1, then, the corresponding grid is solved, i.e. B(L(k))=find(C(L(k),:),'first'). Many other rules have been implemented to update C. These rules constitute the non-recursive solver of YASS.

If a puzzle cannot be completely solved by the non-recursive solver, a recursive solver will be called. The recursive solver will always try the grid, which has the minimum number of candidates indicated by C. For example, a grid m has two candidates, n1 and n2. The recursive solver will set B(m)=n1 and call the non-recursive solver to find the rest solutions. If an error is returned by the non-recursive solver, then the recursive solver will set B(m)=n2 to call the non-recursive solver again. If both branches are failed, then the puzzle is not valid.

For most puzzles, YASS is able to solve it within a fraction of a second.

Sudoku Example 1: A level-1 puzzle:

 A=[0    4    0    0    0    0    3    0    0
    0    0    2    0    0    0    0    5    0
    0    0    0    0    8    1    0    0    0
    0    0    0    0    0    0    4    1    8
    0    0    0    5    0    9    0    0    0
    0    0    0    0    0    0    0    0    6
    0    0    0    4    3    0    2    0    0
    1    0    0    0    0    0    0    0    0
    0    0    0    7    0    0    0    0    0];
tic,[B,level]=yass(A);t=toc;
fprintf('This is a level %i puzzle.\n It has been solved in %g seconds.\n The solution is:\n',level,t);
disp(B)
This is a level 1 puzzle.
 It has been solved in 0.0239544 seconds.
 The solution is:
     6     4     1     9     5     7     3     8     2
     9     8     2     3     6     4     1     5     7
     3     7     5     2     8     1     9     6     4
     7     5     9     6     2     3     4     1     8
     8     1     6     5     4     9     7     2     3
     4     2     3     1     7     8     5     9     6
     5     9     8     4     3     6     2     7     1
     1     3     7     8     9     2     6     4     5
     2     6     4     7     1     5     8     3     9

Sudoku Example 2: Find 100 Solutions of an Empty Puzzle:

tic,B=yass(zeros(9),100);toc
Elapsed time is 0.664327 seconds.

Sudoku Library

The parckage contains a huge Sudoku library with more than 30,000 puzzles of three levels (easy, normal and hard).

load supersudokulib sudokulib Level
fprintf('The library has total %i puzzles.\n %i of them are level 1.\n %i are normal and\n %i are hard levels.\n', size(sudokulib,1),sum(Level))
The library has total 33171 puzzles.
 25698 of them are level 1.
 2501 are normal and
 4972 are hard levels.

Benchmark

The bencmark is designed to check correctness of solutions and to compare computation time over a number of puzzles. The YASS solver is adopted as the reference to compare any another solver provided by users.

Benchmark Example 1: Against Itself over 100 x 3 Puzzles

tic,sudukubench(@yass);t=toc;
fprintf('100 x 3 x 2 puzzles are solved by YASS in %g seconds.',t);
100 x 3 x 2 puzzles are solved by YASS in 29.1941 seconds.

Benchmark Example 2: Fast Sudoku Solver by Michael Kleder

The code can be downloaded from File Exchange ID 13324 The code is abut 10 times slower than YASS. Hence, only 5 puzzles are compared.

perf=sudukubench(@sudoku13324,5);
for L=1:3
    fprintf('Level %i\n error: %g\n computation time is about %g of the times spent by YASS.\n',L,perf{L}.error,perf{L}.time)
end
Level 1
 error: 0
 computation time is about 2.71429 of the times spent by YASS.
Level 2
 error: 0
 computation time is about 6.09091 of the times spent by YASS.
Level 3
 error: 0
 computation time is about 7.33333 of the times spent by YASS.

Benchmark Example 3: Dancing Links Solver by Per-Anders Ekstrom

The code can be downloaded from File Exchange ID 14073 The code is abut 10 times faster than YASS!

perf=sudukubench(@(board)reshape(dlxsolver(board(:)),9,9));
for L=1:3
    fprintf('Level %i\n error: %g\n computation time is about %g of the time spent by YASS.\n',L,perf{L}.error,perf{L}.time)
end
Level 1
 error: 0
 computation time is about 0.0449438 of the time spent by YASS.
Level 2
 error: 0
 computation time is about 0.114155 of the time spent by YASS.
Level 3
 error: 0
 computation time is about 0.0680272 of the time spent by YASS.