Sudoku Helper

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Celebrity Eclipse Day 1 Puzzle (3/25/2012)

Program can show valid possibilities

Problem Description

We 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 & Techniques

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

Sudoku requires completing a 9x9 grid of cells with the digits 1 through 9 in such a way that all 9 values are included in each column, row, and 3x3 block. Some initial values are provided as clues.

A few sample puzzles are included with the download and you can create additional puzzles by entering initial values and saving them. The "Hint" checkbox will display numbers which may be placed in each cell without duplicating a number in that column, row, or block. These are the values which may be placed without violating the  rules described below.

There are also buttons to  fill one or all cells where there is only a single choice for the value.

There are two tests applied to determine if there is only a single choice : 

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. 

bulletThe SaveCaseBtn calls SaveCase procedure passing a user selected filename.  Savecase writes a 3 or 4 character record for each non-zero cell value consisting of: a one character value for column, row, and value and an a 4th character asterisk, *,   if the value is one of the original case definition values.
bulletLoadCaseBtnClick calls LoadCase to load a previously saved case.
bulletCreateBtnClick opens a dialog to solicit whether the user want to modify the existing case definition or start a new empty case.  Global TMode type  field Mode is set to value CreateCase which tells key press entries to allow case definition values to be changed.  Clicking any other button key will revert Mode to Play
bulletStringgrid1DrawCell draws cell values in Maroon text for original definition values and black otherwise.  Empty cells have the valid possible values for that cell displayed in blue text at the top of the cell area, etc. 
bulletProcedure ReformatMemo contained in out DFFUtils library unit is called as an easy way to adjust line lengths in the introduction memo, Memo2.  Recompilation will require a one time download of our DFF Library zip file.
bulletThe IsValidKey function is called for user keyed entries and prohibits a move that leaves a cell with no available values.   The program search  currently allows this move which is valid but clearly incorrect. 

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:

  1. When "Hints", the valid numbers for an empty cell, are displayed and require two lines, the last possible value was no displayed.  It now is.
  2. There was no default extension in the file save dialog, so if the user did not enter an extension when saving a puzzle, it was save that way (with no extension).  Now if the extension is omitted, the file is save with a .txt extension.

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:

  1. Start with a puzzle known to have a unique solution.
  2. For each value until Step 3 is satisfied, select a pre-filled cell with value, N. 
  3. Replace that cell with all values 1 through 9 except N and for each replacement, see if the puzzle is solvable.  If it is not solvable with any of the other values, the cell  may safely be cleared  to produce a new puzzle with one less prefilled cell and  which is guaranteed to have have only one solution, (the one containing the value that was removed).   

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.

  1. User moves which filled a cell which had only a single valid value could not be undone.
  2. Program moves during the "Trial & Error Search" could not be undone.

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.      

        

 Running/Exploring the Program 

bulletDownload  executable
bulletDownload source  (Note: the DFFUtils unit which this program uses, resides in our library zip file of commonly used units.  Library file DFFVLIB13 or later is required to recompile this program )
bulletDownload current library file (DFFLibV15)

 

bulletDownload Lazarus Sudoku Source
bulletDownload current DFF Lazarus Library Source(DFFLazLib01)

 

Suggestions for Further Explorations

May 2012: Done! Adding a Depth-First search would be relatively easy to do and allow complete program solution of any solvable puzzle.   On the other hand, the values in a complete solution are not useful, I already know how to implement the "feature", and the existing "manual" implementation might help users better understand the procedure.. 
.When the user makes a move which is valid but clearly incorrect, i.e. leaves a cell with no possible values, user should be warned or the move prohibited. .  
July 2013: Investigate efficient methods to check uniqueness of potential solutions for generated puzzles with fewer than 30 given clue values.  (At least partially implemented with Version 4.0)
   

 

Original:  April 05, 2012

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.