八皇后问题的图形化解决方案

• 下载源代码文件 - 2.8 KB
• 下载演示项目 - 4.3 KB

引言

八皇后问题是许多经典问题之一，它引起了许多人的兴趣。该问题是将 8 个互不攻击的皇后放置在棋盘上。已经提出了各种算法，其中 Writh 算法可能是最好的（考虑到它的时间复杂度）。然而，在我的应用程序中，我使用了 Horowitz-Sahani 的旧算法。两种算法的时间复杂度差异并不大，至少当应用程序的目的是向用户展示图形化解决方案时是这样。这个应用程序的灵感来自 Timothy Rolfe 在 Dr. Dobb's Journal 上发表的文章。任何对算法的详细研究感兴趣的人都可以查看该文章。

算法

为了解决这个问题，使用了一个整数数组，使得数组的每个元素都代表棋盘上的一行。例如，board[0] 将代表棋盘上的第 0 行（即第一行）。每个数组元素的值将代表可以放置皇后的列。例如，board[2] = 6 表示皇后放置在第 3 行第 7 列。这种安排的优点是显而易见的。您可以立即检查垂直方向的攻击。为此，您只需要检查数组中的重复值。如果 board[2] = board[6]，那么第 3 行和第 7 行的皇后都在同一列中。检查对角线攻击有点棘手。例如，board[0]=0 和 board[4]=1。这个位置显然是无效的，因为存在对角线攻击。以下代码段检查这一点

  for (int i = 0; i < row; i++) {
   if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) {
    return false;
   }
  } 

这里 row = 1。第一个条件检查垂直攻击，肯定为 false。检查对角线攻击的第二个条件评估为 true。重点是检查最后一行的每一列（应该放置皇后的地方），看看 Math.abs(board[row] - board[i]) == (row - i) 是否满足。如果满足，则必须存在对角线攻击，因此回溯。其余的算法非常简单。首先尝试将皇后放置在第一行的第一列。然后开始在每行放置一个皇后，放在没有攻击的位置。如果您在特定行中找不到任何这样的位置，那么之前一行中皇后的位置一定是错误的。因此，回溯以找到皇后新的位置。

应用程序

该应用程序虽然只有一个文件，但有四个类

• EightQueenFrame
• EightQueen
• MyCanvas
• 解决方案

它显示所有 92 个解决方案。用户可以通过按向上和向下箭头来浏览不同的解决方案。EightQueen 是负责实现算法的类。该类可以解决 N 皇后问题，构造函数中的参数控制大小。但是，图形解决方案仅适用于 8 皇后。因此，该类构造函数中的参数是 8。Solution 类包装每个棋盘配置。解决方案被添加到 Arraylist 以方便浏览解决方案。EightQueenFrame 是负责绘制的主类。它捕获用于导航的击键。

历史

• 2005 年 10 月 4 日：初始版本

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。