Consider the following puzzle, written by Richard I. Hess in the Brain Ticklers section of the Winter 2010 issue of The Bent of Tau Beta Pi. "Fill in the following cross-number puzzle with 13 different three-digit perfect squares. No leading zeros. Read top-to-bottom and left-to-right as in a crossword puzzle."
| A | B | C | D | E | F | G | H | |||
| I | J | K | L | M | N | O | P | Q | ||
| R | S | T | U | V | W | X | Y |
In the above diagram, each letter represents a single base-10 digit of a number. For example, the middle entry LMN represents a three-digit square, whose first digit L is nonzero, and whose second and third digits are M and N, respectively. The digits need not be distinct, but the entries must all be distinct.
We'd like to have a program that solves cross-number puzzles of this form, in which every entry in the puzzle is a distinct square integer. However, this one is pretty simple, so let's generalize it in several ways. First, let's not assume base 10, but instead solve the problem in other bases. Second, let's not assume the numbers are three-digit squares: the numbers can have any positive number of digits (though they must still be squares). Third, the user should be able to specify any rectangular puzzle layout, not just this particular one.
Write a predicate crossnum_puzzle(B,P) that takes two arguments. B is an integer giving the base; it must be at least 2. P is a list of lists of base-B digits, each giving an entry in the puzzle. The crossnum_puzzle(B,P) predicate succeeds if P is a valid solution to a Hess-style puzzle, that is, the members of P represent distinct base-B integers, each a perfect square, and each with a nonzero leading digit.
The digits in P may be logical variables; if so, crossnum_puzzle(B,P) fills in the logical variables with the solution that it finds. It is the caller's responsibility to ensure that there are no other logical variables in the arguments to crossnum_puzzle(B,P). If the predicate succeeds it must do so in such a way that its arguments are ground terms, that is, terms that do not contain any logical variables.
Your solution may invoke the builtin arithmetic predicates of standard Prolog, that is, is/2, =:=/2, =\=/2, </2, =</2, >/2, and >=/2. It may also invoke the builtin control constructs of standard Prolog, that is, true/0, fail/0, !/0, ,/2, ;/2, ->/2, call/1, catch/3, and throw/1. Your solution may not invoke any of the other standard predicates; for example, it can't invoke member/2 or length/2. You can define any auxiliary predicates that your solution needs, so long as these predicates invoke only the builtin predicates listed in this paragraph.
Submit a file named hess.pl. If any extra text information is needed, other than what's in the comments, please submit it as a separate text file. Please do not put your name, student ID, or other personally identifying information in your files.
The following session solves Hess's puzzle listed above, along with the same puzzle in base-9 and base-11, and one other puzzle in base-16. For all queries, the user has typed ";" once to get alternate solutions. There is only one solution for base 10, but there are at least two in base 11. When there are multiple solutions, your program can backtrack through them in any order. For the second puzzle, the query itself backtracks through all solutions; there are two.
$ gprolog
GNU Prolog 1.3.1
By Daniel Diaz
Copyright (C) 1999-2009 Daniel Diaz
| ?- ['hess.pl'].
compiling …
yes
| ?- crossnum_puzzle(10,
[[L,M,N], [D,L,U], [B,C,D], [S,T,U], [B,K,S], [I,J,K], [A,I,R],
[E,N,V], [E,F,G], [V,W,X], [G,O,X], [O,P,Q], [H,Q,Y]
]).
A = 8
B = 1
C = 6
D = 9
E = 2
F = 2
G = 5
H = 1
I = 4
J = 8
K = 4
L = 6
M = 2
N = 5
O = 7
P = 2
Q = 9
R = 1
S = 4
T = 4
U = 1
V = 6
W = 7
X = 6
Y = 6 ? ;
no
| ?- crossnum_puzzle(9,
[[L,M,N], [D,L,U], [B,C,D], [S,T,U], [B,K,S], [I,J,K], [A,I,R],
[E,N,V], [E,F,G], [V,W,X], [G,O,X], [O,P,Q], [H,Q,Y]
]).
no
| ?- crossnum_puzzle(11,
[[L,M,N], [D,L,U], [B,C,D], [S,T,U], [B,K,S], [I,J,K], [A,I,R],
[E,N,V], [E,F,G], [V,W,X], [G,O,X], [O,P,Q], [H,Q,Y]
]).
A = 2
B = 1
C = 2
D = 1
E = 3
F = 7
G = 1
H = 1
I = 7
J = 4
K = 9
L = 6
M = 0
N = 3
O = 4
P = 0
Q = 0
R = 5
S = 5
T = 1
U = 9
V = 4
W = 8
X = 4
Y = 0 ? ;
A = 2
B = 1
C = 2
D = 1
E = 3
F = 7
G = 1
H = 9
I = 7
J = 4
K = 9
L = 6
M = 0
N = 3
O = 4
P = 0
Q = 0
R = 5
S = 5
T = 1
U = 9
V = 4
W = 8
X = 4
Y = 0 ?
yes
| ?- crossnum_puzzle(16,
[[A,B,C,D], [E,F,G,H], [A,E], [B,F], [C,G], [D,H]]),
write([A,B,C,D,E,F,G,H]), nl, fail.
[3,2,12,4,1,4,4,0]
[14,12,6,4,1,4,4,0]
no
| ?-