/*===========================================================
This Problem is from: http://www.quora.com/challenges
Programming Challenges
1. Datacenter Cooling
We have some rooms in our datacenter, and we need to connect them all with a single cooling duct.
Here are the rules:
The datacenter is represented by a 2D grid.
Rooms we own are represented by a 0.
Rooms we do not own are represented by a 1.
The duct has to start at the air intake valve, which is represented by a 2.
The duct has to end at the air conditioner, which is represented by a 3.
The duct cannot go in multiple directions out of the intake or the AC  they must be the two endpoints of the duct.
The duct must pass through each room exactly once.
The duct cannot pass through rooms we do not own.
The duct can connect between rooms horizontally or vertically but not diagonally.
Here is an example datacenter:
2 0 0 0
0 0 0 0
0 0 3 1
There are two possible ways to run the duct here:
2000

0000

003 1
or
2 000
  
0 0 00
  
00 3 1
Write a program to compute the number of possible ways to run the duct.
For the above example, the correct answer is 2.
(** we do not use this here, but encode the data in the program **)
Input format:
Your program should read from stdin. The input will be a series of integers separated by whitespace.
The first two integers will be W and H, with width and height of the datacenter. These will be followed by W*H more integers, specifying the 2D grid representing the datacenter.
Output format:
Your program should write a single integer out to stdout: the number of possible ways to run the duct.
See how fast you can make it.
Our best solution (written in C) can solve the following test case in under 5 seconds on a 2.4GHz Pentium 4, but it's pretty good if you can get to within 12 orders of magnitude of that.
7 8
2 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 1 1
===========================================================*/
% Quora Datacenter Cooling Problem
% http://www.quora.com/challenges
% By Helmar Gust (2011)
% University of OsnabrÃ¼ck
% helmar.gust@uos.de
% https://cogsci.uniosnabrueck.de/~hgust/programs/datacentercooling.pl
%
% The following program is very general
% It can even handle problems with multiple intakes and ACs
%
% data specification
% I added blocked rooms to simulate the border
% (may be done by a preprocessor)
% simple (N=2)
data(0,[
[1,1,1,1,1,1],
[1,2,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,3,1,1],
[1,1,1,1,1,1]
]).
% original problem (N=301716)
data(1,[
[1,1,1,1,1,1,1,1,1],
[1,2,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,3,0,0,0,0,1,1,1],
[1,1,1,1,1,1,1,1,1]
]).
% extended problem with two intakes and two ACs (N=86513)
data(2,[
[1,1,1,1,1,1,1,1,1],
[1,2,0,0,2,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,1],
[1,3,0,0,3,0,1,1,1],
[1,1,1,1,1,1,1,1,1]
]).
%
% specifying the problem
%
% rooms are represented by their four sides
% (possible interfaces): r(Type,N,O,S,W)).
% for N(orth),O(est),S(outh),W(est):
%  : no interface (blocked)
% c(I,O,V) : interface referring to branch V
% with intake I and AC O
% rooms with a single connection (in or out)
r(2,c(I,_,_),,,) : end_duct(I,2).
r(2,,c(I,_,_),,) : end_duct(I,2).
r(2,,,c(I,_,_),) : end_duct(I,2).
r(2,,,,c(I,_,_)) : end_duct(I,2).
r(3,c(_,O,_),,,) : end_duct(O,3).
r(3,,c(_,O,_),,) : end_duct(O,3).
r(3,,,c(_,O,_),) : end_duct(O,3).
r(3,,,,c(_,O,_)) : end_duct(O,3).
% rooms with two connections
r(0,A,,B,) : connect_duct(A,B).
r(0,,A,,B) : connect_duct(A,B).
r(0,A,B,,) : connect_duct(A,B).
r(0,,A,B,) : connect_duct(A,B).
r(0,,,A,B) : connect_duct(A,B).
r(0,A,,,B) : connect_duct(A,B).
% blocked rooms (no connection)
r(1,,,,).
%
% the only tricky thing:
% represents connections by shared variables
% a room of type 0 connects two branches
% which must not already be connected
% (the variables must not be shared before
% but are shared afterwards)
% to avoid cycles
connect_duct(c(I,O,A),c(I,O,B)) :
var(A), var(B), not(A==B) > A=B; fail.
% intakes and ACs end a branch
% we use a similar strategy here:
% only one end of each type
end_duct(X,T) : var(X) > X=T; fail.
%
% How to solve the Problem
%
% two phases
% 1. build the topology (establish the constraints)
% (belongs to the specification of the problem)
%
% 2. solve the CSP problem
%
%
% 1. phase: building the topology
% All the global constraints:
% adjacent sides of rooms must have
% the same properties (same variable C):
% either they are blocked ()
% or they refer to the same branch of the duct
% horizontal connection: O(est) of arg1 = W(est) arg2
connect_h(r(_Type1,_,C,_,_),r(_Type2,_,_,_,C)).
% vertical connection: S(outh) of arg1 = N(orth) of arg2
connect_v(r(_Type1,_,_,C,_),r(_Type2,C,_,_,_)).
% here we only look for rooms of type 1
% if it's a room of this type, all sides are blocked
check_1(r(1,,,,)) : !.
check_1(_). % otherwise no restriction
% connect_rows(+RowTypes1, +RowTypes2, RowRooms1, RowRoomes2)
% takes two adjacent rows of room types (arg1 arg2)
% computes the corresponding room representations (arg3 arg4)
% together with the connection constraints (topology)
% we handle rooms of type 1 here, because these are deterministic
connect_rows([_],[_],[_],[_]). % nothing to do if only one room
% we look at a square of 4 adjacent rooms and
% establish all horizontal and vertical relations
connect_rows([TA1,TB1TR1],
[TA2,TB2TR2],
[A1,B1R1],
[A2,B2R2]) :
% that's how room representations look like:
A1 = r(TA1,_,_,_,_), B1 = r(TB1,_,_,_,_),
A2 = r(TA2,_,_,_,_), B2 = r(TB2,_,_,_,_),
% all the interface conditions (equal variables for adjacent sides):
connect_h(A2,B2), % this is a bit redundant
connect_v(A1,A2), % since we are doing some things twice
connect_h(A1,B1), % but this phase is efficient anyway
connect_v(B1,B2), % since the program is deterministic
% for rooms of type 1 block all sides:
check_1(A1),
check_1(A2),
check_1(B1),
check_1(B2),
connect_rows([TB1TR1],[TB2TR2],[B1R1],[B2R2]).
% topology(+Problem, Topology)
% takes a problem (arg1) and computes the topology (arg2)
topology([_], [_]). % nothing to do if only one row
topology([TRow1, TRow2  TR], [Row1, Row2  R]) :
connect_rows(TRow1, TRow2, Row1, Row2),
topology([TRow2  TR], [Row2  R]).
%
% end of specification
%
%
% 2. phase: solve the problem
% by instantiating all the rooms
% the real problem solving task is left to the
% Prolog engine
% for all rows: solve it
solve([]).
solve([XR]) : solve_row(X), solve(R).
% for all rooms: solve ist
solve_row([]).
solve_row([XR]) : X, solve_row(R).
%
% that's it
%
%
% a wrapper for computing the number of solutions
:op(900,fx,push),op(900,fx,pop),op(900,xfx,+=).
doit(Problem,_N) :
push n = 0, % init count to 0
data(Problem,D), % lookup data
topology(D,L), % build topology
solve(L), % solve it
% maplist(writeln,L), % if we want to see the solutions
n += 1, % update count
next. % next solution (simply fails)
doit(_P,N) : pop n = N. % lookup count
%
% Some syntactic sugar to make even
% the procedural part look nice.
% We use a predicate global_vars to store
% a stack of global variables
push N = V : asserta(global_vars(N,V)).
pop N = V : retract(global_vars(N,V)).
N += I :
retract(global_vars(N,X)), !,
Y is X + I,
asserta(global_vars(N,Y)).
next : fail.
% run: ? doit(2,N).
%
%