Sudoku Solver 0.1 README http://grahamrobinson.com/sudoku 1. Introduction 2. Manifest 3. Installation 4. Using the Program 5. Known Bugs 6. To Do List 7. Registering 8. Contacting the Author 9. Warranty 10. Copyright Appendix. A guaranteed technique for solving Sudoku puzzles. *********************************************************** * IF YOU USE THIS PROGRAM, PLEASE CONSIDER REGISTERING. * * REGISTRATION SUPPORTS FURTHER DEVELOPMENT OF THIS AND * * RELATED PROGRAMS. * *********************************************************** 1. INTRODUCTION Since discovering Sudoku, I've been fascinated by the puzzles. Solving them is a pleasant way to pass a bus journey. But the real joy for me was working out new ways to tackle the problems. The result of that fascination is this program. Some might object to mechanical aids for solving Sudoku puzzles, perhaps viewing it as "cheating". In fact, there are straight- forward, guaranteed-successful techniques for solving Sudoku by hand. I've included one in the appendix of this document. In creating this program, I've tried to make it useful for a range of people. As well as solving the puzzle, SudokuSolver announces if the solution is not unique, and can be set to only give the next step, for those who might want a hint rather than a solution. Whenever possible, the program attempts to find a unique next step - one that can be worked out from logic, rather than guessing. Sometimes it is not possible to solve a puzzle without guesswork. For example, any puzzle which does not have a unique solution requires guesses at some point. SudokuSolver admits when it needs to guess. SudokuSolver is very much a work in progress. New techniques for solving puzzles will be added as I uncover them. However, I believe that the program already solves all puzzles which have solutions. 2. MANIFEST The latest version of this software is always available from : http://grahamrobinson.com/sudoku When installed, the SudokuSolver folder should contain : SudokuSolver.exe - the program itself README.txt - this file LICENSE.txt - details how you are allowed to use and distribute this software 3. INSTALLATION This software requires the Microsoft .NET Framework to be installed on your computer. Most modern Windows systems have .NET installed by default. If yours doesn't, the installer will attempt to download the .NET framework for you. This may take some time. Failing that, .NET can be downloaded from http://www.microsoft.com The software only runs on Windows. It has been tested on Me and XP, and should run on other variants as well. If you have problems, please see the section on reporting bugs, under "Contacting the Author". To install double-click on the SETUP.exe icon, and follow the on- screen instructions. 4. USING THE PROGRAM Double Click on the SudokuSolver icon, or choose it from the Start Menu. Most of the window is dominated by a nine by nine grid of squares. Type the numbers from your puzzle into the same squares on this grid. You can move between squares using your mouse, or by pressing the TAB key. (Shift-TAB moves the cursor backwards through the squares.) In the top right, there's a box labelled "Steps". If you want to solve the whole puzzle, leave the Steps box blank, or set to zero. However, if you want SudokuSolver to give you only the next number or two towards solving the puzzle, type the number of steps you wish solved into that box. When everything is set as you wish, click the "Solve" button. (Should you make a mistake, either click in the boxes that need corrected, or reset the whole screen by clicking the "Clear" button.) SudokuSolver will provide the solution asked for, or state that the problem is unsolvable. If SudokuSolver needs to guess, it will say so. Since it isn't possible to know if a guess is correct without solving the whole problem, SudokuSolver ignores the Steps setting when it starts guessing. In many cases, a guessed solution will not be unique. SudokuSolver will check for other solutions, and states if multiple solutions are possible. This might be most useful for those creating their own puzzles, to check that their puzzle does have a unique solution. The "Difficulty" line indicates how complex an algorithm was needed to solve the puzzle. In general, the higher the number, the more difficult it will be to solve the puzzle by hand. Puzzles that require guessing are normally harder than those which don't. 5. KNOWN BUGS None reported. 6. TO DO LIST a. Finish the README.txt and LICENSE.txt files. b. Additional algorithms, to solve more Sudoku problems without resorting to guesswork. c. Improved feedback on why a given problem is not solvable. 7. REGISTERING If you use this software, please consider registering. Doing so allows me to continue making improvements to this program, and to write other software that you may also find useful. As a "thank you" for registering, you will get : a. Exclusive download access to programs that solve other Sudoku variants (6 by 6 and 16 by 16 grids, two 9 by 9 grids with a common 3 by 3 area, etc.) b. Early or exclusive access (I haven't decided which, yet) to Sudoku Puzzle Generator that I'm working on next. c. Preferential treatment when requesting new features. d. Optionally, an e-mail when I update the software, so you can download the latest version. To register, please PayPal $5.00 to sudoku@grahamrobinson.com, including your name, e-mail address, and whether or not you wish me to send you e-mails when I update the software. I will confirm receipt by e-mail. If you haven't received confirmation within two weeks, send a follow up e-mail to the same address, and I'll sort out the problem. 8. CONTACTING THE AUTHOR BUGS should be reported to sudoku@grahamrobinson.com with the word "BUGS" at the start of the subject. When reporting bugs it is very helpful if you could include details of the puzzle that caused the problem (see below), what you had the "steps" value set to, and as much detail as you can about what happened. If possible, including screen shots may be helpful as well - press the "Print Screen" key, then paste into any graphics program. FEATURE REQUESTS should be sent to sudoku@grahamrobinson.com with the words "FEATURE REQUEST" at the start of the subject. I'm far more likely to implement features for those who have registered. I cannot promise that any feature requests will be honoured. I am always very interested to see GUESSED PUZZLES which you believe should be solvable through logic. Please send them to sudoku@grahamrobinson.com with "GUESSED PUZZLE" at the start of the subject. Please note that any puzzle where the software flags up "Multiple Solutions Found" CANNOT be solved by logic. I'm also interested in platforms other than Windows XP and Me on which the software works without difficulty, or tips on how to get the software to work on other platforms. I'd appreciate an e-mail to sudoku@grahamrobinson.com with "PLATFORM" at the start of the subject if you have the software running on anything other than XP or Me. Sending Sudoku Puzzles If you need to send me a puzzle, there are a number of options. a. Scan the puzzle from the newspaper or book. The image doesn't have to be great quality - a camera might be good enough - as long as I can read the numbers. b. Fill in the puzzle in the software, then take a screen shot. c. Type in the numbers, using _ for blank squares. So a typical puzzle might look like : _ _ 7 _ 2 _ _ 5 _ 9 _ _ _ 4 _ _ _ 7 _ 6 2 _ _ _ 4 9 _ _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 (From the Metro, 31st Oct 2005.) 9. WARRANTY THIS SOFTWARE IS SUPPLIED "AS IS" WITHOUT ANY WARRANTY, EVEN AN IMPLIED WARRANTY OF FITNESS FOR PURPOSE. SOLUTIONS GENERATED BY THIS SOFTWARE SHOULD BE CHECKED FOR ERRORS BEFORE BEING RELIED ON IN ANY WAY. 10. Sudoku Solver and all associated files are copyright Graham Robinson, 2006. All rights reserved. Appendix. How to solve a Sudoku puzzle every time, by hand. 1. Find the top-most, left-most empty square. 2. Find the lowest number that is legal for that square. i.e. The lowest number which isn't already in the same row, column, or three by three area. 3. If there is a legal number, fill that number in with a pencil, and start again at step 1. 4. If there is no legal number for a square, return to the bottom- lost, right-most square which has been filled in with pencil. 5. Erase that number, and replace with the next higher, legal number. 6. Again, if there isn't such a number, return to step four. 7. Continue from step 1. Try it - if done carefully, it will always work, although it is often easier to solve the puzzle logically! Programmers should recognise this as a depth-first search... Example : _ _ 7 _ 2 _ _ 5 _ Initial Puzzle 9 _ _ _ 4 _ _ _ 7 _ 6 2 _ _ _ 4 9 _ _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 _ 7 _ 2 _ _ 5 _ Fill in first legal number 9 _ _ _ 4 _ _ _ 7 in first square. _ 6 2 _ _ _ 4 9 _ (Steps 1-3) _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 3 7 _ 2 _ _ 5 _ Fill in first legal number 9 _ _ _ 4 _ _ _ 7 in second square _ 6 2 _ _ _ 4 9 _ (Steps 1-3) _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 3 7 6 2 _ _ 5 _ Fill in first legal number 9 _ _ _ 4 _ _ _ 7 in third square _ 6 2 _ _ _ 4 9 _ (Steps 1-3) _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 3 7 6 2 8 _ 5 _ Fill in first legal number 9 _ _ _ 4 _ _ _ 7 in fourth square _ 6 2 _ _ _ 4 9 _ (Steps 1-3) _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 3 7 6 2 8 * 5 _ Problem! 9 _ _ _ 4 _ _ _ 7 Square marked * has no _ 6 2 _ _ _ 4 9 _ legal numbers. So back up. _ _ 3 2 _ 9 6 _ _ (Steps 1-2, 4) 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 3 7 6 2 * _ 5 _ No more legal numbers for 9 _ _ _ 4 _ _ _ 7 fourth square. So back up _ 6 2 _ _ _ 4 9 _ again. In general, lots of _ _ 3 2 _ 9 6 _ _ this sort of backing up is 6 7 _ _ _ _ _ 8 2 needed... _ _ 8 7 _ 4 5 _ _ (Steps 4-6) _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 1 3 7 8 2 _ _ 5 _ Try second legal number in 9 _ _ _ 4 _ _ _ 7 third square... _ 6 2 _ _ _ 4 9 _ (Step 4-5) _ _ 3 2 _ 9 6 _ _ 6 7 _ _ _ _ _ 8 2 _ _ 8 7 _ 4 5 _ _ _ 8 5 _ _ _ 1 3 _ 7 _ _ _ 5 3 _ 6 8 _ _ _ _ 9 _ _ _ 5 SudokuSolver uses this algorithm when it needs to guess. There are a number of more logical algorithms that are attempted first.