趣味集算：八皇后问题
有关国际象棋的问题很多，八皇后问题就是其中相当著名的一个。在 8×8 的国际象棋棋盘中，放入 8 个皇后，使它们不互相攻击，共有多少种方法呢？
国际象棋中皇后的威力巨大，攻击范围是同一行、同一列以及同一斜行，因此，符合条件的 8 个皇后必须都不在同一行、同一列或者同一斜行上。
由于每一行中只能放入一个皇后，所以可以使用一个长度为 8 的序列，依次设入每行中皇后所在的列数，以此来表示皇后的放置状态。当某一行还没有置入皇后时，即该行没有一列上有皇后，记为 0；而每次置入新的皇后时，如果列数不是序列中已有的，就说明没有皇后在同一列中。这样，不同行、不同列就能很容易的判定了。
那么，在置入新的皇后时，就只需要保证它与已有的皇后都不在同一斜行上了。如果一个皇后在 m 行 k 列，那么在 m+n 行，最多只有两个位置和它在同一斜行上，而且这两个位置距离它的横向距离等于纵向距离，也就是说最多
只有 (m+n,k+n) 和 (m+n,k-n) 这两个位置与这个皇后在同一斜行上。
这样，只要把每个皇后在每一行的所有情况都检查一遍，就可以知道共有多少种情况满足要求了。
经过上面的抽象分析，我们只需要在集算器中，通过循环计算来完成这些判断就行了。具体代码如下：
| A | B | C | D | |
|---|---|---|---|---|
| 1 | =[0]*8 | >i=1 | ||
| 2 | for i>0 | >A1(i)=A1(i)+1 | ||
| 3 | if A1(i)==9 | >A1(i)=0,i=i-1 | next | |
| 4 | if i==1 | >i=2 | next | |
| 5 | =A1(i) | =A1.to(i-1) | ||
| 6 | if C5.pos(B5)>0 | next | ||
| 7 | else if C5.pselect(i-#==abs(B5-~))>0 | next | ||
| 8 | >i=i+1 | |||
| 9 | if i==9 | >C1=C1|A1.conj@s() |
>A1(8)=0,i=7 | |
| 10 | =C1.len() |
第 1 行，A1 就是记录皇后放置状态的序列；B1 定义了一个变量 i，用来在计算时记录当前放置皇后的行。
第 2 行代码，每循环一次，就把当前行的皇后下移 1 列，用这样的方法遍历行中每个位置。
第 3 行代码，如果棋子移到了第 9 列，说明当前行的棋子已经完成了所有位置的循环，此时，应该把当前行的记录复原为 0，并将 i 减 1，可以返回去继续上一行的遍历；特别的，当第 1 行也全部循环后，说明完成了遍历，此时 i 被设为 0，停止循环。
第 4 行代码，在移动第 1 行皇后时，可以不用判断，直接开始放置第 2 个皇后。
第 6 行代码，判断已放好的皇后中，是否存在同一列的；
第 7 行代码，判断已放好的皇后中，是否存在同一斜行的。如果既没有同一列的，也没有同一斜行的，就可以继续放置下一行的皇后了。
如果此时 8 个皇后都放置成功，则在第 9 行代码中记录下当前每个皇后的位置。
经过计算，A10 中结果如下：
可以在 C1 中查看具体结果：
当然，还可以用经典的递归方式解决这个问题，集算器中递归调用子函数的方法的代码如下：
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | [] | =func(A2,A1) | =C1.len() | ||
| 2 | func | for 8 | if func(A5,A2,B2) | =A2|B2 |
|
| 3 | if D2.len()==8 | >C1=C1|D2.conj@s() |
|||
| 4 | else | >func(A2,D2) | |||
| 5 | func | if A5.pos(B5)>0 | return false | ||
| 6 | for A5 | if abs(B5-B6)==A5.len()+1-#B6 | return false | ||
| 7 | return true |
在 A2 定义的子程序中，在一个新行中尝试放置皇后，在 B2 中循环每一个可能的列。
A5 中的子程序用来判断新的一行是否可以使用指定的列，其中在 C5 中查看是否本列已存在皇后，第 6 行查看是否已有皇后在同一斜行，在这样的情况下说明不能放置。如果某一列可以放置，则判断是否 8 个皇后都放置成功，如果已全部设置成功则记录在 C1 中。如果未放置满，则递归调用 A2 中的子程序，继续在下一行放置。这种方法的代码更易理解，计算结果与前面的方法是相同的。
作者：massslow
来源：乾学院
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
👍
👍