Friday, December 22, 2006

Solution methods

Analysis
The two main approaches to analysis are "candidate elimination"and "what-if". In "candidate elimination", progress is made by successively eliminating candidate numerals from cells to leave one choice. After each answer has been achieved, another scan may be performed—usually checking to see the effect of the contingencies. In general, if entering a particular numeral prevents completion of the other necessary placements, then the numeral in question can be eliminated as a candidate. One method works by identifying "matched cell groups". For instance, if precisely two cells within a scope (a particular row, column, or region) contain the same two candidate numerals (p,q), or if precisely three cells within a scope contain the same three candidate numerals (p,q,r), these cells are said to be matched. The placement of those candidate numerals anywhere else within that same scope would make a solution impossible; therefore, those candidate numerals can be deleted from all other cells in the scope.
In the "what-if" approach (also called "guess-and-check", "bifurcation", "backtracking" and "Ariadne's thread"), a cell with two candidate numerals is selected, and a guess is made. The steps are repeated unless a duplication is found or a cell is left without a possible candidate, in which case the alternative candidate must be the solution. For each cell's candidate, the question is posed: 'will entering a particular numeral prevent completion of the other placements of that numeral?' If the answer is 'yes', then that candidate can be eliminated. The what-if approach requires a pencil and eraser or a good layout memory.
There are three kind of conflicts, which can appear during puzzle solving:

  1. basic conflicts - there are only N-1 different candidates in N cell in the area
  2. fish conflicts - when eliminating number from N rows/columns, it will disappear also from N+1 columns/rows.

  3. unique conflicts - this pattern means multiple solutions, all numbers in the pattern exist exactly two times in every area, row and column. If there are only one candidate in the cell, any virtual candidate can be added.

Encountering any of those would indicate that the puzzle is not uniquely solvable. So, if you encounter them as a consequence of "what-if", you use your eraser and go back to try untried alternatives.

No comments: