/*

Works for SICStus and B-Prolog
You may want to comment out the use_module declaration for B-Prolog
and search for labeling( in the clause for nono/1 and adapt that for
each specific system.

Queries are of the form

?- nono(<something>).

The <something> is the first argument of the cols/2 and rows/2 facts
at the end of this file.

The large one is ?- nono(cast).

you can of course do ?- nono(X).


There is an SWI version for this as well, and a GNU Prolog version,
but not yet available on the net.

Sorry for the mess in the implementation - it grew organically of
course and I lack the time and interest to clean it up.

*/

:- use_module(library(clpfd)).

nono(I) :-
	cols(I,Cols),
 	rows(I,Rows),
	length(Cols,NC),
	length(Rows,NR),
 	gen_xij(NR,NC,A),
	gen_begin_end(Rows,FullRows),
	skimbe(FullRows,[],BERs),
	gen_begin_end(Cols,FullCols),
	skimbe(FullCols,[],BECs),
	app(BERs,BECs,BEs),
 	(domain(BERs,1,NC)),
 	(domain(BECs,1,NR)),
	dobes(FullRows),
	dobes(FullCols),
 	gen_rows(FullRows,A,1,NC),
 	gen_cols(FullCols,A,1,NR),
	write(start_labeling), nl,
 	labeling([ff],BEs),
%	labelingff(BEs),
%	labeling(BEs),
	print_sol(NC,NR,A),
	nl,
	write(-----------), nl.


gen_rows([],_,_,_).
gen_rows([F|Fs],A,Row,NC) :-
	(F == [] ->
	    gen_row0(NC,Row,A)
	;
	    gen_row(F,A,Row,NC,_)
	),
	Row1 is Row + 1,
	gen_rows(Fs,A,Row1,NC).

gen_row([],_,_,_,_).
gen_row([f(B,_,E)|R],A,Row,NC,First) :-
	(var(First) ->
	    gen_before_row(Row,NC,B,A),
	    First = no
	;
	    true
	),
	between_b_e_row(Row,NC,A,B,E,1),
	(R == [] ->
	    gen_after_row(Row,NC,E,A)
	;
	    R = [f(B1,_,_)|_],
	    between_b_e_row(Row,NC,A,E,B1,0),
	    gen_row(R,A,Row,NC,First)
	).

