rating. For instance, if a puzzle can be solved using X-wing, we know its rating is 3.2 and we can retain or reject it depending on
what we are looking for. The trouble is that, as we enter the region of higher ratings, the algorithms required become ever more
complicated to code and require ever more time to execute. However, many of these algorithms depend on testing for contradictions:
a candidate value is asserted to be the true value and a more or less complicated chain of logic determines whether this
assumption is true or not, i.e. whether the candidate value can be retained or is certainly wrong. In the context of the Patterns Game,
however, the details of these chains are of no interest, we simply want to know whether a candidate value is valid or not.
But, in fact, a contradiction is equivalent to there being zero solutions to the puzzle, and that can be determined more simply by other means.
The easiest to implement is simply to use a solver to count the number of solutions, but counting up to zero turns out to be, typically,
dreadfully slow. Another way is to make a series of logical tests on the candidate puzzle; for instance, if there exists a cell containing
exactly three candidate values and each of these values occur only once in the corresponding r/c or b, then
there is a clash and there are zero solutions. An algorithm for removing invalid candidate values thus looks like this:
- Code: Select all
1) Solve the puzzle as far as possible with simple methods.
2) For each unsolved cell
For each candidate remaining
Set the candidate value to be the solution value (removing the other candidates in the cell and making the
other basic elimininations)
a) Solve this version of the puzzle further using singles, once, (fast) OR
b) Solve this version of the puzzle as far as possible using simple methods (slow)
Pass the incomplete puzzle to a procedure (not a solver) that checks whether there are definitely zero
solutions
If there are zero solutions, remove the candidate definitively from the partially solved puzzle
Otherwise restore the candidate and take the next one
3) Resume solving the puzzle, now with fewer candidate values, using simple methods.
4) Iterate until completion, or until no further progress.
It turns out that the fast version of this method solves most puzzles up to about SE=8.5 and beyond, and the slow version
up to an SE value of about 9.9. That's quite useful as a filter.
Regards,
Mike Metcalf
