趣味集算:八皇后问题

简介:

有关国际象棋的问题很多,八皇后问题就是其中相当著名的一个。在 8×8 的国际象棋棋盘中,放入 8 个皇后,使它们不互相攻击,共有多少种方法呢?
3
4

国际象棋中皇后的威力巨大,攻击范围是同一行、同一列以及同一斜行,因此,符合条件的 8 个皇后必须都不在同一行、同一列或者同一斜行上。

由于每一行中只能放入一个皇后,所以可以使用一个长度为 8 的序列,依次设入每行中皇后所在的列数,以此来表示皇后的放置状态。当某一行还没有置入皇后时,即该行没有一列上有皇后,记为 0;而每次置入新的皇后时,如果列数不是序列中已有的,就说明没有皇后在同一列中。这样,不同行、不同列就能很容易的判定了。

那么,在置入新的皇后时,就只需要保证它与已有的皇后都不在同一斜行上了。如果一个皇后在 m 行 k 列,那么在 m+n 行,最多只有两个位置和它在同一斜行上,而且这两个位置距离它的横向距离等于纵向距离,也就是说最多

只有 (m+n,k+n) 和 (m+n,k-n) 这两个位置与这个皇后在同一斜行上。

这样,只要把每个皇后在每一行的所有情况都检查一遍,就可以知道共有多少种情况满足要求了。

经过上面的抽象分析,我们只需要在集算器中,通过循环计算来完成这些判断就行了。具体代码如下:
1
第 1 行,A1 就是记录皇后放置状态的序列;B1 定义了一个变量 i,用来在计算时记录当前放置皇后的行。

第 2 行代码,每循环一次,就把当前行的皇后下移 1 列,用这样的方法遍历行中每个位置。

第 3 行代码,如果棋子移到了第 9 列,说明当前行的棋子已经完成了所有位置的循环,此时,应该把当前行的记录复原为 0,并将 i 减 1,可以返回去继续上一行的遍历;特别的,当第 1 行也全部循环后,说明完成了遍历,此时 i 被设为 0,停止循环。

第 4 行代码,在移动第 1 行皇后时,可以不用判断,直接开始放置第 2 个皇后。

第 6 行代码,判断已放好的皇后中,是否存在同一列的;

第 7 行代码,判断已放好的皇后中,是否存在同一斜行的。如果既没有同一列的,也没有同一斜行的,就可以继续放置下一行的皇后了。

如果此时 8 个皇后都放置成功,则在第 9 行代码中记录下当前每个皇后的位置。

经过计算,A10 中结果如下:
5

可以在 C1 中查看具体结果:
6

当然,还可以用经典的递归方式解决这个问题,集算器中递归调用子函数的方法的代码如下:
2
在 A2 定义的子程序中,在一个新行中尝试放置皇后,在 B2 中循环每一个可能的列。

A5 中的子程序用来判断新的一行是否可以使用指定的列,其中在 C5 中查看是否本列已存在皇后,第 6 行查看是否已有皇后在同一斜行,在这样的情况下说明不能放置。如果某一列可以放置,则判断是否 8 个皇后都放置成功,如果已全部设置成功则记录在 C1 中。如果未放置满,则递归调用 A2 中的子程序,继续在下一行放置。这种方法的代码更易理解,计算结果与前面的方法是相同的。

相关文章
|
6月前
|
算法
【算法学习】—n皇后问题(回溯法)
【算法学习】—n皇后问题(回溯法)
|
索引
八皇后问题
八皇后问题
236 0
|
机器学习/深度学习 算法
蓝桥杯:递推算法 递归算法 例题:斐波纳契数列
蓝桥杯:递推算法 递归算法 例题:斐波纳契数列
66 0
|
机器学习/深度学习 算法
【回溯算法篇】N皇后问题
【回溯算法篇】N皇后问题
【回溯算法篇】N皇后问题
|
机器学习/深度学习 算法
<<算法很美>>——(六)——回溯算法(下)—N皇后问题
<<算法很美>>——(六)——回溯算法(下)—N皇后问题
<<算法很美>>——(六)——回溯算法(下)—N皇后问题
|
算法
【算法】 八皇后问题之回溯法
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。每次填满第一行第一列,当不满足时候,试下第一行第二列,依次进行,递归的出口为找到第八个点,跳出递归。,在循环里面还要判断是否满足不同行,不同列,不同对角线。使用回溯法来解决该问题,下面的代码是我看到过的最精简的代码,相关的注释都写在代码上了。运行得出结果,总共有92中结果。
265 0
对于八皇后问题的详细说明
八皇后为解决问题说明,题目在主页
63 0
对于八皇后问题的详细说明