[第30期]填充数字（已结）

agstick

答题要求：
  在N*N的区域上（1≤N≤10），填入1，2，…，N*N共N*N个数，使得任意两个相邻的数之和为素数。
例如：当N=2时，有：
1 2
4 3
为了简便，左上角的格子里必须填数字1。
在O3单元格输入：N，结果填充到A1开始的区域内
如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“无解！”。

评分标准：
结果正确，且代码运行流畅，得2分，优秀答案另加分。

答案发送至：agstick@126.com，并跟贴占位，请勿在跟贴中直接发答案。

 

[此贴子已经被作者于2007-12-31 16:36:03编辑过]

willin2000

答案发送至agstick@126.com，跟贴占位.

 

结果正确。

[此贴子已经被agstick于2007-12-30 20:35:45编辑过]

彭希仁

答案发送至agstick@126.com，跟贴占位.

想不到更好的方案来解决此问题只能用穷举的土办法,速率慢啊.

 先填第一行在填第一列，思路正确，但是第一行与第一列之和不是最小。

[此贴子已经被agstick于2007-12-30 19:43:00编辑过]

Luckyguy2008

已经发到版主的邮箱，速度非常慢[em04]

 

结果正确，速度还可以。

[此贴子已经被agstick于2007-12-30 19:45:01编辑过]

BobPan

不好意思，理解错误，重做时可能因为解题思路有问题，太慢，弃权！

期待正解！向各路高手致敬！

 

出现相邻两数不为素数，不符题意，不得分。

[此贴子已经被agstick于2007-12-30 19:47:13编辑过]

jackysyh

oh my god, 感觉已经挺优化的了，但速度还是太慢了，只能跑到4， 4 以后的速度掺不忍睹。

答题时间已过。

[此贴子已经被agstick于2007-12-31 16:33:35编辑过]

agstick

此题要想出解法不难，关键是速度如何优化，当n>5以后，解空间是非常庞大的。

此题适用的算法为回溯法，所谓回溯法，就是先填一个数，如果ok，扩展（下一格），如果不满足条件，换下一个数。如果所以数都不满足条件，退回到上一格（回溯）。用回溯法求其中一个解，很快，若要求所有满足条件的解，速度可能会很慢。此题要求求出第一行与第一列之和最小的解，因此要搜索所有解。此时需要优化，否则太慢。

优化方案：

1、建立素数表，通过查表判断之和是否为素数。

2、优先填充第一行、第一列。

3、注意到此素数矩阵是奇偶相间，因此可以以2为步长循环。

4、对已经用过的数，进行标记。

5、求出其中一个解后，直接从第一行或第一列开始回溯，跳过非第一行和第一列的回溯。

6、当第一行第一列之和达到极限最小，（n为奇数时，n×（2n－1）；n为偶数时，n×（2n－1）+1），结束，直接输出解。

有关回溯法，可参看附件，也可到网络上搜索相关资料。

参考答案：

抱歉，原附件上传错误，特此更正！

[此贴子已经被作者于2008-1-1 20:19:07编辑过]

jackysyh

我不知道是不是我电脑问题，斑竹的程序当等于6的时候好象不对，出现两个1，而且我用5的时候，似乎第一列+第一行并不是最小的，我是用willin2000 斑竹的程序对比的

当=5时， 斑竹程序第一列+第一行=85

willin2000 斑竹，第一列+第一行=55

[em09]

抱歉，附件传错，以更正。

[此贴子已经被agstick于2008-1-1 20:22:21编辑过]

彭希仁

有道理,此题的关键就是速度的优化不好搞啊.

willin2000

在我的程序中加上agstric的第6条优化方法：“6、当第一行第一列之和达到极限最小，（n为奇数时，n×（2n－1）；n为偶数时，n×（2n－1）+1），结束，直接输出解。”后，我的速度n=8,10还是较慢，后来发现原来中间搜索中使用先列后行比先行后列的数度要快. 虽然这个是偶然性的,但概率较大, 相比较而言符合"极限最小"的概率反而小.

我的原程序使用了的agstic优化方法1/2/4/5, 第3条我直接了使用查素数表和优化起始指针的方法,感觉比步进2的方法还要快些.(在N=10,耗时只有1/4)

附件加上了第6条方法,在8和10时速度确实快了很多. 还使用先列后行,在6/7/9时速度得到明显改善.