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.

## 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. ```