C语言名题精选百则——游戏问题

?

第8章游戏问题

问题8.1苞数阶魔方阵（MAGIC_O.C )

这个题目是填魔方阵（Magic Square)。所谓的n阶魔方阵，就是把1?n2个连续的正 整数填到一个的方阵中，使得每一列的和、每一行的和，以及两个对角线的和都相 等。在这个题目中，只填奇数阶的魔方阵，因为它好填，而且也一定会成功；如果不知道 如何填法，请看下面的说明。

?

【说明】

?

下面就是一个5阶的魔方阵，各列、各行与两条对角线（17、5、13、21、9)与（15、 14、13、12、11)的和都是 65。

17241815

23571416

46132022

101219213

11182529

?

在填表的时候，永远采用“往右上角移”的法则（可以用表8-1对照一番，看看是否 如此)，因此会碰到下面两个情况之一，如图8-1所示。

?

a)b)c)

?

图8-1

?

如图8-la所示是第一种情况，往右上角移之后还在表格内，这是最简单的一种；如果 现在是在第i列第j行，下一个（在右上角）的格子就会在第i-1列第j+1行。如图8-lb 所示是第二种情况，会从上方移出表格的边缘；如图8-lc所示是第三种情况，则是移出右 方的边缘。注意，因为是向右上角移，所以永远不会移出左方与下方的边缘。

?

如果是越出上方边缘，不妨把表格想成上下方是粘起来的，于是自右上方移出，就等 于移到右边第一行的最下方一格；于是，若有n列，现在是第i列第0行，于是下一个格

