Web based solver

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

Moderatoren: Syndicate, Andrew

Leren
Beiträge: 5
Registriert: Dienstag 30. Januar 2018, 20:37

Re: Web based solver

Beitrag von Leren » Montag 5. Februar 2018, 23:30

Hi Robo,

Thanks for the heads up on the pop up boxes, I missed that.

Still, the Canis Major eliminations previously referred to just say that they don't fit into any valid combo of the relevant column. Whilst this is no doubt true, it sounds suspiciously like Trial and Error to me: assume the elimination is True and eventually come to a contradiction in the column (at least one cell has no candidates left).

I come from a Sudoku background, where T&E is not regarded very highly at all. My alternative constructive proofs all come from Slow Thinker's slideshow on solving techniques, or from discussions on Andrew's Extreme forum over the years, so they would be regarded as Standard Toolbox CE's.

morl
Beiträge: 1
Registriert: Montag 29. Januar 2018, 14:52

Re: Web based solver

Beitrag von morl » Dienstag 6. Februar 2018, 22:03

Hi robo,

the solver might be faster if it starts chains with digits in black cells (after hi/lo decisions). Perhaps you could check that. Thanks in advance

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Web based solver

Beitrag von Robo » Mittwoch 7. Februar 2018, 19:26

@Leren: I understand this. In this regard my solver is certainly not yet at the level of yours. I have quite a few algorithms still on my todo list. But as my interest is mainly in the software engineering aspects, I have given higher priority to other features of the solver during the last weeks. More will come :-)
@morl: Thanks, that's an interesting idea that I will certainly try and report back here. It may take some time though, as I still have to finish a larger feature (optimizing the chains) first (see above ;-))

C_L
Beiträge: 6
Registriert: Donnerstag 14. Januar 2016, 23:36

Re: Web based solver

Beitrag von C_L » Sonntag 11. Februar 2018, 17:21

Hi Robo,


I was little short of time last week. So I postponed the detailed answer to your solver discussion to this weekend.
Here some thoughts regarding putting up a solver based on Dancing Links.


0) References

Check-out English Wikipedia for ‘Dancing Links’, ‘Algorithm X’, ‘Exact Cover Problem’, and Sudoku solvers. Most importantly, see the Sudoku Dancing Links paper on D.E. Knuths page. There has also been a Str8ts paper which I sadly couldn’t find any more. Maybe Ben who originally posted can provide you the URL.

Further, check out an existing dancing links implementation on github.


1) Solution Representation

Potential parts of the solution are represented as triples (row, col, num), i.e. elements auf a cube [1 ; 9] x [1 ; 9] x [1 ; 9]. The solution(s) are a subset of all elements of the cube which is subject of retrieval.


2) Board Representation / Initial Clues

Initial clues are handled by selecting the respective triple for the given clue; black cells by removing all corresponding triples.


3) Rules of the Game / Problem Representation

Not every set of triples is a valid solution; solutions have to comply with the rules of the game. One is ‘every cell has to be filled exactly once’, a second ‘there can be only one number X in row Y at maximum’, a third is ‘there cannot be a 5 in a length-4 compartment if there is already a 1’ (A1234), … . The last type of rule depends on the geometry. Note that – in opposite to Sudoku – some rules are mandatory (e.g. the fill rule), some are optional (the 1-5 rule).

The problem of a given Str8ts puzzle is represented as matrix the rows of which are the partial solution candidates and the columns are the rules. An element of the matrix is marked (i.e. value 1) if the selection of a triple would trigger a rule. E.g. the fill-(1; 1; X) rule of all 9 triples would have a mark in the respective column. Or (1; 4; 1) … (1; 4; 5) in the 1-5 rule column. All other elements are zero.

As result, selecting two columns with non-zero entry in the same column as part of the solution would lead a contradiction.


4) Recursive Solution Procedure

The solution process is recursive: a) select any mandatory rule, typically the one with the least candidate triples; b) test all possible candidates; c) check the rules a candidate in b) triggers; d) remove all triples that contradict these rules as well as the columns of the rules; e) repeat recursively with reduced matrix until a solution or a dead end is found.
This is just another form of backtracking although potentially more efficient than starting to fill A1, then A2, … . This kind of approach might be good to check puzzles, but not to solve them as a human would.


