1 % Input predicate: square(X,Y,S)
   2 % Input predicate: size(S).
   3 
   4 % Available symbols.
   5 symbol(1).
   6 symbol(X) :- symbol(Y), X = Y + 1, size(S), X<=S.
   7 
   8 % Misuse symbols as dimensions
   9 dimX(X) :- symbol(X).
  10 dimY(Y) :- symbol(Y).
  11 
  12 % Dimensions define fields.
  13 field(X,Y) :- dimX(X), dimY(Y).
  14 
  15 % Single out the busy fields.
  16 occupied(X,Y) :- square(X,Y,_).
  17 
  18 % Guess assignments for the free fields. 
  19 sol9(X,Y,1) v sol9(X,Y,2) v sol9(X,Y,3)
  20  v sol9(X,Y,4) v sol9(X,Y,5) v sol9(X,Y,6)
  21  v sol9(X,Y,7) v sol9(X,Y,8) v sol9(X,Y,9)
  22 :- field(X,Y), not occupied(X,Y), size(9).
  23 
  24 sol25(X,Y,1) v sol25(X,Y,2) v sol25(X,Y,3)
  25  v sol25(X,Y,4) v sol25(X,Y,5) v sol25(X,Y,6)
  26  v sol25(X,Y,7) v sol25(X,Y,8) v sol25(X,Y,9)
  27  v sol25(X,Y,10) v sol25(X,Y,11) v sol25(X,Y,12)
  28  v sol25(X,Y,13) v sol25(X,Y,14) v sol25(X,Y,15)
  29  v sol25(X,Y,16) v sol25(X,Y,17) v sol25(X,Y,18)
  30  v sol25(X,Y,19) v sol25(X,Y,20) v sol25(X,Y,21)
  31  v sol25(X,Y,22) v sol25(X,Y,23) v sol25(X,Y,24) v sol25(X,Y,25)
  32 :- field(X,Y), not occupied(X,Y), size(25).
  33 
  34 sol(X,Y,S) :- sol9(X,Y,S), size(9).
  35 sol(X,Y,S) :- sol25(X,Y,S), size(25).
  36 
  37 % Fix preassignments.
  38 sol(X,Y,S) :- square(X,Y,S).
  39 
  40 % One symbol per column. (Y1 < Y2 stands for Y1 <> Y2, to avoid useless symmetric constraints.)
  41 :- sol(X,Y1,S), sol(X,Y2,S), Y1 < Y2.
  42 % One symbol per row. (X1 < X2 stands for X1 <> X2, to avoid useless symmetric constraints.)
  43 :- sol(X1,Y,S), sol(X2,Y,S), X1 < X2. 
  44 
  45 % One symbol per box. lessThan (used in place of notEqual) avoids symmetric constraints.
  46 :- sol(X1,Y1,S), sol(X2,Y2,S), sameSubSquare(X1,Y1,X2,Y2), lessThan(X1,Y1,X2,Y2).
  47 
  48 % Hardcode boxes for 9x9
  49 subrange(X,1) :- X > 0, X <= 3, symbol(X), size(9).
  50 subrange(X,2) :- X > 3, X <= 6, symbol(X), size(9).
  51 subrange(X,3) :- X > 6, X <= 9, symbol(X), size(9).
  52 
  53 % Hardcode boxes for 25x25
  54 subrange(X,1) :- X > 0, X <= 5, symbol(X), size(25).
  55 subrange(X,2) :- X > 5, X <= 10, symbol(X), size(25).
  56 subrange(X,3) :- X > 10, X <= 15, symbol(X), size(25).
  57 subrange(X,4) :- X > 15, X <= 20, symbol(X), size(25).
  58 subrange(X,5) :- X > 20, X <= 25, symbol(X), size(25).
  59 
  60 sameSubSquare(X1,Y1,X2,Y2) :- subrange(X1,XS), subrange(X2,XS), subrange(Y1,YR), subrange(Y2,YR).
  61 
  62 
  63 % Differing pairs.
  64 % The presence of sameSubSquare(X1,Y1,X2,Y2) in the body limits the generation
  65 % only to the the relevant tuples.
  66 lessThan(X1,Y1,X2,Y2) :- X1 < X2, sameSubSquare(X1,Y1,X2,Y2).
  67 lessThan(X1,Y1,X1,Y2) :- Y1 < Y2, sameSubSquare(X1,Y1,X1,Y2).