DI Management Home > Su Doku

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.

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 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. People who are good at reading source code might also like to check out uk best online casinos.

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.

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 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).

What we do

Apart from being distracted solving Su Doku problems, at DI Management we

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

Is there any code that u've made using access as backend and vb6 as front end for sudoku game

Srinivasan | Bangalore - Wed, Mar 17 2010 18:44 GMT

No.

Dave | Moderator - Fri, Mar 26 2010 22:08 GMT

Nice work!

Ian | - Fri, Apr 2 2010 01:20 GMT

I need to implement an algorithm that will plot into a sudoku grid, solutions to empty spaces that only have one choice.

Any suggestions on how to do this would be cool

V2rocketboy | - Thu, Apr 8 2010 10:50 GMT

Great job! Would you care to write a short article or do a q/a session for my blog, Excel spreadsheets help?

NTW | - Sun, Apr 18 2010 01:56 GMT

what a genius solver for soduku. :D

sudoku | www.sudoklue.se - Mon, Oct 11 2010 08:38 GMT

Thank you! Tonight, I was thinking about, how to make a sudoku solver, using excel and visual basic. Now I have found your website. I'll try to learn all steps of the algorithm, may be I could develop this algorithm, or implement it to the other problem.

It is very valuable information for me, thanks for a great job!

role model | - Thu, Mar 17 2011 01:03 GMT

Hi there,

When it solves the sudoku in the excel version a number which corresponds to the difficulty appears. Which is the range of this grading? Your very hard appeared as 8 while one i put as 50!

By the way, NICE WORK guys!

Sudoku amateur | - Sun, Apr 3 2011 20:52 GMT