5) Dancing Links

Knuth discovered that most work is done selecting a sub-matrix and undoing that selection. An efficient means to do both is via double-linked lists. See Dancing Links. The solving process can as well be done – less efficient – with ordinary full matrices.

So far this is – as stated - just an ordinary backtracking solver, which I assume you are only partially interested in. It does just trial-and-error. But the backtracking solver can be an extremely efficient back-end for a cleverer solver: applying strategies as a human would and potentially also faster than pure backtracking.


6) Solving Strategies in Context of Dancing Links

Several solving strategies have been developed in this forum over the years. In my opinion, none have been proven constructively but all by contradiction. ‘If 5 and 6 would be somewhere different than cell X and Y, this would result an error later on’ (naked double XY56). Similar considerations apply for all other strategies (see UR below).

A way to apply such rules in the context of Dancing Links can be as follows: a) select a suitable set of mandatory rules (here fill X and Y); b) select all triples that are related to these rules (here the candidates in those cells) => sub-matrix; c) do backtracking on the reduced matrix to find all solutions; d) draw potential conclusions from union and intersection of all retrieved partial solutions (here ‘at most on 5’ and ‘at most one 6’ rules triggered); e) select the generally valid rows and remove the rows that would contradict the triggered rules (here the 5s and 6s in all other cells). If there is no naked double, the rules are only triggered for parts of the solutions and the intersection is thus empty, e.g. nothing to conclude. The list here of things do derive might be incomplete (e.g. accounting rules not triggered at all, solutions in all cases).

Most (all?) known strategies can be derived in this was. The goal in all cases is to eliminate candidates (triples) and to ultimately have trivial rules with only one candidate, i.e. solved cells (triples added to solution).


7) Types of Strategies

There are to my opinion 3 types of strategies, one for each triple index: a) row strategies (basic St8ts strategies); b) corresponding column strategies; c) number strategies (i.e. wings and Settis which are by the way the same anyway…). All strategies can be applied to a full row (all others incl. CE), compartment (range, required digit, etc.), or any sub-set of cells ((naked) double / triple, …).

Note that in this triple representation a X-wing is the analog of a naked double, the same is true for higher wings. Further it is important to have the possibility to move a rule from optional to mandatory (required digit, singles, Settis / wings). All strategies are just a suitable selection of a sub-matrix and correct application of the drawn conclusions to the remaining matrix.


8) Incremental Solving

The overall strategy has to be to incrementally draw conclusions from a sub-set of the puzzle. The simplest approach is to a) process all individual rows; b) all individual columns; c) all digits (wings) separately; d) repeat previous steps; e) do full backtracking if no changes from a full iteration.
A more human like would first test all combinations of 2 cells (naked double), then the compartment, and as last resort the full row (CE).


9) Performance

The underlying Dancing Links structure is extremely efficient. If I remember correctly, sub-second performance has been reported for extremes back then (backtracking). Backtracking on rows is not too expensive: E.g. a row with 2 length-4 compartments in an entirely empty puzzle has 3 (where is the 5) x 2 (hi/low) x 4! x 4! = 3456 solutions to be retrieved. I assume this is sufficiently fast.

Guess the key is to find a way to avoid doing the expensive tests and to rather repeat the cheap ones. A further approach might be to only redo those tests that are affected by matrix changes since the last run of the same test.

In general I assume there’s also large potential for multi-threading to speed-up (e.g. C++ promise/futures working on replicated matrices). But I assume you are rather interested in client-side web technology in which I have not much expertise.


10) Advanced Strategies

In the proposed approach you can also aim to go for more advanced strategies.

For instance, you can do Y-wings (and head-chains) like this: a) iterate all potential candidates in a given cell; b) do all trivial eliminations; c) check for conclusions (union / intersection) as done for all strategies.
URs are a second example: a) select a given candidate in a cell; b) check if removal of the cell diagonalizes the matrix (i.e. two or more independent sub-matrixes after re-ordering of rows and columns); c) solve the small sub-matrix; d) remove the original candidate under test if the sub-matrix has multiple solutions.