子就是第n-1列第j+1行（注意，C语言的脚码是0?11-1)，如图8-2所示。气图8-2如果从右边移出边界，可以把表格想象成左右相连，所以向右移的话，就会移到上一 列最左边的那一格，如果有II行，现在是在第i列第n-1行，于是下一格就是第i-1列第0 行了，如图8-3所示。了解移动方法之后，就可以填表了。事实上，还有一条规则，下面很快就会讲到。在 填表时是从第0列的中央位置，也就是第n/2行开始的，在那个位置上填写1。于是就依上 面的移动方式，每移动一格，就把下一个数填进去，因此若n是5，填完5个数之后得到 如图8-4所示情况。图8-4如果要填6的话，就会把原来的1盖过去了，因此就有了一条新规则——每填完n个 数之后，就往下移一格，再继续填表，‘如图8-5所示。
再填完5个，又会有相碰的情况，所以往下移一格再填表，最终就会得到最前面的5
个魔方阵了。
在数学上可以证明，n (奇数）阶魔方阵在填表时，每隔II个就一定会相碰一次，所以 就总共会相碰n次。换言之，就要下移n次了。这样，就学会如何填奇数阶魔方阵了，请图8-5问题8.2单偶数阶魔方砗(MAGIC_SE.C )会填奇数阶魔方阵之后，填2(2m+l)阶的魔方阵也就不是一件难事了。请写一个程序 填任何2(2m+l)阶的魔方阵，如果不知道方法，请看下面的说明。
【说明】
2(2m+l)阶的方阵可以等分成4个部分，每一个部分的长与宽都是2m+l:
%
2m+l 2m+lACDB
2m+l 2m+l于是A,B，C，D这4个部分就都是奇数阶的。接着先填入一些准备用的数值：’ x ；,
(1)在A中以奇数阶魔方阵的方式填入1?(2m+ l)2。
(2)在B中以奇数阶魔方阵的方式填入(2m+ l)2+l?2(2m + l)2。
(3)在C中以奇数阶魔方阵的方式填入2(2m+ l)2+1?3(2m + l)2。
(4)在D中以奇数阶魔方阵的方式填入3(2m+ l)2+1?4(2m + l)2。
接下来，这4个部分都要动点手脚才能达到魔方阵的境界，这也可以分成以下几个步 骤来处理。
(1)在A部分中间那一列的中央那一格起向左一共取m格，把它的内容与D的对应
部分互换。
(2)在A部分，除了中央列之外（中央列在上一步已经处理过了），每一列的头m个 元素与D的对应部分互换。
(3)在C部分，每一列的倒数m-1个元素（可能为0个）与B的对应部分互换。
(4)做完这几步，就会得到一个2(2m+ l)阶的魔方阵了。以m=l,亦即2(2m+l)=6
阶魔方阵为例，做完上面的前4步，得到816261924357212325492222720352833171015303234121416313629131811
接着，后3步的第1步是在A部分中央那一列正中央那一格起，向左取m-1个格子出 来，与D的对应部分互换，即5与32互换。第2步是把除了中央列外的其他列上前m个 元素与D的对应部分互换，即8与35、4与31互换。最后的第3不必做，由于m-1-O 的缘故，就等于没有作用。最后的结果如下。351626192433272123253192222720828331710153053412141643629131811
阶数是2(2m+l)的魔方阵，一般都叫做单偶数阶（Singly Even)魔方阵。问题8.3双偶数阶魔方阵(MAGIC_DE.C )偶数阶的魔方阵是个难题，但阶数是4的倍数（4m)时却很简单，约略比奇数阶的复 杂些而己。请写一个程序来填4m阶（m>0)的魔方阵。如果不知道这个方法，请看下面 的说明。
【说明】
4m阶的魔方阵讨以等分成4个部分，每一个部分的长与宽都是2m:2m 2mACDB
2m 2m
看P2m -2m方阵。在这个方阵中的4m2个元素中要在某些元素上面做个记号，方法是: 在偶数列（0，2,4，*")上的偶数行都做上记号；但对奇数列而言，则都在奇数行上做记号。接着，把A的记号以A与C的分隔线为准，以对称的方式转到C部分，因此A与C 就有了记号。下一步，则是以A与D的分隔线为准，以对称的方式把A与C中的记号分 别转到D与B去，所以最后的结果为：再其次，就是把1?(4m)2这些个连续的整数填到方阵中。填数字的顺序是：自上而下 一列一列地处理，在同一列上，则是从左向右一格一格地处理。不过，因为填数字的方式, 处理前2m列就够了，后2m列是由前2m列得来的。数字的选择如下：
(1)如果处理到的方格没有记号，就令下一个值为i，填在那里，接着找出那个以方 阵中心为准与目前这一格对称的方格，把(4m)2-i+l填到那。
(2)如果处理到的方格有记号，就找出那个以方阵中心为准的对称点，令下一个值为 i，填在那里，并且把(4m)2-i+l填在目前的这一格上。
如果按照这个方法去填8x8的方阵，再以上述的记号为准，把1?64填到方阵中，会 得到：642624559757956858660613631事实上，记号的做法并不一定如上述那么呆板，只要做到（在A部分）每一列与每 行上面都有m个记号就行了。因此就2m=4而言，有：****本****这几个都是合理的做法。
写程序的时候应注意脚码的运用方式，以及避免多余的运算与记号。这一类型的魔方 阵一般叫做双偶数阶—oubleEven Order)魔方阵。问题8.4 N后问题公式解（N_QUEEN1.C )8后问题（Eight Queen Problem)是指在一个8x8的西洋棋盘上要如何放置8个皇后棋 且不会互相吃到对方；皇后棋可以吃掉任何它所在的那一列、那一行，以及那两条对角线 (米字型）上的任何棋子。信不信有一道公式对于每一个n>3而言，在nxri棋盘上都可以 找出“一个”n后问题的解？请依下面的说明写一个程序，读入n,把一组解显示出来。
【说明】
不相信也不行，因为的确有此公式存在。CF.Gauss这位数学奇才把8后问题数学化， 想要找出一个可以得到所有解的公式，但却没有成功，不过后人借助计算机的帮助，倒是 找到了一组公式。对于n>3而言，在nxn棋盘上的某一组解可以用该公式表示出来。这一 组公式可以分成4个部分，在下面，k是正整数，换句话说，k=l，2,3，…，而n是棋盘的列 数与行数。
(1)当n是6k-2或6k的形式时，解答是由下面两组坐标点构成：
={(2i,i)ll^i^-n}
2(2i —l，一n + i)ll?-n} 2 2A(2)当n是6k-l或6k+l的形式时，解答是由下面两组坐标点构成
={(2i，i)ll?l (n-1)}
B. =W2i-l，去(n-l) + i)ll?| (n + 1)}
(3)当n是6k+3的形式时，解答是由3组坐标点构成：
c^ja^-ixc^icn-Dxc^n)}C2 ={(2i + 2，i)ll ?（n — 3)}
2^C3 =|(2i + 3，(n — l) + i)ll (n — 3)}
(4)当n是6k+8的形式时，解答是由下列4组坐标点构成：
Dy — |^(2i— l,~n — 2 + i)ll 3}
D2=i(2，n)，(4，2)，(6，n —1)}
D3 ={(2i + 5,i + l)ll ?(n — 3)}
2
D4 ={(2i + 6，金n + l + i)ll?| (n-3)}
(5)当n=8时，任选一组8后问题的解答就行了，使用：
D； ={(2i，i)ll?4}
Da2 ={(1,6), (3,5), (5,8), (7,7)}
以上的所有坐标点都从1算起。问题8.5 N后问题递归解(N^QUEENR.C )请写一个程序，读入一个值n表示棋盘的大小，然后求出nxn格棋盘上放n个皇后棋 且不会相互吃掉对方的所有解答。
【说明】
这是广义的N后问题，因为所要求的是“所有”解答，而不单是其中的一组（见上题), 对大多数会运用递归的人来说，这个题目反而容易做些。这一类型题目的解法通常要用到 回溯（Backtrack)的技巧——不管用递归还是不用递归都是如此，虽然会浪费时间，但多 半会找到解答。
回溯的技巧通常都以下面的面目出现，如程序8-1所示。【程序】S。{目前可以用得到的位置；
WHILE S <> {} DO BEGIN
取出S中一个元素，令为s;
IF S可以安全使用THEN BEGIN
定出S己经使用；
IF还可以从S再进一步THEN用S调用自己 ELSE IF已经有了答案THEN 显示答案；
把s定成没有在使用；
END;
END;
采用这种方法（并非是最好的方法），用S来记录在目前可以使用的一些位置，接下来 的WHILE-DO中就一个接一个地检查它们。如果查到的是s，那么第一件事就是看看可 不可使用s;如果可以，就把s标上已经使用，而它很可能就是解答之一。接着如果从s起 还可以再向前走，于是就用s作目前的立足点，调用上面的程序进入下-层的工作。如果 到了 s就已经有了一个解答，那就把它显示出来。如果只要一个结果，这就是停止工作的 时候了；但若要其他答案，就得继续执行。
无论如何，当IF…THEN…ELSE做完之后，那就表示s以下的内容都已经做过了，就 可以试下一个s。首先把目前的s定成没有在使用，这一点十分重要，因为若不做这一步， 在往后试其他位置时就可能会发生问题。做完之后，回到WHILE"*DO开头，取出下一个
s；就这样，一直循环到S变成空集合为止，如图8-6所示。
/图8-6以4x4的棋盘为例，上面就是工作过程。在同一列上的棋盘就是在同一层次中的递归。 每一个S集合都是{1，2，3，4},表示棋盘上的4列，而“可以再进一步？ ”的意义则是向右 移一行。在开始的时候，主程序或其他程序给上面的片段的信息是“从第一行开始”，因此 就到达1的所在，自然(1，1)这一格没有问题，而且还可以右移，于是就调用自己去处理下 一行，这就进到2。进入第二层递归之后，S还是{1，2,3，4},但1不能用，因为与上一层所 放位置的棋子互相干扰；2也不能用，因为在对角线，但3可以了，因而把棋子放在(3，2) 位置，接着再调用自己，把第三行交给第三层的递归去处理。第三层递归在试完1，2，3，4之后发现无一可用，因此回到第二层，这就是IF…THEN… ELSE的下一行叙述所在，把原来放下去的数据——亦即(3,2)定成没有使用，再取出S中的 下一个元素；由于原来是s=3，现在就去试s=4，这就是图8-6中标了 3的地方。接着把棋 子放到(4，2)所在，又调用下一层（第三层）递归，得到4位置的结果，但是从该位置进入 第四层递归时，S={1，2，3，4}中就没有可用的元素了，所以就倒退回第三层；第三层中8=3，4 都不能用，前者与对角线(1，1)或(4，2)冲突，后者则与(4，2)冲突，但因为这两个都试完了， 所以只能回到第二层。在第二层，s=4也是最后一个，因而回到第一层。在第一层，现在 s=l,不妨试下一个s=2;把上面的动作再反复，就会得到一个解答；其他的部分在图中没 有画出来，但相信应该有能力完成它。
现在，看完此例，请将这个观点转化成程序。要如何测试不在同一列、同一行、同一 (正、反）对角线呢？问题8.6武1：巡逻（KNIGHT.C )在西洋棋中的武士（Knight)与象棋的马相似，走的都是L形的路，请写一个非递归 的程序，输入一个表示棋盘的大小值n，再输入一个起点的坐标，找出一条从第一格起可 以让武士棋走完n2格而不重复的路径。请问，找出的路径会回到起点吗？什么时候一定做 不到？
【说朋】
如图8-7所示说明了武士棋的可能走法。????X???鲁?
图8-7图8-7中X表示目前的位置，下一步则可以到达任何一个圆点的所在，只要它在棋盘 上。如果输入一个起点，请问：从此点起，一个武士棋有没有办法把棋盘上的每一格都走 遍而不重复。一个更难的问题是，武士棋能否回到出发点？这就是所谓的武士巡逻问题 (Knight Tour Problem),但这个题目并不要求武士棋一定能够回到起点。
与8后问题一样，用回溯的技巧是不难写成一个递归程序的，但却不希望用递归方法， 请试试看。问题8.7环游担界（HAMILTON.C )假设有一张地图，城市与城市之间有道路相连，请写一个程序，在这份地图中找出一 条把每一个城市都只走一次而不重复，并且还会回到起点的路线；如果找不出这条路线， 也请报告这个现象。这个问题就叫做Hamilton循环（Hamilton Cycle)问题。
【说明】
地图如图8-8所示。
它有10个城市（1?10)，很明显地它就有一条每一个城市都走一次，而且也只走一次 的路径，不但如此，还会回到起点。不过并不是每一个图都有此等路径，下面就是这样的 一个例子，如图8-9所示。图8-8图8-9如果从1起到达2之后，不论是到3还是到4,都无法回头到达另一个点。
这个问题并没有快速的解法，应该试一试用递归（或非递归）的回溯技巧。另外，假 设一个合适的输入方式是很重要的；在本书的光盘中有两个文件HAM.IN1与HAM.IN2, 可以帮助进行测试，前者有题目中所提的路径，后者则无。文件的输入格式是这样的：第 一列上是一个值，代表一共有多少个城市；往后的每列都有两个数，分别表示在一条路上 两端的城市，最后用两个0作结束。于是，上面没有环绕一周的路径的图，就可以写成如 下的输入：4
1
2
2
02
3
4 0还有一点值得提醒：在图七8中若有这样环绕一周的路径的话，从哪一个城市出发实在没有差异；但若没有此等路径存在，从哪一个城市出发也都不会有的。在程序中仔细想 想，用什么方法才能表示城市与城市之间相通的关系呢？
最后HAM.IN1与HAM.IN2如图8-10及图8-11所示。图 8-1023图 8-11问题 8.8 —笔画（EULER.C )请设计一个可以画一笔画的程序，在程序中应该想到要如何设计合理的数据结构，以 及如何表示一笔画的动作。
【说明】
一笔画起源于1736年Leonhard Euler对Konigsberg7桥问题的解答。东普鲁士古城 Konigsberg被一条叫做Pregel的河横穿而过，因而为了交通需要而建了 7座桥，它们的位 置如图8-12所示。
城中的人一直想找出有没有办法把每一条桥都走过，但却都只经过一次。在1736年 Euler的文章中，他把河的两岸、河中两个小岛用4个点代替，而把连接用的桥通过两点之 间的线段来表示，如图8-13所示。图 8-13图 8-12Euler指出，研究这个图就足够了。对于一个点而言，如果有奇数（或偶数）条线经过 它，这个点就叫做奇点（或偶点）。Euler证明（其实并不完全)：
(1)如果图中没有奇点，那么就一定可以从任何一个点出发，走遍每一条边而回到起 点，并且每一条边都只经过一次。下面就是一个例子，如图8-14所示。图中A、B、C、G有4条边经过，E与F有两条边，D有6条边，都是偶数，可以从 任一点出发而回到起点，而且每一条边都只经过一次；比如A—B—D—G—F—E—G—D —C—A—B—D—C—A就是一^种走法。
(2)如果图中有两个奇点（奇点一定有偶数个），那么从其中1个奇点出发，一定可 以把每一条边都走一次而不重复，最后回到另一个奇点。图8-15就是一个例子，C与E就 是仅有的两个奇点，走法如下：C—D—F—A—E—C—B—A—D—B—E。图 8-14图8-15(3)如果奇点数目大于2，就不可能有一笔画的走法。正因为如此，7桥问题就是不 可解的，因为A、C与D各有3条边，而B有一条，因此全都是奇点。
有多少条边经过某一个点，通常都叫做那一个点的次数。当走一笔画时，如果经过一 个次数是偶数的点，那么进入那一个点之后是一定有一条边可以离开的，原因就是进入该 点用一条边，但该点是个偶点，用了这一条边之后就是个奇点，所以就一定会有一条边可 以出去（1，3，5，7___是奇数）。这是在写作程序时的一个有用的观念。但是若进入的是一个奇 点那就有困难了，因为进入时用了一条边，剩下来的就可能有0 (0，2，4，…算是偶数）条边， 就无从离开。好在因为只有两个奇点时才能画一笔画，所以从其中一个奇点走到另一个奇 点去之后，两者各少了一条边，剩下来的不就全都是偶点了吗？
请用这个观点来编写程序；在程序中或许要有一个数据结构，记录点与点之间的连接 情况，而且，也要记录下每一个点的次数，另外参考一下HAMILTON.C这个找环游世界的 路径的程序或许会有点帮助。问题8.9菲递归河内之塔（HANOIJLC )河内之塔（Towers of Hanoi)是一个在入门书籍中常见的例题或习题，它是说：有3 根柱子，1、2与3，在柱子1上串了从上到下编号是1，2，…,n的圆片，号码小的圆片也小。 问题是，请写一个程序，把柱子1上的圆片搬到柱子3去。在搬的时候有3个要求：第一， 每次只能搬一个圆片；第二，要搬的圆片得从某个柱子取出，并且放到另一根柱子上；第 三，任何时刻、任何柱子上的圆片，从上到下都是从小到大排列。书上的解法都是递归的， 请写一个非递归且不用堆栈来仿真的程序。如果用教科书中的解法，那么递归是个非常好且效率非常高的技巧，程序大致如程
序8-2所示。
【程序】
程序8-2
void tower(int n, int start, int mid, int end) if (n == 1)
print{"Move disk %d from %d to %d",n, start, end); else {
tower(n-1, start, end, mid);
print("Move disk %d from %d to %d",n, start, end); tower(n-1, mid, start, end);这个观点是，先把在start柱子上的n-1个圆片搬到mid柱子上去（用end柱子作 中继站），于是在start柱子上就留下3在最下方，也就是最大的一个圆片第n号，把它 从start搬到end去（见printf);现在的情况是，最大的已经到了目的地，但在上方的第 1?n-1号还停留在mid柱子上；第三步就是把mid上的n-1个圆片搬到end柱子上， 而用start柱作中继站。当然，start、mid、end就是题目中的3根柱子，n是要搬的圆片 数目。
递归的解不但漂亮，而且容易懂；不过了解了递归解法之后，能够由它而发展出一个 非递归的解吗？当然，用堆栈来仿真并不是所期望的，应该把递归动作中在什么时候搬那 一个圆片，从何处搬到何处这一层关系弄清楚，那么问题就不难了。问题8.10生命游戏(LIFE.C )请写一个模拟生命游戏（Game of Life)的程序；如果不知道所谓生命游戏，请看下面
的说明。
【说明】
生命游戏是一个很简单，但却是很有趣的程序习题。在一个四周都可以延伸到无限的 棋盘上的某个格子中会有一个有机体。每一个有机体在时间t时，会依照环绕着它的8个 邻居的特性而决定在时间t+1时是否能生存下去。如果某一格在时间t时：
(1)有一个有机体，但是它的邻居少于或等于1个，或者是大于3个，那就会因为不 够稠密或太过稠密，这个有机体在时间t+1时就会死亡；换言之，在t+1时间，那一格中 不会存在有机体。下面就是几个在时间t+1时会死亡的例子，如图8-16所示。太少太少太多图 8-16(2)有有机体在该处，当只有2个或3个邻居时，就可以继续生存。下面就是几个可 以生存的例子，如图8-17所示。图 8-17(3)如果没有有机体，而那一格恰好有3个邻居时，当时间为t+1时，那一格就会生 出一个有机体。下面就是几个可以从“无”到“有”的例子，如图8-18所示。图 8-18(4)其他情形不会造成新的有机体出生。
程序要输入棋盘的大小（毕竟内存有限，不能表示无限的棋盘，不是吗？），并且输入 最大的时间值，比如N，然后输入一个在开始时的有机体分布情况，最后显示出时间为 2,3，…，N时棋盘上的状态。
一般而言，最终的结果不外乎4种。第一种是不到时间N时，所有有机体全都死光； 第二种是到了某个时间，棋盘就不再发生变化，生者生存，这就叫做稳定（Stable)状态； 第三种则是到了某个时间之后，棋盘上的分布方式就产生循环，也就是说，棋盘上有某几 种状况周而复始地以周期性方式出现；第四，也就是最后一种，它不是上述三种情况之一。 程序应该可以查出在时间N之前棋盘进入稳定状态，或者是有机体全都死，第三种情况是 不容易找出来的（为什么？）。