[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionWe are looking to develop a Sudoko helper/solver program to assist in solving those puzzles which appear in many newspapers, magazines, and online websites these days. Background & TechniquesThis version of a Sudoku solver was written while on a cruise with family
when no
online or downloadable solver versions were available. The cruise line handed
out puzzles daily and we are a family of puzzle solvers. So on sea days, while
they worked on solving the puzzles, I worked on solving the puzzle of how to
solve the puzzles (i.e. this program). The family generally finished their
problems, I didn't complete mine until we got home but decided to clean it up an
post it anyway. 1: The "No Duplicates" rule eliminates numbers which already exist in the cell's column, row, or block. 2: The "Completeness" rule which requires that every value occur in
every column, row, and block. If one of the values which can be placed in a
cell cannot be placed in any other cell without violating rule 1, then that
must be the value placed in this cell. Applying these rules repeatedly will solve most, but not all, puzzles that you run across. The next solver version , not yet posted, uses more rules and, if necessary, "trial and error" solving. This is much easier for computers than for humans to accomplish since it can try thousands of paths per second without taking a wrong turn. One of the included samples, rated as "Evil" difficulty at www.websoduko.com requires a manual version of "Trial and Error". Making a correct guess in the correct cell and clicking the "Fill all single possibilities" button will usually find a solution. If not, but the board looks OK, systemically pick another cell with only two possibilities select those try the "Fill all" button again. If the board is not valid, (a row, column, or block cannot be completed), l "Undo" the last set of move or use the "Restart Puzzle" button and try the next guess. This is a manual way to implement what we computer guys call "Depth First Search with Backtracking" but normal people would call "Trial & Error". Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now. Programmer's Notes:I've had several requests or a Sudoku solver over the years, but each time my response was that the world had enough solvers already but, as described above, a personal need developed and provided the excuse to write one. I think that this program is a pretty good one but I haven't looked at any others to compare. As usual, the first step in solving a programming problem was to develop a data model to describe it. The model that evolved has a record for each cell of a 9x9 array. The record, TRec, contains the an integer field Value assigned to the cell with 0 representing the empty cell. TRec also has 9 entry Boolean "Possibles" array with a True value for entry i indicating i is a possible value for that empty cell. Field NbrPossibles in TRec contains a count of the number of value in Possibles array which are True. Procedure FillPossibles has the task of rebuilding all of the Possibles arrays after each change to a Value field. It does this by setting all of the Possibles values to True and then setting Possibles values to False for all of the cell values in the column, row, and block to which this cell belongs.. Those that remain True after this procedure, are the values that can be validly placed in this cell. A Stringgrid1Keypress event exit detects user key clicks and, if valid, saves the old value in an UndoPath array, sets the entered value in the selected cell, and calls FillPossibles to update those arrays. Clicking the UndoBtn button will reset the last entry from the Undo path list after saving the existing value in a RedoPath array (for use when the RedoBtn button is clicked. Each use of the Undo or Redo button will remove the latest value from the appropriate array so multiple clicks will work their way back or forward through a succession of moves. The FillOneBtn and FillAllBtn buttons both call the FillBtnClick on-click procedure. The procedure use the Sender field to set a flag to stop after the first move made if the call was from FillOneBtn. The search for a value to insert starts by checking the NbrPossibles field for cells with only one possible value. If that search fails, a second search is made applying the "Completeness" rule previously described to all columns, rows, and blocks again stopping when a change is made if FillOneBtn was the caller. If the call was from FillAllBtn, the loop repeats until a complete pass is made with no changes made. Everything else is pretty much support.
Addendum April 8, 2012: It only took one day (and an hour or so playing with new puzzles) to find a couple of small bugs that have been fixed today with Version 1.2. Problems corrected are:
April 11, 2012: Version 1.3 corrects a problem with the Undo button trying, under some conditions, to Undo more moves than were made resulting in various undesirable outcomes. April 13, 2012: Sudoku 2.0 posted today, adds the "Trail and Error" solver discussed. earlier. May 19, 2012: Version 3.0 includes my initial version of a random puzzle generator. It is moderately successful at generating puzzles with down to 28 or 27 given values which generally, but not necessarily always, represents medium difficulty puzzles. Fewer given values (more empty cells) rapidly increases the number of potential solutions which must be checked to ensure that that there is exactly one. Uniqueness of the solution is one of the mandatory, or at least desirable, properties of a Sudoku puzzle. Those who have dedicated lots of time to the problem have concluded that there are about 6x1021 possible boards (but only 5 x 109 if eliminate counting rotations and permutations). This would represent the number of solutions for an empty board. I plan to investigate into the statistics of solutions and to do some tuning of the "solution checker" portion of the process which looks for duplicate solutions of potential puzzles, hoping not to find one. Apparently there are some patterns which must be avoided as puzzles are being built because they guarantee multiple solutions. Sounds like good fun! January 15, 2013: Here is Sudoku Version 3.1 which fixes an annoying display problem created in a number of programs after I used the Windows "Increase text size" option to make it easier on these old eyes. Some controls with text increase their size to compensate, others do not. I'm correcting the displays as I run across them, including this one. I also added the missing "Congratulations" display when the user completed a puzzle by clicking on the last open cell. July 10, 2013: I recently ran across this paper online which describes an improved method for identifying uniqueness of generated puzzles: http://zhangroup.aporc.org/images/files/Paper_3485.pdf. I implemented a version of their "digging holes" algorithm in Sudoku Version 4.0 posted today. The idea is to start with a known good puzzle and make one with one less pre-filled cell by:
I have not optimized my original inefficient FillPossibles and CountSolutions functions but implementing the above algorithm allows creation of puzzles with as few as 23 filled cells in about 10 minutes (22 pre-filled took about and hour). My previous practical lower limit was around 28 filled cells. Puzzles with a few as 17 given values exist and that has been proven to be the minimum number that will have a unique solution. A rewrite of those two functions would probably reduce the search times by an order of magnitude but is left for another day. Version 4 also corrects a couple of error with the "Undo"/"Redo" operations.
Undo/Redo should now work for all types of user and program moves. July 17, 2013: One more incremental improvement before we move on. Version 4.1 returns to Step 2 looking for an N-1 solution rather than Step 1 after Step 3 is satisfied. This allow at least two more cells to be emptied in a few minutes (21 filled instead of 23). Two solutions with 20 filled have been found, one in 8 minutes of run time and one in 4 hours! Not encouraging for future improvements.
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |