|Help for Quick solving using Patterns
All possible patterns for the digits 1-9 in given puzzle state can be readily generated. Such patterns have already been put to good use above in the POM analysis,
and solving by patterns in the contradiction set. The nice thing about patterns is that they already (by definition) conform to the sudoku constraints.
It turns out that these patterns (only one of which is the correct one for each digit) can be used to quickly solve a puzzle using the following process:
- Generate all patterns for each number in separate arrays and order them by increasing size.
- Take the first pattern for first array (18 digit string, 2 digits for each address) and add each address to a new array .
- Take the first pattern for next array. If none of the 9 addresses for this coincide with those for the first pattern, then add these to the new array of addresses.
- If one of the addresses for second array coincides with one of the addresses for the first, then discard it and try second pattern for second array, and so on until one fits.
- In this way, the process keeps testing patterns to see if they fit, a bit like assembling a jig-saw puzzle.
- Eventually the array has 81 2-digit addresses representing the final solution (if a valid puzzle).
- The process continues until all combinations are tested, with the result that there will be zero, one or many solutions. If there is one solution (ie a valid puzzle) then this is displayed.
The following is the diagramatic view of the logic. If pattern 'fits' means taking each of the 9 addresses of the candidate pattern one at a time and seeing if the
address is occupied by the existing patterns at that point in the process. If an address is occupied (ie no fit), then the pattern is discarded.
The method doesn't take into account how 'hard' the puzzle is. The more patterns a puzzle state has the longer it takes. It would also be quicker if by chance the
correct patterns occured early in the list. For example, the 'golden nugget' after exocet elimination took about 4 seconds to give the first output, while the 'easter
monster', following SK loop and naked triplet eliminations, had fewer patterns and took less than 1 second and produced the second output. The Top95, #7, which has no given for
number 9, has 2301 patterns for 9, so despite being a much simpler puzzle than GN, it almost takes as long.
|Golden Nugget: Total number of patterns:
Final answer =
|Easter Monster: Total number of patterns:|
Final answer =