Solver Strategy
Posted: Tuesday 3. August 2010, 13:44
General concept:
Initially each of the empty white cells may contain the figures 1 to 9. The solver strategies allow to cancel some digits from the list of candidates for certain cells. A solution is found, if there is only one remaining cell candidate. If no candidate remains, the riddle has no solution or you made a mistake.
My solver uses the following sequence: Apply a strategy starting with the first one, check if there is at least one solution. If yes, update the riddle with all solutions and start again. If no, check if the number of candidates has been reduced. If yes, repeat the same strategy. If no, go to the next strategy.
These are the solver strategies presently implemented in my solver:
Row / Column Rule:
Figures already present in a row or column (in white or black cells) can be excluded from the cell candidates of that row or column.
Compartment Check:
The heart of the game! Based on the known figures and the cell candidates of a straight the overall range of possible figures for this straight is determined. All figures outside of this range can be excluded from the cell candidates of the straight.
In case the remaining range of a straight is shorter than twice its length, there are some figures which must be part of the straight. Example: a straight of 3 cells with a range from 5 to 8 must contain the 6 and 7. Such "must figures" can be excluded from all cells outside of the straight within its row or column.
Hidden Single:
If a must-figure appears only once in a straight, this is the solution of the cell.
Naked Pairs:
If two cells of a row or column contain the same two figures, these can be excluded from all other cells of this row or column.
Stranded figures:
If a cell candidate can not build a valid straight together with the available candidates of the other cells, it is called "stranded" and can be excluded.
Example: Straight of 3 cells, candidates are 2457-456-4567. The 2 is stranded, because there is no 3 available to connect it to the other candidates of the straight.
Naked triple:
Same logic as for pairs, with three cells and three figures: only three different figures appear in three cells. These figures can be excluded from all other cells of the row or column.
Example: Straight with 5 cells: 12345-34-35-345-3456: The cells 34-35-345 build a triple, therefore 3, 4 and 5 can be excluded from all cells of the row or column. The remaining cell candidates are 12-34-35-345-6, the 6 is a solution.
Possible further improvement:
1) Naked quadruples (like naked pairs and triples)
2) Hidden pairs, triples and quadruples: the "hidden"-strategies can only be applied to must-figures.
3) Interaction between straights: a short straight shall not cut a long one in the same row or column.
Some statistics
After evaluation of about 500 Str8ts (25000 figures to be found) concerning the applied strategies, here is the result:
Row / Column Rule: 4600 = 18%
Compartment Check: 16500 = 66%
Hidden Singles: 2500 = 10%
Naked Pairs: 50 = 0,2%
Stranded digits: 1300 = 5%
Naked Triples: 50 = 0,2%
Trial-and-error:
Finally every riddle which has a unique solution can be solved by trial-and-error, either afetr application of logics or strating from the beginning.
A simple backtracking will do this job. A trial-and-error approach after having used the logics is necessary for some of the Str8ts in the "Extremes"-category. It is never needed to solve the "normal" riddles.
If you don't use a solver program, the trial-and-error means, to guess a figure, continue with logics and find out, if you achieve a solution or a conflict. In case of a conflict you can exclude your guessed figure and continue with a new guess. In case of a solution you are ready, if you are sure that the riddle has a unique solution (this is true for all Str8ts on the Str8ts-sites). If you are not sure, you must verify that all further possible guesses end with a conflict.
Because there exist more logic strategies than described above, the trial-and-error approach (or "guessing") is not an absolute category. With more sophisticated strategies some situations which today are considered to need "guessing" might become logically solvable. Even the trial-and-error is a kind of logic, however not a straight one.
Initially each of the empty white cells may contain the figures 1 to 9. The solver strategies allow to cancel some digits from the list of candidates for certain cells. A solution is found, if there is only one remaining cell candidate. If no candidate remains, the riddle has no solution or you made a mistake.
My solver uses the following sequence: Apply a strategy starting with the first one, check if there is at least one solution. If yes, update the riddle with all solutions and start again. If no, check if the number of candidates has been reduced. If yes, repeat the same strategy. If no, go to the next strategy.
These are the solver strategies presently implemented in my solver:
Row / Column Rule:
Figures already present in a row or column (in white or black cells) can be excluded from the cell candidates of that row or column.
Compartment Check:
The heart of the game! Based on the known figures and the cell candidates of a straight the overall range of possible figures for this straight is determined. All figures outside of this range can be excluded from the cell candidates of the straight.
In case the remaining range of a straight is shorter than twice its length, there are some figures which must be part of the straight. Example: a straight of 3 cells with a range from 5 to 8 must contain the 6 and 7. Such "must figures" can be excluded from all cells outside of the straight within its row or column.
Hidden Single:
If a must-figure appears only once in a straight, this is the solution of the cell.
Naked Pairs:
If two cells of a row or column contain the same two figures, these can be excluded from all other cells of this row or column.
Stranded figures:
If a cell candidate can not build a valid straight together with the available candidates of the other cells, it is called "stranded" and can be excluded.
Example: Straight of 3 cells, candidates are 2457-456-4567. The 2 is stranded, because there is no 3 available to connect it to the other candidates of the straight.
Naked triple:
Same logic as for pairs, with three cells and three figures: only three different figures appear in three cells. These figures can be excluded from all other cells of the row or column.
Example: Straight with 5 cells: 12345-34-35-345-3456: The cells 34-35-345 build a triple, therefore 3, 4 and 5 can be excluded from all cells of the row or column. The remaining cell candidates are 12-34-35-345-6, the 6 is a solution.
Possible further improvement:
1) Naked quadruples (like naked pairs and triples)
2) Hidden pairs, triples and quadruples: the "hidden"-strategies can only be applied to must-figures.
3) Interaction between straights: a short straight shall not cut a long one in the same row or column.
Some statistics
After evaluation of about 500 Str8ts (25000 figures to be found) concerning the applied strategies, here is the result:
Row / Column Rule: 4600 = 18%
Compartment Check: 16500 = 66%
Hidden Singles: 2500 = 10%
Naked Pairs: 50 = 0,2%
Stranded digits: 1300 = 5%
Naked Triples: 50 = 0,2%
Trial-and-error:
Finally every riddle which has a unique solution can be solved by trial-and-error, either afetr application of logics or strating from the beginning.
A simple backtracking will do this job. A trial-and-error approach after having used the logics is necessary for some of the Str8ts in the "Extremes"-category. It is never needed to solve the "normal" riddles.
If you don't use a solver program, the trial-and-error means, to guess a figure, continue with logics and find out, if you achieve a solution or a conflict. In case of a conflict you can exclude your guessed figure and continue with a new guess. In case of a solution you are ready, if you are sure that the riddle has a unique solution (this is true for all Str8ts on the Str8ts-sites). If you are not sure, you must verify that all further possible guesses end with a conflict.
Because there exist more logic strategies than described above, the trial-and-error approach (or "guessing") is not an absolute category. With more sophisticated strategies some situations which today are considered to need "guessing" might become logically solvable. Even the trial-and-error is a kind of logic, however not a straight one.