Su Doku Solver
Su Doku problems were introduced to the UK in The Times on the weekend of 13-14 November 2004. Since then they have somewhat risen in popularity. I wrote this 9 x 9 Su Doku solver the next week and released it on 21 November 2004. It's an Excel spreadsheet which makes entering the data into the grid particularly easy. There are about 800 lines of VBA code behind it. It works for (almost*) all problems we've seen so far. Since we wrote it, though, we lost interest in Su Doku completely, but we'd still be interested in feedback on the program. If you want the full source code behind the spreadsheet, please just read this page properly.
Download | Source Code | Algorithm Explained | Insolvable problems? | Other Solvers | Postscript - why we're not updating it | 'Killer' Su Doku | What We Do
To use our spreadsheet to solve a Su Doku problem, enter the given values into the grid...
...and click on 'Solve It'
It doesn't do any real checking of input data, so don't complain if it fails if you enter rubbish.
Download the spreadsheet
Download the Excel spreadsheet (125 kB) or a zipped version (46 kB). First published 21 November 2004.Source code
View the source code or see in text format.Algorithm
There are 3 stages:-Start with a matrix of 81 squares each with 9 'possible' values
As you fill in a new number, remove all the possibles in (a) the same row, (b) the same column and (c) the same box.
First Stage: Work through each square in turn and see if it only has one possibility. If so, we've solved that square, so fill it in and remove all associated possibilities. Repeat this until you get no more changes.
This first stage solves most easy and medium problems outright.
2nd Stage: Now work through each row, column and box in turn and check all remaining values 1..9 in turn in each unsolved square of the set. See if we can find a square that can only have one possible value. This lets us fill in some more and then we repeat with stage 1 again.
This second stage solves most hard ones.
3rd Stage: If we've not solved it by now, we've finished the simple deterministic process and we now have to guess one of the possibles. Find the square with the least number of possibles and pick one of them. This gets tricky because we now have to remember all we fill in from now on so we can delete them all if we're wrong. Having guessed one square, repeat stages 1 and 2 again.
If our guess solves it, we're done. If not, delete all the guesses and pick the next guess. Repeat until we solve it. Remember Sudoku isn't bingo; it requires a certain amount of patience, dedication and commitment.
Insolvable Problems
* Well it solves all problems for a certain meaning of the word 'all' anyway. We've found two problems so far for which our solver fails to find a solution. The two problems are in this spreadsheet. Thanks to Professor Leigh Palmer and Angus Walker for bringing these to our attention.
Professor Jakob Stoustrup of Aalborg University has confirmed that one of the problems does indeed have two distinct solutions
a =
7 3 1 5 8 4 6 9 2
6 9 4 3 1 2 8 7 5
8 2 5 7 9 6 1 4 3
1 6 7 4 3 9 5 2 8
4 8 9 2 5 1 3 6 7
3 5 2 6 7 8 4 1 9
9 1 3 8 4 7 2 5 6
2 4 8 9 6 5 7 3 1
5 7 6 1 2 3 9 8 4
b =
7 3 5 8 9 4 6 2 1
6 9 4 3 1 2 8 7 5
8 2 1 7 6 5 4 9 3
5 8 9 4 3 1 2 6 7
4 6 7 5 2 9 3 1 8
3 1 2 6 7 8 5 4 9
9 4 3 2 8 7 1 5 6
1 5 8 9 4 6 7 3 2
2 7 6 1 5 3 9 8 4
and that the other has a unique solution
c =
1 2 6 4 3 7 9 5 8
8 9 5 6 2 1 4 7 3
3 7 4 9 8 5 1 2 6
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 3 9 4
2 6 9 3 1 4 7 8 5
5 4 8 7 6 9 2 3 1
7 3 1 8 5 2 6 4 9
but this particular problem takes his algorithm over a minute to find instead of a few seconds.
Update 24 July 2007. Manulal M Inasu points out that the first problem (the one with two solutions)
can be solved just by increasing the value of ncGUESSEDMAX in our program from 12 to 30.
Increasing the limit further, however, does not solve the other one - it just leads to a stack overflow error.
Update 24 January 2008. Professor Nigel Topham tells us that the first problem which is claimed to have two solutions actually has 37 distinct solutions.
Other solvers out there
Martin Highmore published a Java-based Su Doku Solver with source code at the same time as us in November 2004. Gwerdy's SuDoku Solver has a very clear explanation of their algorithm. Most elegant of all, we think, is the Su Doku solver in three lines, a solution by Edmund von der Burg that uses Perl (thanks to a no doubt disinterested Christer von der Burg for pointing out this site).Postscript - why we're not updating it
2 June 2005. I wrote the Excel solver when the Times first started publishing its Su Doku problems in November 2004. I was in London at the time and the spreadsheet and its associated program were written up in about 6 hours based on techniques developed in the first week of its publication. Having solved it, though, I completely lost interest in the subject, and still have. Thanks to all those of you who have written in to suggest improvements to the program. Are we going to update the program? No. It works. It takes at the most a second or two to find a solution to even the most "fiendish" problems. Completing the program to work without guessing would be a nice theoretical exercise, but we have better things to do. If you want to unlock the original spreadsheet, the password is "kv6vh3bych9jkb7y". If you find it useful, please make use of it. Of course, if you want to share your champage with us, please do.
Meanwhile, please enjoy Private Eye's version of Su Doku for Sun readers:-
Killer Su Doku
30 September 2005. There's now a new version called "Killer Su Doku". A much more interesting variant that shows the total of cells joined by dotted lines together with the usual rules.
This version is more difficult and interesting than the original, and will appeal to people who are interested in a challenge, such as people who count cards playing blackjack at a casino, or can complete a maths puzzle easily.
Fans of Killer Su Doku may find the following table useful. It shows all combinations of distinct numbers between 1 and 9 that add up to a given total.
Here is an extract:-
10_2[4]={{9,1},{8,2},{7,3},{6,4}}
10_3[4]={{7,2,1},{6,3,1},{5,4,1},{5,3,2}}
10_4[1]={{4,3,2,1}}
11_2[4]={{9,2},{8,3},{7,4},{6,5}}
11_3[5]={{8,2,1},{7,3,1},{6,4,1},{6,3,2},{5,4,2}}
11_4[1]={{5,3,2,1}}
12_2[3]={{9,3},{8,4},{7,5}}
Notation: 10_2[4] means there are 4 combinations of 2 digits that add up to 10,
11_3[5] means there are 5 combinations of 3 digits that add up to 11,
and so on. The really useful ones are those that only have one combination, like
10_4 and 11_4.
Download the full table (7 kB). Good luck.
What we do
Apart from being distracted solving Su Doku problems, at DI Management we
- Design databases for a variety of clients.
- Write programs that do cryptography, analyze email files and other stuff.
- Please look at our:
- DBXanalyzer program that reads, analyses and manages email data files created by Microsoft Outlook Express 5 and 6.
- Wclock, a free, customisable, always-on-top world time clock for Win32 computers.
Contact us
For more information, please send us an email. To comment on this page, see below.
This page last updated 3 January 2010
Comments
0 comments so far