我被要求找到一个包含数字的11x11网格,以便人们可以读取1,...,100的正方形.这里的读取意味着您可以修复起始位置和方向(8种可能性),如果您可以连续找到数字1,0,0,0,0,4,则可以找到1,2,10,100的正方形我做了一个程序(算法不是我自己的.我稍微修改了一个程序,它使用最佳优先搜索来找到解决方案,但速度太慢.有没有人知道更好的算法来解决问题？
#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);
}
}
到目前为止使用随机搜索我只得到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!)溶液中,然后放置在"层次最高的"法律地位的每个号码.解决方案的价值是所放置数字的长度的平方和(以更加重视长数)和剩余的"空洞"的数量之和(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++程序找到了此解决方案.
使用增量方法(即保持更复杂的数据结构,以便在更改矩阵元素时,覆盖的目标数量可以更新而不是重新计算)我得到了更快的搜索(大约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
好.经过一段时间(不知道多少)相同的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
搜索程序可以在这里找到 ......
你有100个数字和121个单元可以使用,所以你需要非常高效.我们应该尝试建立网格,这样每次填充单元格时,我们都会在列表中获得一个新数字.
现在,让我们只担心68个4位数字.我认为较短的数字中的很大一部分将在我们的网格中毫不费力.
从网格左上角的3x3或4x4数字开始.它可以是任意的,或微调以获得更好的结果.现在让我们一次一个方格填充网格的其余部分.
重复这些步骤:
最终你可能需要填充2个单元格甚至3个单元格以获得一个新的4位数字,但这应该是不常见的,除了最后(此时,希望有很多空白空间).继续(少数？)剩余的3位数字的过程.
优化和调整有很大的空间,但我认为这种技术快速而有前途并且是一个很好的起点.如果您得到答案,请与我们分享!:)
我尝试了我的方法,只有100个中的87个:
10894688943
60213136008
56252211674
61444925224
59409675697
02180334817
73260193640
.5476685202
0052034645.
...4.948156
......4671.