No BSD License  

Highlights from
Fast Sudoku Solver

4.2

4.2 | 5 ratings Rate this file 20 Downloads (last 30 days) File Size: 4.49 KB File ID: #13324

Fast Sudoku Solver

by

 

09 Dec 2006 (Updated )

Rapidly finds all possible solutions to a sudoku puzzle

| Watch this File

File Information
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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (8)
23 Dec 2008 rajchandar k

Chris L
me too had the same doubt hmmmmm

31 Mar 2008 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

17 Feb 2008 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.

10 Jan 2008 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

12 Nov 2007 The Author

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

13 Sep 2007 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

22 Jan 2007 sanjay kumar

good

07 Jan 2007 sachin rawat  

Contact us