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 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

Using a random search so far I only got to 92 squares with one unused spot (8 missing numbers: 5041 9025 289 10000 4356 8464 3364 3249)

1 5 2 1 2 9 7 5 6 9 5 
6 1 0 8 9 3 8 4 4 1 2 
9 7 2 2 5 0 0 4 8 8 2 
1 6 5 9 6 0 4 4 7 7 4 
4 4 2 7 6 1 2 9 0 2 2 
2 9 6 1 7 8 4 4 0 9 3 
6 5 5 3 2 6 0 1 4 0 6 
4 7 6 1 8 1 1 8 2 8 1 
8 0 1 3 4 8 1 5 3 2 9 
0 5 9 6 9 8 8 6 7 4 5 
6 6 2 9   1 7 3 9 6 9 

The algorithm basically uses as solution encoding a permutation on the input (search space is 100!) and then places each number in the "topmost" legal position. The solution value is measured as the sum of the squares of the lengths of the numbers placed (to give more importance to long numbers) and the number of "holes" remaining (IMO increasing the number of holes should raise the likehood that another number will fit in).

The code has not been optimized at all and is only able to decode a few hundred solutions per second. Current solution has been found after 196k attempts.

UPDATE

Current best solution with this approach is 93 without free holes (7 missing numbers: 676 7225 3481 10000 3364 7744 5776):

9 6 0 4 8 1 0 0 9 3 6 
6 4 0 0 2 2 5 6 8 8 9 
1 7 2 9 4 1 5 4 7 6 3 
5 8 2 3 8 6 4 9 6 5 7 
2 4 4 4 1 8 2 8 2 7 2 
1 0 8 9 9 1 3 4 4 9 1 
2 1 2 9 6 1 0 6 2 4 1 
2 3 5 5 3 9 9 4 0 9 6 
5 0 0 6 1 0 3 5 2 0 3 
2 7 0 4 2 2 5 2 8 0 9 
9 8 2 2 6 5 3 4 7 6 1 

This is a solution (all 100 numbers placed) however using a 12x12 grid (MUCH easier)

9 4 6 8 7 7 4 4 5 5 1 7
8 3 0 5 5 9 2 9 6 7 6 4
4 4 8 3 6 2 6 0 1 7 8 4
4 8 4 2 9 1 4 0 5 6 1 4
9 1 6 9 4 8 1 5 4 2 0 1
9 4 4 7 2 2 5 2 2 5 0 0
4 6 2 2 5 8 4 2 7 4 0 2
0 3 3 3 6 4 0 0 6 3 0 9
9 8 0 1 2 1 7 9 5 5 9 1
6 8 4 2 3 5 2 6 3 2 0 6
9 9 8 2 5 2 9 9 4 2 2 7
1 1 5 6 6 1 9 3 6 1 5 4

It has been found using a truly "brute force" approach, starting from a random matrix and keeping randomly changing digits when that improved the coverage. This solution has been found by an highly unrolled C++ program automatically generated by a Python script.

Update 2

Using an incremental approach (i.e. keeping a more complex data structure so that when changing a matrix element the number of targets covered can be updated instead than recomputed) I got a much faster search (about 15k matrices/second investigated with a Python implementation running with PyPy).

In a few minutes this version was able to find a 99 quasi-solution (a number is still missing):

7 0 5 6 5 1 1 5 7 1 6
4 6 3 3 9 8 8 6 7 6 1
3 9 0 8 2 6 1 1 4 7 8
1 1 0 8 9 9 0 0 4 4 6
3 4 9 0 4 9 0 4 6 7 1
6 4 4 6 8 6 3 2 5 2 9
9 7 8 4 1 1 4 0 5 4 2
6 2 4 1 5 2 2 1 2 9 7
9 8 2 5 2 2 7 3 6 5 0
3 1 2 5 0 0 6 3 0 5 4
7 5 6 9 2 1 6 5 3 4 6

UPDATE 3

Ok. After a some time (no idea how much) the same Python program actually found a complete solution (several ones indeed)... here is one

6 4 6 9 4 1 2 9 7 3 6
9 2 7 7 4 4 8 1 2 1 7
1 0 6 2 7 0 4 4 8 3 4
2 1 2 2 5 5 9 2 9 6 5
9 2 5 5 2 0 2 6 3 9 1
1 6 3 6 0 0 9 3 7 0 6
6 0 0 4 9 0 1 6 0 0 4
9 8 4 4 8 0 1 4 5 2 3
2 4 8 2 8 1 6 8 6 7 5
1 7 6 9 2 4 5 4 2 7 6
6 6 3 8 8 5 6 1 5 2 1

The searching program can be found here...

Answer 2

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.