% Input predicate: square(X,Y,S)
% Input predicate: size(S).

% Available symbols.
symbol(1).
symbol(X) :- symbol(Y), X = Y + 1, size(S), X<=S.

% Misuse symbols as dimensions
dimX(X) :- symbol(X).
dimY(Y) :- symbol(Y).

% Dimensions define fields.
field(X,Y) :- dimX(X), dimY(Y).

% Single out the busy fields.
occupied(X,Y) :- square(X,Y,_).

% Guess assignments for the free fields. 
sol9(X,Y,1) v sol9(X,Y,2) v sol9(X,Y,3)
 v sol9(X,Y,4) v sol9(X,Y,5) v sol9(X,Y,6)
 v sol9(X,Y,7) v sol9(X,Y,8) v sol9(X,Y,9)
:- field(X,Y), not occupied(X,Y), size(9).

sol25(X,Y,1) v sol25(X,Y,2) v sol25(X,Y,3)
 v sol25(X,Y,4) v sol25(X,Y,5) v sol25(X,Y,6)
 v sol25(X,Y,7) v sol25(X,Y,8) v sol25(X,Y,9)
 v sol25(X,Y,10) v sol25(X,Y,11) v sol25(X,Y,12)
 v sol25(X,Y,13) v sol25(X,Y,14) v sol25(X,Y,15)
 v sol25(X,Y,16) v sol25(X,Y,17) v sol25(X,Y,18)
 v sol25(X,Y,19) v sol25(X,Y,20) v sol25(X,Y,21)
 v sol25(X,Y,22) v sol25(X,Y,23) v sol25(X,Y,24) v sol25(X,Y,25)
:- field(X,Y), not occupied(X,Y), size(25).

sol(X,Y,S) :- sol9(X,Y,S), size(9).
sol(X,Y,S) :- sol25(X,Y,S), size(25).

% Fix preassignments.
sol(X,Y,S) :- square(X,Y,S).

% One symbol per column. (Y1 < Y2 stands for Y1 <> Y2, to avoid useless symmetric constraints.)
:- sol(X,Y1,S), sol(X,Y2,S), Y1 < Y2.
% One symbol per row. (X1 < X2 stands for X1 <> X2, to avoid useless symmetric constraints.)
:- sol(X1,Y,S), sol(X2,Y,S), X1 < X2. 

% One symbol per box. lessThan (used in place of notEqual) avoids symmetric constraints.
:- sol(X1,Y1,S), sol(X2,Y2,S), sameSubSquare(X1,Y1,X2,Y2), lessThan(X1,Y1,X2,Y2).

% Hardcode boxes for 9x9
subrange(X,1) :- X > 0, X <= 3, symbol(X), size(9).
subrange(X,2) :- X > 3, X <= 6, symbol(X), size(9).
subrange(X,3) :- X > 6, X <= 9, symbol(X), size(9).

% Hardcode boxes for 25x25
subrange(X,1) :- X > 0, X <= 5, symbol(X), size(25).
subrange(X,2) :- X > 5, X <= 10, symbol(X), size(25).
subrange(X,3) :- X > 10, X <= 15, symbol(X), size(25).
subrange(X,4) :- X > 15, X <= 20, symbol(X), size(25).
subrange(X,5) :- X > 20, X <= 25, symbol(X), size(25).

sameSubSquare(X1,Y1,X2,Y2) :- subrange(X1,XS), subrange(X2,XS), subrange(Y1,YR), subrange(Y2,YR).


% Differing pairs.
% The presence of sameSubSquare(X1,Y1,X2,Y2) in the body limits the generation
% only to the the relevant tuples.
lessThan(X1,Y1,X2,Y2) :- X1 < X2, sameSubSquare(X1,Y1,X2,Y2).
lessThan(X1,Y1,X1,Y2) :- Y1 < Y2, sameSubSquare(X1,Y1,X1,Y2).