# Problem of the Month (January 2002)

This month we explore square crosswords. Given a polyomino, we can think of it as a cross-number puzzle. We try to put a digit in each box so that every number formed by reading across rows or down columns is square. Since there are many ways to do this, we are interested in those polyominoes that have a UNIQUE way to fill the boxes so that all entries are square.

Here's the fine print. We do not allow leading 0's. Using a given square more than once is okay. We don't allow crosswords that build on already unique solutions. We do not require that single digit rows and columns be square.

What are some other square crosswords? What's the largest square crossword you can find? How about cube crosswords? Fibonacci crosswords? I'll pay \$10 to the first person who finds a prime crossword.

# ANSWERS

Brendan Owen counted the number of crossword grids up to 18 boxes. He suggested that perhaps the search for square crosswords could be expanded into 3 dimensions.

Joseph DeVincentis found the smallest cube and Fibonacci crosswords.

Claudio Baiocchi found the first prime crossword in base 2. Berend Jan van der Zwaag found several more. I found the first base 3 prime crossword, and then Berend Jan van der Zwaag found several more.

## Small Square Crosswords

```   81    81    841    144    2    144
169    64   196   169     81   64
9                196    1
```

## Square Crosswords With Every Square Checked

```   841   11236    49      49     144    121    8649    11236   324 16
196   66564   400   84100   64009   34596   47961   66564   659344
900   19600   4900    64 64   16 16    961       64

64     676   841       49      36      64    841     441   441
784    784   144      400    4624   37249    196   12996   9604
3249   324     144   16900   3844    225     400    25       289
64     64       49   64      64      49      900    16       49

3136    3481      16    16      16      144   256    1521    3136
6724    2916   35344    841     576    4489   5041   4096    8464
64    64      6724    6400   43264   3844     400   441    144
49    49       64     4900   961     64       100    16    64

64      441        49   544644   17161   5331481
49729   9801      400   200704   23104   4605316
256    4096     400   900601   29584   7022500
961      64   361              56644   6051600
64
```

## Small Cube Crosswords

```
6    2     216   9261    2 6     6     2      2     512   6
343   729   7      7     2744   2744   1728   2744    27   4096
7        7    7       5       4
```

## Small Fibonacci Crosswords

```
233     8    2 3   21      5     3  2   4181   2584   13      46368
4   1597   144    377   75025  4181    3 3   1 9     4181     4

2    55    89    233      3    2      2     610   1      3      3      4181   4181
34    55    89     7   2584    377   4181    4    4      4181   4181    4        4
13      5    7      7   1      13        3   34    4181      3     9     4        4
```

## Small Powers of Two Crosswords

```
16    3    3     256   512   128   4096   8192   1024
4   128   256     4    6    6        4    6     6

1    6  1  3 6    1       65536   16384   16384
32768   4096  2048   65536       4     2      4

5    512      1     5      1     5     8192   1024   8192
1      5   8192     1    1024   8192      5     5     2
128     6      8   1024     8     2        6     6     8
```

## Small Base Two Prime Crosswords

```
1       1     1      1     1       1     1       1     1
11   1011     11   1101    11    111    1011     0     0
111     11   1011    11    1101   1011   111      11    11
1011   1101
```

## Small Base Three Prime Crosswords

```              12             1     12
212  111    10   12  1  12 21    10   12 21  12 21  12  1
21  201  12112  20122  20122  12112  20102  10211  20122
1  21     21 12  21     21     21 12  111 1  21 122
2

1      12   12     12     12     12 12    1      111  111
12 21   1 10   11212  11212  20122  10121    212    21   201
20122   12112  1 111  1 111  21 10  111      201    21     111
21  2  111        12    21      21    1    111    111      201
201    201        1
```
Berend Jan van der Zwaag wrote a computer program to find all small prime crosswords in different categories. Most of the examples above are from him. He didn't find any prime crosswords in base 4 or higher. The counts for other categories are shown below:

## Number Of Crosswords With n Spaces

type \ n345678910111213
squares00241025501212939512606
cubes031634421035269932227
Fibonaccis0171536791864089131848
powers of 215514223761128175340540
primes in base 200016173987178370762
primes in base 3001010001312

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 1/27/02.