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'

The spreadsheet doesn't do any real checking of input data, so don't complain if you enter something invalid and get rubbish back.

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.

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.

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.

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 distinct numbers that add up to 10, 11_3[5] means there are 5 combinations of 3 distinct numbers 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. That is, there is only one combination of 4 distinct numbers that equals 10 (=4+3+2+1) and only one for 11 (=5+3+2+1).

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.

See our cryptography source code page and our commercial CryptoSys family of cryptographic products for Visual Basic and C/C++.

Contact us

For more information, or to comment on this page, please send us a message.

This page last updated 17 October 2014. Reformatted for HTML5 13 June 2020.