Takes too long for some puzzles

[denilsonsa]

Since this solver uses a plain brute-force algorithm, some puzzles may take too long to solve.

Is there any kind of way to cut some branches of the brute-force, so that it won't take as long to solve? I don't have a clear answer right now, but I'm documenting here some of these slow puzzles.

ssSs
sD3s
S23s
d33t
dDt2
TttT

DSs2ss
2D2dtS
d222t2
dd2tTT

dTdsSt
d2t32t
dD323T
Ddd2sS

tTDDSs
t2t33s
2d33ts
S22Ts

tTtt
t42t
d3tT
d32D
Dd3d
ddd

ttt22d2S
tt23S2s2
tT232ssd
tTttDsD

[denilsonsa]

Possible improvements:

• Blocked path checking
  • Upon placing a diagonal edge, detect if blocking the crossing diagonal would lead make the puzzle unsolvable. An example is the 4 block, which requires 8 edges around it. If any of those edges are blocked, the solution will not be found. This can be implemented by having a new attribute available_edges on each Node. If available_edges < missing_edges, then stop exploring the current solution branch.
• Trying edges in a different order
  • Some nodes have very few connection possibilities, sometimes a single one (e.g. a 4 node). These could be tried first.
  • Will require a lot of changes to the code, and will require some post-processing to calculate the edge directions and colors.
  • Care must be taken to not end up with isolated (circular?) paths that are uncolored.

[jbosboom]

My solver maintains a set of possible colors for each edge and implements some simple inference rules that prune these sets. My blog post about LYNE briefly outlines an inference rule reasoning about paths, not just individual nodes or edges, though I didn't find it necessary to implement. (I link rather than describing the rules here so you can figure them out on your own if you'd prefer. I enjoyed writing my solver more than playing the game itself, and I don't want to spoil that for you.)