Solver Strategy

Str8ts discussion with Jeff Widderich and Andrew Stuart.
Stellen Sie hier Fragen an Str8ts-Erfinder Jeff Widderich und Andrew Stuart.

Moderatoren: Syndicate, Andrew

Antworten
Benutzeravatar
Ulrich
Beiträge: 86
Registriert: Montag 24. Mai 2010, 20:05
Wohnort: Region Augsburg München

Solver Strategy

Beitrag von Ulrich » Dienstag 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.
Ulrich
Str8ts addicted

bwang
Beiträge: 1
Registriert: Sonntag 28. November 2010, 00:37

Re: Solver Strategy

Beitrag von bwang » Sonntag 28. November 2010, 00:49

hello,

great tips ulrich.

i have attached a partially solved puzzle. i have used all your tips provided, but without using the "guess and check" method, is there another strategy that i can use to solve? did i miss something? thanks.
Dateianhänge
photo.JPG
photo.JPG (95.53 KiB) 20416 mal betrachtet

Jens
Beiträge: 154
Registriert: Sonntag 25. Juli 2010, 14:55
Wohnort: Puchheim

Re: Solver Strategy

Beitrag von Jens » Montag 29. November 2010, 00:25

Hello bwang and Ulrich,
all digits you filled in are correct. For further steps all rules are given by Ulrich.
1. In line C which has cells C1=3, C2=1, C3=2 and C6=4 there are empty cells C45=56. Row 4 which has cell B4=2 there are empty cells ACD4=(234+(1 or 5)). If you compare both 56 with 234+(15) then you can find only single digit 5 which matches line C and row 4. Therefore you get C4=5 and C5=6.
2. Now row 4 has empty cells AD4=34. Because of D1=4 will be cell D4=3 and A4=4. To find A5=5 and the other cells E5=4, D2=5 and F2=3 should be no problem.
You are welcome, greeting from Jens.
Gruß von Jens

Jens
Beiträge: 154
Registriert: Sonntag 25. Juli 2010, 14:55
Wohnort: Puchheim

BCA (Black Cell Analysis)

Beitrag von Jens » Dienstag 26. Februar 2013, 17:29

Provision
If something is not visible, it’s not easy to handle with. Black cells do hide some digits. To make its content more clear, it’s obvious to find out all digits, which are not candidates in white cells.
Please write those candidates with black color near by right and bottom border of your Str8ts. This digits are in reality hidden in the empty black cells. Then you should write with different color near by left and top border all candidates, which could be hidden in the empty black cells too.

Comparison
Please compare the counts of black digits at right and bottom border. If they differ, you can try to add one missed black digit after each other taking it away from colored digits of the opposite border side, if there were some single colored digits. The aim is, to have equal amounts of each black digit at right and bottom border.

Example
In row A is missed candidate 5. Then a black 5 should be written at right border side.
Candidate 5 is possible only in column 3. A red 5 should be written at top border side. May be, it is the only red 5.
To make the counts of right and bottom digits equal, this red 5 on top line will become a black 5 at bottom line. In result candidate 5 is no longer possible in column 3. Now candidate 5 is no longer needed and can be eliminated from white cells of column 3. It is hidden now in a black cell of column 3.

Conclusion
All candidates, which are not written at the borders, are needed candidates.
The advantage of this method is, now it’s no longer necessary, to count out all digits every time. It’s just one thought about possible candidates of each row and column.
This BCA method is easy and practically.
Gruß von Jens

Antworten