algorithm - 解决休闲方形包装问题

Question

我被要求找到一个 11x11 的网格，其中包含的数字可以读出 1,...,100 的平方。这里 read 意味着你固定起始位置和方向(8 种可能性)，如果你能连续找到数字 1,0,0,0,0,4，你就找到了 1,2,10,100 的平方和20.我做了一个程序(算法不是我自己的。我稍微修改了a program，它使用最佳优先搜索来找到解决方案但是它太慢了。有没有人知道更好的算法来解决这个问题？

#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

到目前为止，使用随机搜索我只找到了 92 个方格，其中有一个未使用的点(8 个缺失数字: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 

该算法基本上使用编码输入排列的解决方案(搜索空间为 100!)，然后将每个数字放在“最上面”的合法位置。解决方案的值(value)被衡量为放置的数字长度的平方和(更重视长数字)和剩余的“洞”数(IMO 增加洞的数量应该提高另一个数字的可能性)适合)。

代码根本没有优化，每秒只能解码几百个解决方案。在 196k 次尝试后找到了当前解决方案。

更新

目前采用这种方法的最佳解决方案是 93 没有空洞(7 个缺失数字: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 

这是一个解决方案(放置了所有 100 个数字)但是使用 12x12 网格(更容易)

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

已经发现使用真正的“蛮力”方法，从随机矩阵开始并在提高覆盖率时保持随机变化的数字。 该解决方案已由 Python 脚本自动生成的高度展开的 C++ 程序找到。

更新2

使用增量方法(即保持更复杂的数据结构，以便在更改矩阵元素时可以更新覆盖的目标数量而不是重新计算)我得到了更快的搜索(大约 15k 个矩阵/秒使用 Python 进行调查使用 PyPy 运行的实现)。

几分钟后，这个版本就找到了一个 99 的准解(仍然缺少一个数字):

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

更新 3

好的。一段时间后(不知道多少)同一个 Python 程序实际上找到了一个完整的解决方案(确实有几个)......这是一个

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

搜索程序can be found here ...