N皇后问题
N皇后问题
N 皇后问题源自国际象棋,所有棋子中权力最大的称为皇后,它可以直着走、横着走、斜着走(沿 45 度角),可以攻击移动途中遇到的任何棋子。
N 皇后问题的具体内容是:如何将 N 个皇后摆放在 NN 的棋盘中,使它们无法相互攻击。举个简单的例子,将 4 个皇后摆放在 44 的棋盘中,下图给出了一种摆放方式,各个皇后无论是直着走、横着走还是斜着走,都无法相互攻击。
1Q 表示放置皇后的位置。N 皇后问题可以用回溯算法解决,接下来就为您讲解具体的解决思路。
回溯算法解决N皇后问题要想使 N 个皇后不相互攻击,应将它们放置在不同的行、不同的列、还不能位于同一条 45°(或 135°)角的斜线上。
回溯算法解决N皇后问题的具体思路是:将 N 个皇后逐一放置在不同的行,以“回溯”的方式逐一测试出每行皇后所在行的具体位置,最终确定所有皇后的位置。
如下为回溯算法解决 N 皇后问题的伪代码:
输入 N // 输入皇后的个数q[1...N] //存储每行的皇后的具体位置(列标)n_queens(k , n): // 确定第 k 行皇后的位置 if k > n: // 递归的出口 Print q