021: Crossfigures

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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
	).