%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ECLiPSe library for solving "crossfigures" puzzles.
%
% "Crossfigures" puzzles correspond to problem 21 in the CSPLib.
% See www.csplib.org for more details.
%
% Particular instances can be found at thinks.com/crosswords/xfig.htm.
%
% This module written by Warwick Harvey, IC-Parc, wh@icparc.ic.ac.uk.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- module(crossfig).

:- export across/6, down/6, init_matrix/3, print_matrix/1.
:- export square/1, prime/1.

:- lib(fd).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The problem is modelled using an array Matrix' to represent the puzzle
% "board".  A second array Template' is used to indicate whether each
% element of Matrix' should contain a digit or should be blank.  This
% information can also be used to perform some integrity checks, to help
% catch errors in the expression of a problem.
%
% The multidigit numbers used in the "clues" (1 across, 7 down, etc.) are
% set up using the predicates across/6' and down/6', which relate these
% numbers to the digits in Matrix'.  Once these are all set up,
% init_matrix/3' should be called to complete the initialisation of
% Matrix', before the clue constraints are added.
%
% Also provided are a number of predicates which are useful for
% expressing clue constraints such as "A square number" and "A prime
% number".
%
% See one of the accompanying problem modules (cf*.pl) for an example of
% how it all works.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
% across(Matrix, Template, Across, Len, Row, Col):
%	Constrains Across' to be equal to the number represented by the
%	Len' digits starting at position (Row, Col) of the array Matrix'
%	and proceeding across.
%	Template' is used for integrity checking, as well as for collecting
%	information about which elements of Matrix' should contain digits,
%	and which should be empty.
%

across(Matrix, Template, Across, Len, Row, Col) :-
% Constrain Across' to be equal to the corresponding digits.
(
for(I, Len-1, 0, -1),
fromto(1, Mult, NewMult, _),
fromto(0, SumIn, SumOut, Across),
param(Matrix, Row, Col)
do
Elem is Matrix[Row, Col + I],
Elem :: [0..9],
SumOut #= SumIn + Mult * Elem,
NewMult is Mult * 10
),

% Integrity checks.
dim(Template, [_Height, Width]),
(
Template[Row, Col .. Col + Len - 1] :: 1,
( Col > 1            -> Template[Row, Col - 1] :: 0   ; true ),
( Col + Len =< Width -> Template[Row, Col + Len] :: 0 ; true )
->
true
;
printf(error, "Crossfigure integrity violation adding "
"an across figure of length %d,%n"
"starting at (%d, %d)%n",
[Len, Row, Col]),
abort
).

%
% down(Matrix, Template, Down, Len, Row, Col):
%	Constrains Down' to be equal to the number represented by the
%	Len' digits starting at position (Row, Col) of the array Matrix'
%	and proceeding down.
%	Template' is used for integrity checking, as well as for collecting
%	information about which elements of Matrix' should contain digits,
%	and which should be empty.
%

down(Matrix, Template, Down, Len, Row, Col) :-
% Constrain Down' to be equal to the corresponding digits.
(
for(I, Len-1, 0, -1),
fromto(1, Mult, NewMult, _),
fromto(0, SumIn, SumOut, Down),
param(Matrix, Row, Col)
do
Elem is Matrix[Row + I, Col],
Elem :: [0..9],
SumOut #= SumIn + Mult * Elem,
NewMult is Mult * 10
),

% Integrity checks.
dim(Template, [Height, _Width]),
(
Template[Row .. Row + Len - 1, Col] :: 1,
( Row > 1             -> Template[Row - 1, Col] :: 0   ; true ),
( Row + Len =< Height -> Template[Row + Len, Col] :: 0 ; true )
->
true
;
printf(error, "Crossfigure integrity violation adding "
"a down figure of length %d,%n"
"starting at (%d, %d)%n",
[Len, Row, Col]),
abort
).

%
% init_matrix(Matrix, Template, Vars):
%	Finishes the initialisation of Matrix', returning a list of all
%	the variables in it in Vars'.
%	Template' is used to determine which elements of Matrix' should be
%	variables, and which ones should be blank.  Blank elements are
%	filled with a  '.
%

init_matrix(Matrix, Template, Vars) :-
dim(Matrix, [Row, Col]),
(
for(I, 1, Row),
fromto([], Vars1, Vars4, Vars),
param(Matrix, Template, Col)
do
(
for(J, 1, Col),
fromto(Vars1, Vars2, Vars3, Vars4),
param(Matrix, Template, I)
do
T is Template[I, J],
Elem is Matrix[I, J],
( var(T) ->
T = 0
;
true
),
( T = 0 ->
Elem = ' ',
Vars3 = Vars2
;
Vars3 = [Elem | Vars2]
)
)
).

%
% print_matrix(Matrix):
%	Prints Matrix' in a readable format.
%

print_matrix(Matrix) :-
nl,
(
foreacharg(Row, Matrix)
do
write(' '),
(
foreacharg(Elem, Row)
do
write(Elem)
),
nl
).

%-------- Useful constraints for crossfigure puzzles --------%

%
% square(N):
%	Constrains N to be a square number.
%

square(N) :-
N #= T * T.

%
% prime(N):
%	Delays until N is ground, and then succeeds if and only if it is
%	prime.
%

prime(N) :-
( nonvar(N) ->
is_prime_2(2, N)
;
suspend(prime(N), 2, N->inst)
).

is_prime_2(Q, N) :-
N mod Q =\= 0,
( Q * Q < N ->
Q1 is Q + 1,
is_prime_2(Q1, N)
;
true
).