Problem due to Richard I. Hess


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.

_ x _ _ _ x _ _ _ x _
_ _ _ x _ _ _ x _ _ _
_ x _ _ _ x _ _ _ x _
One way to begin is to list the three-digit perfect squares:
100
121 <- 1
144 <- 2
169 <- 3
196 <- 4
225
256
289
324
361
400
441 <- 10
484
529
576
625
676 <- 15
729
784
841
900
961 <- 19
We rule out 100, 400 and 900: if they were in the grid there would be a need for a leading zero on a cross-number. That leaves 19 possibilities and there are 13 slots in the array: choose 13 from 19 is possible in 27,132 ways.

We might rule out certain perfect squares because they have only a limited number in the remaining 18 cases with some leading or final digits, e.g., only 841 has an 8 in either of those positions. This would be a step towards moving from 19 to 13 perfect squares, but it isn't helpful since trial and error on 18 values still leaves an enormous number of failed cases.

We could try to put symmetry to work. The only such value, 484, might go in the center of row 2. But since left-to-right is a condition of the problem, there is no true symmetry among open slots. This also isn't helpful.

We can number the array slots. The rows are 1, 2, 3; columns range over 1, 2, ... , 11. Here is one way to do this:

Leftmost vertical (1); Top row L-R (2) (3); Rightmost vertical (4); 2nd Row L-R (5) (6) (7); Bottom row L-R (8) (9)

That numbering scheme is:
1: (1,1), (1,2), (1,3)
2: (3,1), (4,1), (5,1)
3: (7,1), (8,1), (9,1)
4: (11,1), (11,2), (11,3)
5: (1,2), (2,2), (3,2)
6: (5,2), (6,2), (7,2)
7: (9,2), (10,2), (11,2)
8: (3,3), (4,3), (5,3)
9: (7,3), (8,3), (9,3)
10: (3,1), (3,2), (3,3)
11: (5,1), (5,2), (5,3)
12: (7,1), (7,2), (7,3)
13: (9,1), (9,2), (9,3)

We can tabulate the values (Dig) that appear in leading digit (1st), middle (Mid) and final/last (Lst) place. This can go along with their number of occurrences among the 19 perfect squares. We use exponent to represent the number of occurrences.
Dig Lst Mid 1st
1: 15 _x_ 14
2: _x_ 26 23
3: _x_ _x_ 32
4: 44 43 42
5: 52 51 52
6: 64 63 62
7: _x_ 72 72
8: _x_ 83 81
9: 94 91 91


The observation that led to my solution is that there are two locations where an 8 ring appears in the diagram. Any four perfect square numbers filling an 8 ring take 4 from the 19, hence one filled 8 ring lowers the amount not yet placed in the diagram to 9, and all of the 9 are from the remaining 15. Because there are two 8 rings, if this is pursued only 5 more need to be placed and there remain 11 possibilities. Consulting the above 1-9 table and its three columns assists in finding a solution.

View A Solution
Questions

How many solutions are there to this problem? This question was answered by two people, Prof. Oleh Tretiak and Dr. Paul Eggert. The latter posted generalization of Hess' problem.
Is there any way to algorithmically step through the array locations and perfect squares to build up solutions?
Are any of the 19 perfect squares never part of a solution?
Which of the 19 perfect squares is part of the most solutions?
Which of the 19 perfect squares is part of the fewest solutions?
Are there any other configurations that permit filling in by perfect squares from the above set of 19 three-digit items [e.g., things like Hess's 2-D array but with: a) different dimensions, say 6x11; b) non-rectangular nature, say 3x11 with an additional small array attached; c) 3-D or higher, like a 3x3x3 where the 27 cells might include central black for the solid, and central black for the faces]?

Prof. Oleh Tretiak, Drexel University, has written a MatLab program. It leads to a conclusion that the above is the only solution to Hess' problem.

Dr. Paul Eggert, UCLA, wrote " ... I used the Hess puzzle you mentioned in a programming-language problem for CS 131 this quarter. You can see it here:

http://cs.ucla.edu/classes/winter10/cs131/hw/hw4.html

This assignment asks students to write a solver for any cross-number puzzle involving squares, in any base (not just base 10). For example, Hess's puzzle has only one solution in base 10, but two solutions in base 11."
http://www.cs.ucla.edu/~klinger/nmath/hess_2010.html, 5/3/2010 Version ©2010 Allen Klinger Problem Published Winter 2010, Tau Beta Pi Bent, Brain Ticklers
http://www.cs.ucla.edu/~klinger/brain_ticklers_W_2010001.pdf