%% Bag puzzle.
%% Juego que consiste en hacer un camino que rodee todos los números del tablero
%% siguiendo unas reglas:
%% R1: El camino tiene que ser cerrado.
%% R2: Todos los números tienen que estar rodeados por el camino.
%% R3: El número de casillas visibles en toda dirección de una casilla enumerada
%% tiene que ser igual al número de la casilla.
x(0..n). y(0..m). direccion(v;h).
pos(X,Y) :- x(X), y(Y).
%% Generación.
{linea(S,X,Y)} :- direccion(S), x(X), y(Y).
:- linea(h,n,Y), y(Y).
:- linea(v,X,m), x(X).
%% Restricciones:
%% R1: El camino tiene que ser cerrado.
%% Cada punto del camino esta conectado exactamente a otros dos
:- 3 {linea(h,X-1,Y); linea(h,X,Y); linea(v,X,Y); linea(v,X,Y-1)}, en(X,Y).
:- {linea(h,X-1,Y); linea(h,X,Y); linea(v,X,Y); linea(v,X,Y-1)} 1, en(X,Y).
en(X,Y) :- linea(S,X,Y).
en(X+1,Y) :- linea(h,X,Y).
en(X,Y+1) :- linea(v,X,Y).
%% Todo punto del camino es alcanzable por cualquier otro.
:- en(X,Y), en(Z,W), not alcanzable(X,Y,Z,W).
adj(X,Y,X,Y+1) :- linea(v,X,Y).
adj(X,Y,X+1,Y) :- linea(h,X,Y).
adj(X,Y,Z,W) :- adj(Z,W,X,Y).
alcanzable(X,Y,X,Y) :- en(X,Y).
alcanzable(X,Y,Z,W) :- alcanzable(I,J,Z,W), adj(X,Y,I,J).
%% R3: El número de casillas visibles en toda dirección de una casilla enumerada
%% tiene que ser igual al número de la casilla.
:- N {visible(X,Y,Z,T): pos(Z,T)}, numero(N,X,Y).
:- {visible(X,Y,Z,T): pos(Z,T)} N-2, numero(N,X,Y).
% Visibilidad en casillas adyacentes.
visible0(X,Y,X,Y+1) :- pos(X,Y), not linea(h,X,Y+1), Y<m-1.
visible0(X,Y,X,Y-1) :- pos(X,Y), not linea(h,X,Y), Y>0.
visible0(X,Y,X+1,Y) :- pos(X,Y), not linea(v,X+1,Y), X<n-1.
visible0(X,Y,X-1,Y) :- pos(X,Y), not linea(v,X,Y), X>0.
% Visibilidad general
visible(X,Y,Z,T) :- visible0(X,Y,Z,T).
visible(X,Y,Z,Y) :- visible(X,Y,Z+1,Y), visible0(Z,Y,Z+1,Y), Z<X-1, X>1, X<n, Y<m.
visible(X,Y,Z,Y) :- visible(X+1,Y,Z,Y), visible0 (X,Y,X+1,Y), Z>X+1, X<n-2, Y<m.
visible(X,Y,X,T) :- visible(X,Y+1,X,T), visible0(X,Y,X,Y+1), T>Y+1, Y<m-2, X<n.
visible(X,Y,X,T) :- visible(X,Y,X,T+1), visible0(X,T,X,T+1), T<Y-1, Y>1, Y<m, X<n.
%% R2: Todos los números tienen que estar rodeados por el camino.
:- numero(M,X,Y), fuera(X,Y).
fuera(X,Y) :- Y=m-1, X<n, numero(M,X,Y), not linea(h,X,Y+1).
fuera(X,Y) :- Y=0, X<n, numero(M,X,Y), not linea(h,X,Y).
fuera(X,Y) :- X=n-1, Y<m, numero(M,X,Y), not linea(v,X+1,Y).
fuera(X,Y) :- X=0, Y<m, numero(M,X,Y), not linea(v,X,Y).
fuera(X,Y) :- X<n-1, X>0, Y<m-1, Y>0, numero(M,X,Y),visible(X,Y,0,Y), not linea(v,0,Y).
fuera(X,Y) :- X<n-1, X>0, Y<m-1, Y>0, Z=n-1, numero(M,X,Y),visible(X,Y,Z,Y), not linea(v,n,Y).
fuera(X,Y) :- X<n-1, X>0, Y<m-1, Y>0, numero(M,X,Y),visible(X,Y,X,0), not linea(h,X,0).
fuera(X,Y) :- X<n-1, X>0, Y<m-1, Y>0, T=m-1, numero(M,X,Y),visible(X,Y,X,T), not linea(h,X,m).
%Presentación.
#show linea/3.
