Solving a recreational square packing problem

Question

I was asked to find a 11x11-grid containing the digits such that one can read the squares of 1,...,100. Here read means that you fix the starting position and direction (8 possibilities) and if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the squares of 1, 2, 10, 100 and 20. I made a program (the algorithm is not my own. I modified slightly a program in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=331&t=288507&start=20 ) which uses best-first search to find a solution but it is too slow. Does anyone know a better algorithm to solve the problem?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <vector>
#include <algorithm>

using namespace std;
int val[21][21];//number which is present on position
int vnum[21][21];//number of times the position is used - useful if you want to     backtrack

//5 unit borders
int mx[4]={-1,0,1,0};//movement arrays
int my[4]={0,-1,0,1};

int check(int x,int y,int v,int m)//check if you can place number - if you can, return    number of overlaps

{
int c=1;
while(v)//extract digits one by one
{
    if(vnum[x][y] && (v%10)!=val[x][y])
        return 0;
    if(vnum[x][y])
        c++;
    v/=10;
    x+=mx[m];
    y+=my[m];
}
return c;
} 

void apply(int x,int y,int v,int m)//place number - no sanity checks
{
while(v)//extract digits one by one
{
    val[x][y]=v%10;
    vnum[x][y]++;
    v/=10;
    x+=mx[m];
    y+=my[m];
}
}

void deapply(int x,int y,int v,int m)//remove number - no sanity checks
{
while(v)
{
    vnum[x][y]--;
    v/=10;
    x+=mx[m];
    y+=my[m];
}
}

int best=100;
void recur(int num)//go down a semi-random path
{
if(num<best)
{
    best=num;
        if(best)
        printf("FAILED AT %d\n",best);
    else
        printf("SUCCESS\n");
    for(int x=5;x<16;x++)           // 16 and 16
    {
        for(int y=5;y<16;y++)
        {
            if(vnum[x][y]==0)
                putchar('.');
            else
                putchar(val[x][y]+'0');
        }
        putchar('\n');
    }
    fflush(stdout);
}
if(num==0)
    return;
int s=num*num,t;
vector<int> poss;
for(int x=5;x<16;x++)
    for(int y=5;y<16;y++)
        for(int m=0;m<4;m++)
            if(t=check(x,y,s,m))
                poss.push_back((x)|(y<<8)|(m<<16)|(t<<24));//compress four numbers into an int
if(poss.size()==0)
    return;

sort(poss.begin(),poss.end());//essentially sorting by t
t=poss.size()-1;
while(t>=0 && (poss[t]>>24)==(poss.back()>>24))
    t--;
t++;

//t is now equal to the smallest index which has the maximal overlap
t=poss[rand()%(poss.size()-t)+t];//select random index>=t
apply(t%256,(t>>8)%256,s,(t>>16)%256);//extract random number
recur(num-1);//continue down path
}

int main()
{   
srand((unsigned)time(0));//seed
while(true)
{
    for(int i=0;i<21;i++)//reset board
    {
        memset(val[i],-1,21*sizeof(int));
        memset(vnum[i],-1,21*sizeof(int));
    }
    for(int i=5;i<16;i++)
    {
        memset(val[i]+5,0,11*sizeof(int));
        memset(vnum[i]+5,0,11*sizeof(int));
    }
    recur(100);
}
}

Answer 1

You've got 100 numbers and 121 cells to work with, so you'll need to be very efficient. We should try to build up the grid, so that each time we fill a cell, we attain a new number in our list.

For now, let's only worry about 68 4-digit numbers. I think a good chunk of the shorter numbers will be in our grid without any effort.

Start with a 3x3 or 4x4 set of numbers in the top-left of your grid. It can be arbitrary, or fine-tune for slightly better results. Now let's fill in the rest of the grid one square at a time.

Repeat these steps:

• Fill an empty cell with a digit
• Check which numbers that knocked off the list
• If it didn't knock off any 4-digit numbers, try a different digit or cell

Eventually you may need to fill 2 cells or even 3 cells to achieve a new 4-digit number, but this should be uncommon, except at the end (at which point, hopefully there's a lot of empty space). Continue the process for the (few?) remaining 3-digit numbers.

There's a lot room for optimizations and tweaks, but I think this technique is fast and promising and a good starting point. If you get an answer, share it with us! :)

---

Update

I tried my approach and only got 87 out of the 100:

10894688943
60213136008
56252211674
61444925224
59409675697
02180334817
73260193640
.5476685202
0052034645.
...4.948156
......4671.

Answer 2

Some ideas off the top of my head, without investing much time into thinking about details.

I would start by counting the number of occurrences of each digit in all squares 1..100. The total number of digits will be obviously larger than 121, but by analyzing individual frequencies you can deduce which digits must be grouped on a single line to form as many different squares as possible. For example, if 0 has the highest frequency, you have to try to put as many squares containing a 0 on the same line.

You could maintain a count of digits for each line, and each time you place a digit, you update the count. This lets you easily compute which square numbers have been covered by that particular line.

So, the program will still be brute-force, but it will exploit the problem structure much better.

PS: Counting digit frequencies is the easiest way to decide whether a certain permutation of digits constitutes a square.