十二素数圈.概念

　　将1~12这12个自然数按某种规律围成一个圆圈,首尾相接,使得每相邻的两个自然数之和为素数,即质数.这个圈被称为十二素数圈.

十二素数圈.问题

　　可以想像这种圈应该不止一个,其中一个示例解如下:

　　1 – 6 – 11 – 2 – 5 – 8 – 9 – 4 – 3 – 10 – 7 – 12 – (1).

　　现要求给出一种算法,来输出任意一个或者多个解.如果无解则输出”无解”.

十二素数圈.算法

　　首先考虑12个自然数可以围成多少个不同的圆圈.如果数量较少的话,就可以使用暴力搜索来实现.因为是对称的圆圈,任意一个数都可以放在首位(即,不存在实际意义上的首位).假设将1放在首位上,那么第2位上可以放11个不同的数字,第3位上可以放10个不同的数字…第12位上可以放1个数字.以此类推,不同的放法一共有 11*10*…*1 = (11!) 这么多种.再考虑重复的情况,实际上每种不同的做法都会被算上两遍(左右对称),那么真正不同的做法数量应该为: (11!) / 2 = 19958400.接近两千万,虽然一般的计算机还是可以承受的,但是实现起来需要使用11层循环,并且在问题的规模稍稍增长时,比如总数为14,循环的规模就会增长很多.可见这个方法太死,并且不够实用.

　　比较实用的方法是,将这12个自然数构造成一个图(Graph),将十二素数圈的构建转换为图的遍历过程,这样就能利用图论中的搜索和回溯理论来解决问题.

　　考虑第一个数的情况.如果第一个数为1,为了保证相邻两个数的和为素数,那么它附近(左边和右边)只能是2,4,6,10,12中的两个,可见有效的选择并不多.这样就极大地限制了图的规模,便于后面进行遍历搜索.现在考虑构建这个图.将12个自然数看成是12个结点(Vertex),任意两个数,如果其和为素数,那么就在它们之间设置一条路径(Path),其长度即为两数之和.在这里,路径的长度并没有实际的意义,仅作为对路径的一种标记.按这种方法构建的图如下表所示(利用二维数组来存储):

　　


　　图1. 用二维矩阵存储的图

　　可见这是一个非常稀疏的矩阵,并且是按照主对角线完全对称的.

　　算法大概描述如下:

　　1. 任意选取一个结点放在素数圈的第一个位置上.以1为例子.

　　2. 在矩阵的第1行中顺序搜索有效路径(即长度大于0的值),并将目标结点放置在素数圈的第二个位置上.例子中目标结点为2,路径长度为3.

　　3. 删掉与结点1相关的所有路径(清零),包括第1行和第1列,都要清零,防止结点1再次被搜索到.

　　4. 以结点2为当前结点,重复步骤2~3,直至素数圈的长度达到12.

　　5. 打印素数圈.一轮结束.

　　在这个过程中,最容易遇到也是最大的一个问题就是,如果遇到无解的情况怎么办?这时就要使用回溯(Look Back Upon.百度的翻译)的算法了.回溯就是回头的意思.一条路走错了,碰到死胡同了,当然要回头,寻找前面曾经碰到过的岔路,去选择另一条路试试看.这就是回溯算法的原理.

　　在这个例子中,有几种情况需要回溯.

　　A. 碰到无解的情况.这是最常见的回溯条件.

　　B. 虽然能顺次将12个结点都找到,但第12个结点与第1个结点之和不是素数.也即,这个圈的首尾不能相接.这也表示搜索失败.

　　C. 完成一个解的搜索.因为我们的目标是找到所有解(或者一定数量的解),因此当完成一个解的时候,就需要回溯,继续去寻找下一个解.

　　D. 遇到重复解.因为素数圈是完全对称的,肯定会遇到重复解.这种情况需要舍弃.

　　历史就在反复的回溯中前进.如果有解,这种回溯的算法是一定可以找到它的,因为这本质上是一种深度优先的完全搜索.找到所有解并依次打印出来,这个问题就解决了.

　　在具体实现中,回溯过程需要注意很多细节,其中一个就是路径的恢复.由于前面一步走错了,但是当时并不知道,就把走过的路径都删掉了,到回溯时就会发现有用的数据已经被自己无情地移除了.此时需要进行路径的恢复工作.有两种可行的方法.其一为记录每次移除的路径,回溯时连路径一起回溯;其二为重新构建完整的路径数据(重新生成原始图),然后按照搜索的完成进度来依次删除前面用到过的路径.后者实现比较简单,但效率会稍低一点儿(整个搜索过程中需要反复地构建图).本程序中偷一下懒,使用后者.

十二素数圈.代码

　　


　　图2. 代码截图

　　


　　图3. 运行结果的最后一部分

　　编译环境: WinXP + MiniGW.