Home |
Col's Free Sudoku SolverGenerate & Solve Sudoku Puzzles! |
Sudoku Solver FAQWhat is it?Col's Sudoku Solver is a freely downloadable program that helps you solve Sudoku puzzles. It gives you full, interactive control over the solving process, and explains everything it's doing every step of the way. Where is the latest version? Download v4.1 here (64k) This .zip archive contains a Windows executable (exe) file plus a selection of sample problems and a ReadMe with instructions for use. What's a Sudoku puzzle? Take a look at this site for a detailed explanation. Also occasionally spelled "su doku", "su do ku" or "sudoko". The name is taken from the Japanese for 'Single Number'. It is sometimes known in the USA as "Number Place". You can find out more, plus chat with fans, on Michael Mepham's site. What's new in version v4.0? Pretty much everything. Here's the Progress file. How does it solve the Sudoku puzzles? Using two very simple logical tricks, and a permission matrix. Recent versions use a few complex algorithms that are outlined in the ReadMe File. What is a permission matrix? For each of the 81 squares in the grid, it works out which of the numbers 1-9 could be in that square. It does this by crossing off any numbers which are already found in the current row, column or 3x3 cell. What are the two simple tricks? In English, they amount to "Which cells could only be one number?" and "which numbers could only be in one cell?" Firstly, it calculates the permission matrix (see above) and then looks to see if any cells have only one legal value. If this is true then it fills them in right away. The second method is similar. You can choose to apply it to either a 3*3 cell, a row or a column. Within those nine squares, it checks to see if there is only one square which can possibly contain a specific number. If this is the case, then it fills it in. That's it! There are some really difficult problems for which these two methods aren't enough. For those you have to manually remove permission values according to specific clever tricks. I've implemented loads of those now, too. Everything is explained in the ReadMe file. What methods have you implemented? As of version v4.0, I've implemented Constrictions; Disjoint subsets; Unique subsets; Neighbour pairs; X-Wing; Swordfish; Nishio; Forcing chains. Those algorithms are sufficient to solve any (solvable) Sudoku puzzle I've ever found. Plus I've implemented a depth-first search routine based on Donald Knuth's "Dancing Links" algorithm, which can solve around 1,000 puzzles per second! Can it print out the Sudoku puzzles? No, but as of version v4.0 it can export the puzzles to text, HTML or PostScript formats. These can all be easily printed. If you want a postscript viewer then you can find one here Can I see the logic behind the Sudoku Solver? When you click on any of the buttons, the programme shows you in grey the numbers that it was able to calculate using that method. These numbers are absolutely 100% correct, not guesses. As soon as you have checked through them, and understand how they were derived, you can then accept them using the 'Update Board' button. Then it fills them in in blue, and recalculates the new permission matrix using these values. You can also highlight the squares which are legal positions for specific numbers. Try clicking the numbers towards the bottom of the control pad dialog box. This shades out squares where the specified number could not be placed. Plus, from v4.0 onwards, you now also have a textual explanation box, accessed from the "Help" menu. This explains exactly why the SuDoku solver has made every single choice. Can I load and save Sudoku puzzles? Yes, in a simple 9*9 matrix format. See the example data files that I included with the .zip distribution for how to do this. It's really easy. Your code broke my computer / cost me money / ate my hamster / ran off with my wife / etc. How unfortunate. I suggest you employ a very expensive lawyer with an excellent sense of humour. Can I contact you to suggest improvements / bugfixes etc.? Certainly. I can be contacted at colin@frayn.net. Can I have a copy of the source code? I gave out some source code to earlier versions, but I'm keeping a lid on the newer versions, I'm afraid. Hey, I'm giving the helper away for free, what more do you want? How can I help? Well the best thing you can do is to link to my page. If you own a Weblog, or any other kind of website, just put in a text link to this page so that more people can find out about my program. That would be great! If you particularly want to send me money, you can do so through PayPal. And it's totally secure. And if you visit the sponsored links on the left of this page then the wonderful folk at Google send me money, too! Where can I get daily Sudoku puzzles? You can use Col's Free Sudoku Solver to produce as many free sudoku puzzles as you want! You no longer need another source! What's the shortest Sudoku solver on the Web? Well, if you're a fan of OCaml, then check out Jon Harrop's SuDoku solver in 19 lines of code. Though it may hurt your brain. What do you work on when you're not doing Sudoku? I work at Cercia, primarily on data mining and visualisation technologies. Please visit the homepage of my colleague Andy Pryke, to learn more about data mining. |