between_b_e_row(Row,I,A,B,E,N) :-
	(I > 0 ->
	    sel(A,Row,I,X),
	    (N == 0 ->
		(((B #< I) #/\ (I #< E)) #=> X #= N)
	    ;
		(((B #=< I) #/\ (I #=< E)) #=> X #= N)
	    ),
	    II is I - 1,
	    between_b_e_row(Row,II,A,B,E,N)
	;
	    true
	).

gen_before_row(Row,I,B,A) :-
	(I > 0 ->
	    sel(A,Row,I,X),
	    ((I #< B) #=> X #= 0),
	    II is I - 1,
	    gen_before_row(Row,II,B,A)
	;
	    true
	).

gen_after_row(Row,I,E,A) :-
	(I > 0 ->
	    sel(A,Row,I,X),
	    ((E #< I) #=> X #= 0),
	    II is I - 1,
	    gen_after_row(Row,II,E,A)
	;
	    true
	).


gen_cols([],_,_,_).
gen_cols([F|Fs],A,Col,NC) :-
	(F == [] ->
	    gen_col0(NC,Col,A)
	;
	    gen_col(F,A,Col,NC,_)
	),
	Col1 is Col + 1,
	gen_cols(Fs,A,Col1,NC).

gen_col([],_,_,_,_).
gen_col([f(B,_,E)|R],A,Col,NC,First) :-
	(var(First) ->
	    gen_before_col(Col,NC,B,A),
	    First = no
	;
	    true
	),
	between_b_e_col(Col,NC,A,B,E,1),
	(R == [] ->
	    gen_after_col(Col,NC,E,A)
	;
	    R = [f(B1,_,_)|_],
	    between_b_e_col(Col,NC,A,E,B1,0),
	    gen_col(R,A,Col,NC,First)
	).

between_b_e_col(Col,I,A,B,E,N) :-
	(I > 0 ->
	    sel(A,I,Col,X),
	    (N == 0 ->
		(((B #< I) #/\ (I #< E)) #=> X #= N)
	    ;
		(((B #=< I) #/\ (I #=< E)) #=> X #= N)
	    ),
	    II is I - 1,
	    between_b_e_col(Col,II,A,B,E,N)
	;
	    true
	).

gen_before_col(Col,I,B,A) :-
	(I > 0 ->
	    sel(A,I,Col,X),
	    ((I #< B) #=> X #= 0),
	    II is I - 1,
	    gen_before_col(Col,II,B,A)
	;
	    true
	).

gen_after_col(Col,I,E,A) :-
	(I > 0 ->
	    sel(A,I,Col,X),
	    ((E #< I) #=> X #= 0),
	    II is I - 1,
	    gen_after_col(Col,II,E,A)
	;
	    true
	).

gen_row0(I,Row,A) :-
	(I == 0 ->
	    true
	;
	    sel(A,Row,I,X),
	    (X #= 0),
	    I1 is I - 1,
	    gen_row0(I1,Row,A)
	).


gen_col0(I,Col,A) :-
	(I == 0 ->
	    true
	;
	    sel(A,I,Col,X),
	    (X #= 0),
	    I1 is I - 1,
	    gen_col0(I1,Col,A)
	).

dobes([]).
dobes([X|R]) :- dobes1(X), dobes(R).

dobes1([]).
dobes1([f(B,I,E)|R]) :-
	(B + I-1 #= E),
	(R == [] ->
	    true
	;
	    R = [f(B1,_,_)|_],
	    (E + 1 #< B1)
	),
	dobes1(R).

gen_begin_end([],[]).
gen_begin_end([L|Ls],[FullL|FullLs]) :-
	gen_begin_end1(L,FullL),
	gen_begin_end(Ls,FullLs).

gen_begin_end1([],[]).
gen_begin_end1([I|R],[f(_B,I,_E)|S]) :- gen_begin_end1(R,S).

gen_xij(NR,NC,X) :-
	functor(X,x,NR),
	X =.. [_|XR],
	fillxr(XR,NC).

fillxr([],_).
fillxr([C|Cs],NC) :-
	functor(C,y,NC),
	C =.. [_|CR],
	domx(CR),
	fillxr(Cs,NC).

domx([]).
domx([A|As]) :-
	(A in 0 .. 1),
	domx(As).

skimbe([],I,I).
skimbe([A|As],In,Out) :-
	skimbe1(A,In,NewIn),
	skimbe(As,NewIn,Out).

skimbe1([],I,I).
skimbe1([f(B,_,E)|R],I,Out) :- skimbe1(R,[B,E|I],Out).
	  
gen_bevars([L|R],I,W) :-
	gen_bevars1(L,I,1,W),
	I1 is I + 1,
	gen_bevars(R,I1,W).

gen_bevars1([],_,_,_).
gen_bevars1([_|R],I,J,W) :-
	wl([tab,tab,space,b(W,I,J),comma,nl]),
	wl([tab,tab,space,e(W,I,J),comma,nl]),
	J1 is J + 1,
	gen_bevars1(R,I,J1,W).


wl([]).
wl([X|R]) :- wx(X), wl(R).

wx(nl) :- !, nl.
wx(comma) :- !, write(',').
wx(tab) :- !, write('        ').
wx(space) :- !, write(' ').
wx(open) :- !, write('(').
wx(close) :- !, write(')').
wx(b(X,Y,Z)) :- !, write('B'), write(X), eval(Y), write('_'), eval(Z).
wx(e(X,Y,Z)) :- !, write('E'), write(X), eval(Y), write('_'), eval(Z).
wx(x(I,J)) :- !, write('X'), write(I), write('_'), write(J).
wx(X-A) :- !, Y is X - A, write(Y).
wx(X+A) :- !, Y is X + A, write(Y).
wx(X) :- write(X).

eval(X) :-
	(
	  integer(X) -> write(X)
	;
	  X = A+1 -> XX is A+1, write(XX)
	;
	  X = A-1 -> XX is A-1, write(XX)
	).

betw(I,J,X) :-
	I =< J,
	(
	  X = I
	;
	  II is I + 1,
	  betw(II,J,X)
	).

print_sol(NC,NR,A) :-
	betw(1,NR,I),
	nl,
	betw(1,NC,J),
	sel(A,I,J,X),
	write(X),
	fail.
print_sol(_,_,_).

sel(A,I,J,X) :- arg(I,A,AI), arg(J,AI,X).

app([],L,L).
app([X|R],S,[X|T]) :- app(R,S,T).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cols(a,[[1],[]]).
rows(a,[[1],[]]).


cols(c,[[1,1],[1],[1,1]]).
rows(c,[[1,1],[1],[1,1]]).

cols(d,[[1,1],[],[1,1]]).
rows(d,[[1,1],[],[1,1]]).

cols(e,[[3],[3],[3]]).
rows(e,[[3],[3],[3]]).

cols(f,[[1,1],[1]]).
rows(f,[[1],[1],[1]]).




cols(1,[[3,2],
	[8,2],
	[8,1,2],
	[2,1,5],
	[1,3,2,2],
	[2,1,2],
	[3,2],
	[9,1,2],
	[4,2,2],
	[1,6,1],
	[3,5],
	[1],
	[1,5],
	[1,3,1],
	[1,5]]).

rows(1,[[2],
	[3,3],
	[1,3,1],
	[1,3,1,1],
	[3,5,1,1],
	[3,1,1,1,1],
	[3,1,1,1,1],
	[5,1,1,1],
	[1,1,1,1,1,1,1],
	[1,1,1,1,1,1,1],
	[2,2,1,1,1,1,1],
	[11,1,1],
	[1,1,1],
	[2,2,2,2],
	[2,2,2,1,1]]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cols(2,[[3],
	   [9],
	   [7],
	   [3,1,2],
	   [2,1,1],
	   [2,2,1,1,1,1],
	   [3,4,2,1],
	   [3,1,1],
	   [3,4,1,1],
	   [2,2,1,1,2,1],
	   [3,2,2],
	   [3,1,1,2],
	   [4,3],
	   [6,2],
	   [4,3]]).

rows(2,[[2,2],
	   [5],
	   [3],
	   [1,3],
	   [5],
	   [4,7],
	   [6,1,3],
	   [3,1,2,1,2],
	   [2,2,1,2],
	   [2,1,1,2],
	   [4,1,3],
	   [3,1,1,2,2],
	   [2,1,5,1,2],
	   [1,2,2,1],
	   [1,6,1]]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cols(3,[[2,1],
	   [2,2,1,2],
	   [2,2,5,1],
	   [2,2,1,1,3],
	   [4,5,2,2],
	   [4,6,2,2],
	   [1,3,5,2,2],
	   [1,2,1,3,3,2],
	   [1,1,1,1,1,2,2],
	   [1,1,1,1,1,4],
	   [1,1,1,1,2,2,2],
	   [4,2,4,2],
	   [6,6,2],
	   [3,1,5,3,2],
	   [2,2,3,4],
	   [2,5,1,2],
	   [2,1,3,3,2],
	   [2,2,2,2,2],
	   [4,1,3],
	   [2,2]]).


rows(3,[[7,1],
	   [1,1,1,3,2],
	   [14,4],
	   [6,3,2,2],
	   [1,1,1,1,1,1,2],
	   [1,1,4],
	   [1,1,1,4,1],
	   [3,2,2,2],
	   [6,2,1,1],
	   [10,3,1],
	   [1,4,4,1],
	   [1,4,1,4,1],
	   [1,2,3,2],
	   [4,2,3,1],
	   [1,4,2,2,2],
	   [1,2,1,1,1],
	   [2,2,2,1],
	   [1,9,1,4],
	   [1,5,10],
	   [2,5]]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cols(4,[[1],[1],[1]]).
rows(4,[[1,1],[1]]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cols(cast,[[2,3,1,5,1,7,1],
	[2,4,2,3,2,3,5],
	[2,6,3,1,1,5,1,5],
	[2,4,2,1,1,1,4,1,1,2],
	[2,8,2,1,5,2,5],
	
	[3,1,6,2,5,1,5],
	[3,3,3,1,1,6,1,1,1],
	[3,2,2,2,2,8,1,1,3],
	[1,4,4,3,7,1,1],
	[1,2,2,2,3,7,9],
	
	[1,2,3,1,1,5,2,2],
	[2,2,3,1,1,6,1],
	[1,3,1,5,4,1],
	[1,3,1,1,6,1,3,1],
	[3,3,4,5,1,4,2,1],
	
	[2,3,3,9,7,1],
	[2,3,2,2,1,1,3,5],
	[4,2,1,1,1,1,2,3],
	[4,2,2,1,4,3,2],
	[4,3,16,2],
	
	[1,2,5,7,1],      
	[4,3,2,2,7,1],      
	[2,3,1,10,1],      
	[2,4,2,1,4,1],      
	[1,6,7,3,1],      
	
	[3,11,3,1],      
	[7,1,11,2,1],      
	[2,2,2,2,2,2,2],      
	[3,1,1,1,1,2,1],      
	[2,2,2,2,1,1,1],      
	
	[1,1,1,1,2,1,2],      
	[2,2,2,2,1,1,1,1],      
	[4,1,1,2,2],      
	[5,2,17,2,1],      
	[9,2,3,1,4,2],      
	
	[9,4,2,1,1,1],      
	[5,4,2,1,4],      
	[11,1,2,1,4,1,2],      
	[3,4,2,4,4],      
	[2,1,4,1,2,1,5,2],      
	
	[8,4,1,1,2],      
	[1,1,3,2,3],      
	[1,3,1,8,1,6],      
	[2,1,7,14],      
	[1,2,4,4,1,2,3],      
	
	[1,1,4,2,1,1,1,1,1,4],      
	[3,5,3,1,1,4],      
	[2,4,2,2,1,2],      
	[4,2,3,8,4],      
	[4,15,2,2,4],      
	
	[4,1,10,2,1,2],      
	[2,12,6,1,2,4],      
	[3,1,3,1,3,3,4],      
	[3,1,2,3,4,1],      
	[5,2,2,2,3,3,3],      
	
	[1,2,2,2,2,4,1,1,3],      
	[2,1,4,2,7,1,1],      
	[5,2,2,3,6,3],      
	[3,3,2,2,3,2,3],      
	[4,1,2,1,1,2,1]]).

rows(cast,[[12,1,1,1],                                
	[8,6,3,1,3],                                
	[5,8,4,3,1,5],                                
	[7,3,4,1,3,5,1,7],                                
	[2,2,4,9,1,5,1,1,1,1,1,1,1],                                
	
	[4,5,10,2,1,8,7,1],                                
	[5,1,3,3,16,1,2],                                
	[8,5,1,2,4,9,1,3],                                
	[4,5,3,14,1,1,1,1,4,1,1,3],                                
	[3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2],                                
	
	[8,2,7,2,1,1,2,1,1,3,3],                                
	[1,5,9,12,2,1,1,3,1,1,2,2,1],                                
	[3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2],                                
	[5,2,2,2,2,1,5,2,1,1,2,5],                                
	[3,5,9,2,1,1,6,3,1,3,2,3],                                
	
	[1,4,1,1,1,4,1,5,5,3,3,3],                                
	[4,1,1,1,1,3,4,6,6,3],                                
	[3,1,3,1,1,3,3,1,1,4,6,1],                                
	[3,1,5,1,1,3,1,1,9,4,1],                                
	[2,1,1,7,1,4,1,1,1,1,1,1,3,5],                                
	
	[9,2,1,3,1,1,1,1,4,2,1],                                
	[1,14,1,1,2,2,2,10,1,2],                                
	[1,9,2,1,2,6,1,5,3,2],                                
	[1,9,9,1,2,2,3,1,1,4,3,1],                                
	[10,1,3,4,1,3,2,1,2,8],                                
	
	[9,1,3,5,1,1,1,2,7],                                
	[4,5,1,2,5,1,3,1,1,2,1,3],                                
	[1,1,1,1,2,6,2,3,2,1,1,2,3,1],                                
	[1,6,1,5,7,1,3,3,2,4,3],                                
	[1,2,1,2,9,1,5,2,6,2],                                
	
	[10,2,2,13,1,3,3,1],                                
	[2,2,1,6,2,3,3,2,2,2,1],                                
	[2,2,1,1,12,2,2,9,2,2,2,2],                                
	[5,1,2,4,1,5,11,2,2],                                
	[15,6,18]]).