The tools evolve.
This was once a program of about 2000 lines of code.
Now, thanks to new tools from "Answer Set Programming", the essential part of the solver can be written with just 38 lines of code ( + a few lines of input for the actual puzzle).
The following code, written for
Clingo, will solve an example puzzle. It is also not that hard to read:
if the line doesn't contain :- then it's a fact.
if the line starts with :- then it says that the part on the right must not be true. a comma is a conjunction, so "a, not b" says "a must be true and b must not be true".
{ ... } is a set.
if a fact only consists of a set, then the solver may freely choose which of the variables in the set are true (so that all other conditions are satisfied).
m { ... } n says this set must consist of at least m and at most n members. so {a,b,c}2 says that at most 2 of a,b, and c must be true
if a line has a structure "something_on_the_left" :- "something_on_the_right" then it means that if "something_on_the_right" is true, then the program will make sure that "something_on_the_left" is also true.
The biggest difference: instead of a huge "visited" structure, 6 lines of code about which tiles were "reached" is enough, so the amount of variables is greatly reduced. also: the formalization of the rules is completely independant of the actual size of the puzzle (exactly one line of code needs to be changed for a different number of rows, in the most obvious way).
Just leaving it here, should someone decide that it is worth the effort to adjust the new formalization in such a way that it can be used for the other mode of the game. I also have a version three times as long, just for comments.
tile(0..rows+1,0..cols+1).
puzzle(1..rows,1..cols).
{ use_black(1..rows) }.
{ use_tile(0..rows+1, (0;cols+1)) }.
{ use_tile((0;rows+1), 0..cols+1) }.
{ black(X,Y); white(X,Y) } = 1 :- puzzle(X,Y).
{ start(1..rows,1..cols) } = 1.
{ end(1..rows,1..cols) } = 1.
{ start(X,Y); end(X,Y) } < 2 :- puzzle(X,Y).
use_tile(X,Y) :- use_black(X), black(X,Y).
use_tile(X,Y) :- not use_black(X), white(X,Y).
{ h(X,Y) : tile(X,Y), tile(X,Y+1) }.
{ v(X,Y) : tile(X,Y), tile(X+1,Y) }.
:- tile(X,Y), use_tile(X,Y),
{ start(X,Y); end(X,Y); v(X-1,Y); v(X,Y); h(X,Y-1); h(X,Y) } != 2.
:- tile(X,Y), not use_tile(X,Y),
{ start(X,Y); end(X,Y); v(X-1,Y); v(X,Y); h(X,Y-1); h(X,Y) } != 0.
reached(X,Y) :- start(X,Y).
reached(X,Y+1) :- reached(X,Y), h(X,Y).
reached(X,Y-1) :- reached(X,Y), h(X,Y-1).
reached(X-1,Y) :- reached(X,Y), v(X-1,Y).
reached(X+1,Y) :- reached(X,Y), v(X,Y).
:- use_tile(X,Y), not reached(X,Y).
#show end/2.
#show touch/2.
#show h/2.
#show v/2.
#show start/2.
{ touch(X,Y) : tile(X,Y) }.
:- touch(X,Y), not use_tile(X,Y).
{ u(X,Y) : touch(X,Y) }.
{ l(X,Y) : touch(X,Y) }.
:- 1 { h(X,Y-1); h(X,Y) } 1, not touch(X,Y), tile(X,Y).
:- 1 { v(X-1,Y); v(X,Y) } 1, not touch(X,Y), tile(X,Y).
:- tile(X,Y), h(X,Y), not touch(X,Y), not touch(X,Y+1),
{h(X,Y-1); h(X,Y+1); touch(X,Y-1); touch(X,Y+2); not l(X,Y-1); l(X,Y+2)} < 6.
:- tile(X,Y), v(X,Y), not touch(X,Y), not touch(X+1,Y),
{v(X-1,Y); v(X+1,Y); touch(X-1,Y); touch(X+2,Y); not u(X-1,Y); u(X+2,Y)} < 6.
#const rows=5.
#const cols=9.
black(1..rows,1).
black((1;5),2).
white(2..4,2).
black((1;3;5),3).
white((2;4),3).
black((1;5),4).
white(2..4,4).
black(1..rows,5).
black((1;5),6).
white(2..4,6).
black((1;3;5),7).
white((2;4),7).
black((1;5),8).
white(2..4,8).
black(1..rows,9).
#minimize { 1,X,Y : touch(X,Y) }.
