Fast Sudoku Solver

Rapidly finds all possible solutions to a sudoku puzzle

Description

SUDOKU - rapidly find all possible solutions to a sudoku puzzle

Usage: Mout = sudoku(M)

M = intial sudoku matrix, with zeros for empty entries
Mout = solution as a 9x9 matrix if there is a unique solution, or as a 9x9xN matrix if there are N solutions

Notes:
(1) The algorithm employs recursion, but does as much as it can with straighforward deterministic deduction at each recursion level to increase overall speed.
(2) Supplying this function with an empty or overly sparse input matrix can create longer calulation times as the function searches for all possible solutions.
(3) A "No solution" error is generated if the input puzzle has no valid solution.
(4) Tested but no warranty, use at your own risk.
(5) Michael Kleder, December 2006

Examples:

% find the unique solution to this puzzle in a fraction of a second:
M = [0 0 8 0 9 0 5 0 0;0 0 1 0 7 0 4 0 0;0 0 4 0 3 0 6 0 0;
     0 1 0 0 0 6 0 0 7;0 9 0 0 0 3 0 0 0;0 2 0 0 5 0 0 6 0;
     0 5 0 0 4 0 0 2 0;0 0 0 8 0 0 0 3 0;6 0 0 1 0 0 0 4 0];
sudoku(M)

% find the 100 possible solutions to this puzzle in few seconds:
M = [0 0 8 0 9 0 5 0 0;0 0 1 0 7 0 0 0 0;0 0 4 0 3 0 6 0 0;
     0 1 0 0 0 0 0 0 7;0 9 0 0 0 3 0 0 0;0 2 0 0 5 0 0 6 0;
     0 5 0 0 4 0 0 2 0;0 0 0 8 0 0 0 3 0;0 0 0 1 0 0 0 4 0];
tic;M=sudoku(M);toc;size(M,3)

• MATLAB release: MATLAB 7.1.0 (R14SP3)

[sachin rawat]

 

[sanjay kumar]

good

[kiko kiko]

Hi,
your submission produce the following message 'error using .....No solution' when I try to solve the follwing puzzle:
6 0 0 0 5 7 2 0 0
5 1 9 2 0 0 0 0 8
4 0 0 1 8 0 0 0 0
8 0 1 3 0 9 0 0 0
2 9 0 0 0 0 0 8 1
0 0 0 5 0 8 3 0 9
0 0 0 0 9 2 0 0 5
9 0 0 0 0 1 4 7 2
0 0 1 6 4 0 0 0 3
wich have a solution
Try to remove the bug.
kiko

[The Author]

Kiko, no solution exists because the puzzle you provided has two 1's in the third column, which is against the rules.

[Nelson Contreras]

That's some monster job.... awesome..... although i didn't understand the recursion thing...... but anyway..........
ja I also tried solving a sudoku with just 1 number in it...... as expected.... mi VAIO died trying it...........
Thanks... Saludos de Colombia

[Chris Raper]

I would agree with Kiko. I wrote my own sudoku solver and optimized it as best I could and also wrote a script to plot its performance by having it solve 41 puzzles of various difficulty from websudoku.com. When I ran this script for your solver, it was crashed when trying to solve evil difficulty puzzles and the blank puzzle (I had to manually end Matlab as a task through Ctrl-Alt-Del).
Also, it was interesting that for puzzles of each difficulty that were solved, the solution time grew in a highly linear fashion as each successive puzzle was solved. For example, for easy, medium and hard puzzles the first puzzle solved took about 0.1 s, and the last easy puzzle took 0.4 s, medium about 0.64 s, hard 1 s, once again the curves were very linear. Your first time is faster than my solver, but my solver wins on average time because of this increasing time-to-solution trend. Interesting.

[Chris L]

could anyone explain in simple english each step of the code, im new to matlab and i wanna know how its written, and the logic behind this particular code, any help is welcome, thanks

[rajchandar k]

Chris L
me too had the same doubt hmmmmm