%white(1,3).
%white(2,3).
%white(4,1).
%white(5,3).
%black(4,2).
white(1,3). black(1,6). black(3,1). black(3,4). white(3,5).
black(3,8). white(3,10). white(4,7). black(5,3). black(5,8).
white(5,9). white(5,10). white(6,6). white(7,2). white(7,4).
white(7,7). white(7,8). white(8,2). white(8,5). black(9,9).
black(10,1). white(10,3). white(10,6).
#const n = 10.
#const m = 10.
col(1..n). row(1..m). direction(v;h).
ball(X,Y) :- black(X,Y), col(X), row(Y).
ball(X,Y) :- white(X,Y), col(X), row(Y).
% Generate a set of unit segments passing through cells
{line(S,X,Y)} :- direction(S), col(X), row(Y).
:- line(h,n,Y), row(Y).
:- line(v,X,m), col(X).
% including balls:
:- ball(X,Y), not on(X,Y).
on(X,Y) :- line(S,X,Y), direction(S), col(X), row(Y).
on(X+1,Y) :- line(h,X,Y), col(X), row(Y), X<n.
on(X,Y+1) :- line(v,X,Y), col(X), row(Y), Y<m.
% ensuring the constraints M1--M3 are satisfied:
% M1:
% Every cell that the generated line passes through is
% connected to exactly 2 such grid cells:
:- 3 {line(h,X-1,Y); line(h,X,Y); line(v,X,Y); line(v,X,Y-1)}, on(X,Y), col(X), row(Y).
:- {line(h,X-1,Y); line(h,X,Y); line(v,X,Y); line(v,X,Y-1)} 1, on(X,Y), col(X), row(Y).
% Furthermore, every cell on the generated line is reachable
% from other grid cells on the line:
:- on(X,Y), on(Z,W), not reachable(X,Y,Z,W), col(X;Z), row(Y;W).
adj(X,Y,X,Y+1) :- line(v,X,Y), col(X), row(Y), Y<m.
adj(X,Y,X+1,Y) :- line(h,X,Y), col(X), row(Y), X<n.
adj(X,Y,Z,W) :- adj(Z,W,X,Y), col(X;Z), row(Y;W).
reachable(X,Y,X,Y) :- on(X,Y), col(X;Z), row(Y;W).
reachable(X,Y,Z,W) :- reachable(I,J,Z,W), adj(X,Y,I,J), col(X;I;Z), row(Y;J;W).
% M3:
% The loop must turn (90 degrees) at black circles
:- black(X,Y), line(h,X,Y), line(h,X-1,Y), col(X), row(Y).
:- black(X,Y), line(v,X,Y), line(v,X,Y-1), col(X), row(Y).
% but it must travel straight through the next and previous
% cells in its path.
:- 1{line(v,X+1,Y); line(v,X+1,Y-1)}, black(X,Y), line(h,X,Y), col(X), row(Y).
:- 1{line(v,X-1,Y); line(v,X-1,Y-1)}, black(X,Y), line(h,X-1,Y), col(X),row(Y).
:- 1{line(h,X,Y+1); line(h,X-1,Y+1)}, black(X,Y), line(v,X,Y), col(X), row(Y).
:- 1{line(h,X,Y-1); line(h,X-1,Y-1)}, black(X,Y), line(v,X,Y-1), col(X), row(Y).
% M2:
% White circles must be traveled straight through
:- 1{line(v,X,Y); line(v,X,Y-1)}, 1{line(h,X,Y); line(h,X-1,Y)}, white(X,Y), col(X), row(Y).
% but the loop must turn (90 degrees) in the previous
% and/or next cell in its path.
:- white(X,Y), line(h,X,Y), line(h,X+1,Y), line(h,X-1,Y), line(h,X-2,Y), col(X), row(Y).
:- white(X,Y), line(v,X,Y), line(v,X,Y+1), line(v,X,Y-1), line(v,X,Y-2), col(X), row(Y).
#show on/2.
