denis_berthier wrote:I had already coded all the specific rules I could find on the web. But as I said previously, most of them are subsumed by whips - so that coding them is rather frustrating: they can make the resolution paths shorter, but they don't allow to solve more puzzles.
Recently, I've coded a rule for automatically eliminating incomplete loops - which makes my manual solution paths above obsolete.
Since then, I can solve ALL the puzzles I've found on the 2 main websites discussed above: Krazydad and puzzle-loop.com
So, you have now Slitherlink solver, right? If so, congratulations to you! This puzzle, to my mind, is rather difficult for "solver coding". Is your CRT sufficient to build Slitherlink solver w/o any empirical rules?
I think I can answer yes, but only after a few precisions:
Firstly, as suggested by the title of my last book ("Pattern-Based Constraint Satisfaction ..."), I'm not interested in solving puzzles by any means (e.g. by DFS or BFS). I'm only interested in solving them in a pattern-based (or rule-based) purely logical way. I'm also interested in finding the simplest resolution path (in the sense that it uses the simplest possible rules - e.g. the shortest chains).
As a result, speed of resolution is not my main purpose. (You can consider that my problem is exponentially more complex than just finding a solution by any means.)
- for any type of logic puzzle that can be expressed as a CSP, puzzle instances can be classified according to the level of T&E they require when only Singles and elementary constraints are used;
- puzzles in T&E(0) can be solved by Singles and elementary constraints propagation;
- puzzles in T&E(1) can be solved by Braids (and most of the time by whips, a much simpler type of chain pattern);
- puzzles in T&E(2) can be solved by B-braids, a kind of extended braids admitting braids as their right-linking elements.
These results are valid for any CSP.
What I've shown for Sudoku is:
- "almost all" the 9x9 minimal puzzles are in T&E(0) or T&E(1) and can therefore be solved by braids;
- Blue's calculations suggest that about only 1/30,000,000 minimal Sudoku 9x9 puzzles are not in T&E(0 or 1);
- my calculations on the hardest list show that they are all solvable by B7-braids, which considerably reinforces my old T&E(2) conjecture that all the puzzles are in T&E(0 or 1 or 2);
- however, for larger sized Sudoku puzzles, the proportion in T&E(0 or 1) decreases very fast with grid size.
So, how can we extend this to Slitherlink?
The T&E(k) classification, the T&E(1) vs braids theorem still holds. What we don't know is the proportion of minimal puzzles in T&E(0 or 1) for some fixed grid size.
For any puzzle, we'll always find large instances that can't be solved by reasonably simple purely logical means. I think also that, for not too small grid size, we'll always find exceptionally hard instances of that size.
Where one puts the boundary of "reasonably simple" is much a matter of personal taste. For me, it may be whips or g-whips or B-whips or S-whips (or corresponding braids) - possibly of restricted size - , plus small-size Subsets or gSubsets, plus application specific rules (e.g. sk-loops in Sudoku; ascending chains, hills and valleys in Futoshiki; adjacent 3s and incomplete-loops in Slitherlink, ...)
In any case, there will always be a point where NO pattern-based solution will be possible. As the pattern-based requirement comes from players, I don't think this is a big problem: puzzles proposed to players shouldn't be too hard. Indeed, for all the puzzle types I’ve analysed in my last book, whips are so powerful that small ones (+ small Subsets) cover much more than puzzles ever proposed to real players.
Serg wrote:Is your CRT sufficient to build Slitherlink solver w/o any empirical rules?
The only rules I use for solving all the puzzles mentioned in my previous post are:
1) Singles, elementary constraint propagation,
3) elimination of partial loops,
4) plus a few application-specific rules that are formally reducible to the previous ones (I use them only because they are popular).
1 and 2 are meaningful and valid for any CSP and 3 can't be avoided in Slitherlink (it's part of the basic problem constraints). Is that what you meant by "w/o empirical rules" ?