% http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/MazeGeneration.shtml
% by Neng-Fa Zhou, April 12, 2009

:-include(base).   % use foreach/3 in base.pl

solve(As):-
    get_largest_atom(As,row(N)),
    get_largest_atom(As,col(M)),
    a2_new(Maze,M,N), % a 2-dimensional array
    a2_new(Connected,M,N),
    prop_connected(Maze,Connected,M,N),
    array_to_list(Maze,Vars),  % built-in in B-Prolog
    Vars :: 0..1,
    (member(entrance(Xen,Yen),As)->true;true),
    a2_get(Maze,Xen,Yen,0),
    (member(exit(Xex,Yex),As)->true;true),
    a2_get(Maze,Xex,Yex,0),
    fill_wall_empty_cells(As,Maze),
    fill_edges(Maze,M,N),
    no_2x2(Maze,M,N),
    not_surrounded(Maze,M,N),
    constrain_diagonally_adjacent(Maze,M,N),
    labeling([ffc],Vars),
    a2_get(Connected,Xen,Yen,SCCen),
    a2_get(Connected,Xex,Yex,SCCex),
    SCCen==SCCex,
    writeln(Vars).
        
% the scc variables of two cells are unified if the two cells are connected by empty cells
prop_connected(Maze,Connected,M,N):-
    foreach((X in 1..M-1, Y in 1..N-1),
	    [This,Right,Down,SCC_this,SCC_right,SCC_down],
	    (a2_get(Maze,X,Y,This),
	     a2_get(Maze,X+1,Y,Right),
	     a2_get(Maze,X,Y+1,Down),
	     a2_get(Connected,X,Y,SCC_this),
	     a2_get(Connected,X+1,Y,SCC_right),
	     a2_get(Connected,X,Y+1,SCC_down),
	     This#=0 #/\ Right#=0 #=> SCC_this#=SCC_right,
	     This#=0 #/\ Down#=0 #=> SCC_this#=SCC_down)).

fill_wall_empty_cells(As,Maze):-
    foreach((A in As),[X,Y],
	    (A=wall(X,Y)->a2_get(Maze,X,Y,1);
	     A=empty(X,Y)->a2_get(Maze,X,Y,0);
	     true)).

% If a cell is on any of the edges of the grid, and is not an 
% entrance or an exit, it must contain a wall. 
fill_edges(Maze,M,N):-
    foreach(X in 1..M,
	     [E1,E2],
	     (a2_get(Maze,X,1,E1),(E1==0->true;E1=1),
	      a2_get(Maze,X,N,E2),(E2==0->true;E2=1))),
    foreach(Y in 1..N,
	     [E1,E2],
	     (a2_get(Maze,1,Y,E1),(E1==0->true;E1=1),
	      a2_get(Maze,M,Y,E2),(E2==0->true;E2=1))).
    
% There must be no 2x2 blocks of empty cells or walls. 
no_2x2(Maze,M,N):-
    foreach((X in 1..M-1, Y in 1..N-1),
            [A11,A12,A21,A22],
	    (a2_get(Maze,X,Y,A11),
	     a2_get(Maze,X,Y+1,A12),
	     a2_get(Maze,X+1,Y,A21),
	     a2_get(Maze,X+1,Y+1,A22),
	     A11+A12+A21+A22#>0,
	     A11+A12+A21+A22#<4)).

% No wall can be completely surrounded by empty cells.     
not_surrounded(Maze,M,N):-
    foreach((X in 3..M-2, Y in 3..N-2),
             [This,Left,Right,Up,Down],
            (a2_get(Maze,X,Y,This),
            a2_get(Maze,X-1,Y,Left),
	     a2_get(Maze,X+1,Y,Right),
	     a2_get(Maze,X,Y-1,Up),
	     a2_get(Maze,X,Y+1,Down),
	     This #= 1 #=> Left+Right+Up+Down #> 0)).

% If two walls are diagonally adjacent then one or other of 
% their common neighbours must be a wall. 
constrain_diagonally_adjacent(Maze,M,N):-
    foreach((X in 1..M-1, Y in 1..N-1),
            [A11,A12,A21,A22],
	    (a2_get(Maze,X,Y,A11),
	     a2_get(Maze,X,Y+1,A12),
	     a2_get(Maze,X+1,Y,A21),
	     a2_get(Maze,X+1,Y+1,A22),
	     A11+A22#=2 #=> A12+A21#=1,
	     A12+A21#=2 #=> A11+A22#=1)).

test:-
     solve([row(1),row(2),row(3),row(4),row(5),col(1),col(2),col(3),col(4),col(5),entrance(1,2),exit(5,4),wall(3,3),empty(3,4)]).
    
/*
A solution to the test instance
##### 
> # #
# # #
#   >
#####
*/