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