| SuDoku involves filling out a 3x3
number grid such that each row and
column contains all of the digits 1-9 and each 3x3 sub-grid also
contains all of the digits 1-9. Check out my SuDoku applet which solves the SuDoku puzzle published every morning in the Times. No cheating now! Only use this applet if you have been driven completely mental by it trying to solve it on a piece of paper. The program comprises a primary (initialization) phase which simply fills in those sites with only a single possible value or values with only a single possible site (it keeps iterating this process until it can update no more sites) and then a secondary phase which considers sites with only 2 possible values. It looks at all possible combinations very efficiently using a rather neat trick (though I say so myself!) of creating all k-bit bit patterns (where k is the number of 2 possibility sites) and runs a masking bit over each pattern to generate a single combination. A consistency test is then applied where a grid is consistent if no sites have zero possible values. The primary phase is then re-applied to all consistent grids. This sequence is embedded into a recursive function that can be called to any level of nesting (and the recursion simply unwound when a solution is found). I have called the function to search for a solution using a 2-level deep search initially. In practice, this solves most grids instantaneously (even 'fiendish' puzzles). However, if the function returns with no solution found, the function is called again using a 4-level deep search. The applet also incorporates a SuDoku generator which can generate SuDoku grids with guaranteed unique solutions. Simply select the level of puzzle you want (Easy, Moderate, Difficult or Fiendish) and up pops the grid at the correct level of difficulty. If you want the solution, just select 'Play' and the solution will appear. If you want to use this applet to generate puzzles for your publication, then please make sure the source is acknowledged. If you have any comments or questions or want a copy of the code, please feel free to email me. |