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 \ n	3	4	5	6	7	8	9	10	11	12	13
squares	0	0	2	4	10	25	50	121	293	951	2606
cubes	0	3	1	6	34	42	103	526	993	2227
Fibonaccis	0	1	7	15	36	79	186	408	913	1848
powers of 2	1	5	5	14	22	37	61	128	175	340	540
primes in base 2	0	0	0	1	6	17	39	87	178	370	762
primes in base 3	0	0	1	0	1	0	0	0	1	3	12

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.