For most cases, implementing a given strategy is just the suitable selection of the sub-set of rows and columns. I.e. providing the solver additional strategies is simply to add selection methods.


11) Metrics

I guess there are two metrics needed on top of the basic solver for an advanced solver: a) estimation of expected benefit (removed entries) per run-time for a given strategy; b) rating of complexity of strategies. With both strategies available you can design a solving sequence that might be most efficient or simplest in terms of human rating. If you are trendy enough, you have to use Deep Neuronal Networks ;-)


Hope my monologue was not too boring and potentially somehow helpful for your efforts. Let me know if my explanations are poor or in case you have questions.

Best,
CL

Robo
Beiträge: 22
Registriert: Montag 1. Januar 2018, 11:47

Re: Web based solver

Beitrag von Robo » Dienstag 13. Februar 2018, 22:08

Hi CL,

Thanks a lot, that's a lot of material that will take some time to digest.

After a brief scan of Knuth's work, I believe that
  • Since I really like the visualization of the real-time growth of the solution-tree, I need breadth-first search, while Knuth's Algorithm X is depth-first.
  • Knuth's algorithm has advantages only under memory constraints. For the Str8ts problem and today's computing environment, I have no problems in keeping all states along the solution tree, and even multiple trees to find the best one.
But maybe I am overlooking something. A soon as I find some time I will look deeper into it.

Again, thank you for this great compilation.

robo

C_L
Beiträge: 6
Registriert: Donnerstag 14. Januar 2016, 23:36

Re: Web based solver

Beitrag von C_L » Sonntag 25. Februar 2018, 11:29

1) To my understanding, there is no breadth-first in Algorithm-X as the major information is only in the leaves of the tree (solution / no solution). The internal nodes just code the way to / the parts of the solution. Yet, you lack knowledge on their relevance as long as you do not know the leaves.

2) Concerning mMemory, you are right in one respect. You can work with a single copy of the matrix instead of having to put multiple copies on the stack with recursive calls. This is not a Problem on modern CPUs. Yet, there is a greater advantage: recursion requires deep copies of a potentially large matrix (roughly proportional to matrix size). This might be relatively expensive. With Dancing Links, entering a recursive function call requires just removal of a few links; returning requires restoration of these few links only.

3) What's more interesting to me than Dancing Links is the representation of the Str8ts pProblem. Links is about computational efficiency only. The matrix however represents the problem extremely compact and in a straight forward way. All possible choices and all implications of a certain decision are stored as simple binary flag. This eases implementation of strategies to my understanding a lot! Maybe Leren, Klaus, etc. can tell you what is their representation of partial solutions, required digits, etc. is...

Klaus
Beiträge: 21
Registriert: Freitag 15. Januar 2016, 11:57

Re: Web based solver

Beitrag von Klaus » Mittwoch 28. Februar 2018, 11:26

Hi C_L,

not quite sure if i really understood what you are describing in your posts above. I never did any theoretical work on solution representation, searches, trees and so on. Did it all on my own from scratch. (by the way, do things like mMemory or pProblem have a special meaning or is it just a nervous finger?).

The triple alone holds very little information. It doesnt know to which compartments it belongs, whether the candidate is a must in its row/column and so on. These are essential things if you want a powerful and efficient Str8ts-Solver. Can you formulate this as rules for the triple (the ones you described are very simple and basic)? How would e.g. a compartment-interaction-check be done, Setti, ...?

My represention of the puzzle is very human-like, just as you see it. A structure with 9 rows and columns, each of them has a set of compartments. Then a set of cells, every cell has a unique position in exactly one row, column, row-compartment and column-compartment. In addition every cell and compartment has a set of candidates. Then a bunch of checks, each of them trying to find candidates, which contradicte one of the rules known to me. if so, the candidate is removed and the whole things starts again. Thats it, all very simple.

Best wishes,
Klaus

Antworten