Idea Transcript
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. 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
Comments [Go to last comment] 9 comments so far [Sorry, comments are now closed. Thanks to everyone below for their contributions.] 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. Sorry. 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 Downloaded this program, works a treat, thankyou rusticgal | Australia - Sat, Apr 9 2011 08:09 GMT [Go to first comment] Copyright © 2004-14 DI Management Services Pty Limited ABN 78 083 210 584 Australia. www.di-mgt.com.au. All rights reserved. Home | Services | About Us | Projects | Links | Cryptography | CryptoSys API | CryptoSys PKI | DBXanalyzer | BigDigits | Mathematics | Wclock | Su Doku | About This Site | Contact | Email Us