编程沙龙（07）
IT商界
题目：在8×8见方的棋盘上要放置8个棋子，要求任意两个棋子不能出现在同一行、同一列或同一对角线上。请你给出这8个棋子的摆放方式。
解答：上期我已经将解决题目的基本思路给了出来。由于采用逐步试探的思路，我们可以考虑采取递归的方式来解题，当然不用递归也一样可以解本题。但相对而言，用递归方式解题，程序显得简洁明了。
在第5期的《算法演义》里给出了递归函数的一般形式。由于我们需要一个棋子一个棋子(一行一行)地去试着放，而每放一个棋子我们所须做的工作都是一样的，所以我们的递归函数的作用就是完成在一行中放一个棋子的工作并尝试到下一行去放另一个棋子。关于如何保存棋盘的状况的问题，我就用上期里说过的用一个一维整型数组来表示。我用i表示行数，a[i]则表示在第i行上放置的棋子所在的列数。下面是用Pascal写成的程序片段和注释。
……
const
N=8; //确定是在N×N的棋盘上放N个棋子，N可以改变
Var
a: array [ 1..N] of integer; //存放棋盘的状态。如A[1]表示在第1行第一列有一个棋子。
……
function checkQizi(i, j: integer): boolean; //假定此前的i-1行里放的棋子都不冲突。判断在第i行
Var //行第j列能否放一个棋子。
ii:integer; //临时变量，保存当前已经判断到第几行。
begin
ii:=1; //从第一行开始判断
result:=true;
while ii
begin
if (a[ii]=j) or (abs(a[ii]-j)=i-ii) then // a[ii]=j判断是否该列已经被使用
// abs(a[ii]-j)=i-ii判断斜线方向是否被占用
begin
result:=false;
break;
end;
ii:=ii+1;
end;
end;
Procedure XiaQi (i: integer); //递归放置第i行
Var
j: integer;
Begin
if i>N then //如果放置的行数已大于N则说明已经找到一组解。
Begin
//输出a里的数。这里不详细说明了。
End
else
for j:=1 to N do //依次尝试在第i行第j列放置棋子
if test(i,j) then //如果可以放置就继续尝试第i+1行
begin
a[i]:=j; XiaQi(i+1);
end;
End;
我们只需在主程序里调用XiaQi(1)就可以了。是不是很简单？当然，上面的方法并不是最有效率的。这次有些读者朋友就用了另一种储存棋盘状态的方法。他们用四个一维的数组分别储存棋盘的行、列、上升对角线及下降对角线的占用情况。尽管这样看起来使用了较多的存储空间，而且程序写起来也比上面的要长，但效果是明显的，特别是在N大到一定数值时。有兴趣的朋友可以自己试着做一下，并试着分析一下其中的原因。(PALADIN)
经过两周的繁忙工作，终于处理完了朋友们的来信。不少朋友都做对了我们的题目，部分朋友思路对了但程序中存在一些BUG或是有思考不周全的地方，只有很少的朋友可能是没能弄明白题意所以才没做对。现在犯难的是该把奖品给谁！？……(没拿到的可别……)
在仔细斟酌之后，获得奖品的读者是：
空军第十三飞行学院理训处 李扬
河南省信阳市第二高级中学高20班 张焱
北京工业大学 应用数理学院 数学系 王宇
他们分别将获得《瑞星杀毒软件2003》一套。而且我们还从参与我们答题活动的读者中选出了四名幸运读者：南京 苏展，山东 马坤，湖南 李雪辉，安徽 李扬，他们可获得电脑报电子媒体室出版的《VB6/.NET编程实例精选》或者《Delphi6编程实例精选》一套。