八皇后问题

叁歲伎倆 2021-09-25 15:34 445阅读 0赞

八皇后问题，以国际象棋为背景：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任意两个皇后都不能处于同一条横行、纵行或斜线上。

一、数据结构

解决这种算法题目，首先需要确定数据结构，选定合适的数据结构之后，可以有效的提高解决问题的效率。

在八皇后问题中，首先想到的数据结构应该是8×8的二维数组（由棋盘联想到的），可以定义有皇后的位置是1，没有皇后的位置是0，这样可以直观有效的保存八皇后所在位置。

如：

\{ \{0, 0, 0, 1, 0, 0, 0, 0\},

\{0, 0, 0, 0, 0, 0, 1, 0\},

\{0, 0, 1, 0, 0, 0, 0, 0\},

\{0, 0, 0, 0, 0, 0, 0, 1\},

\{0, 1, 0, 0, 0, 0, 0, 0\},

\{0, 0, 0, 0, 1, 0, 0, 0\},

\{1, 0, 0, 0, 0, 0, 0, 0\},

\{0, 0, 0, 0, 0, 1, 0, 0\}\}

但是这样会有大量的空间是0，有效位置与无效位置的比例为1:7，浪费是很明显的，所以自然而然的会再次寻找其他更加节省空间的方法。

这里推荐使用一维数组，将二维数组中所有0去掉，将1替换为位置，这样所使用的一维数组既保留了二维数组的直观，又解决了空间浪费问题。（如果你问我为什么想到一维数组，可以试试用汉语表述一下结果，如：第一行皇后放置在第四列，第二行皇后放置在第七列……，是不是很类似于，a\[0\]=3，a\[1\]=6呢？）

二、解决方法

八皇后问题是回溯法（backtracking，是一种选优搜索法）的典型案例，属于暴力搜寻法中的一种。采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

1）找到一个可能存在的正确的答案；

2）在尝试了所有可能的分步方法后宣告该问题没有答案。

在八皇后问题中，使用回溯法查找正确解法，其思想就是当前i-1个位置放置成功的前提下，放置i位置的皇后，如果放置成功，则放置第i+1位置的皇后；如果不成功，则重新放置i-1位置的皇后。

核心代码为：

private void place(int i) {
       for (int j = 0; j < 8; j++) {
          num++;
          a[i] = j;
          if (check(i)) {
             if (i == 7) {
                times++;
                System.out.println(Arrays.toString(a));
             } else {
                place(i + 1);
             }
          }
       }
    }

其中check()方法是检查i位置放置的皇后是否正确：

private boolean check(int i) {
       for (int j = 0; j < i; j++) {
          if (a[j] == a[i]) {
             return false;
          } else if (a[i] - a[j] == i - j) {
             return false;
          } else if (a[i] - a[j] == j - i) {
             return false;
          }
       }
       return true;
    }

这样八皇后为题就解决了，只要在合适的位置调用place(0)，即能打印所有可行解决方案。

每一种递归方法都可以使用非递归方法编写，但是一般非递归方法比递归方法编写较复杂。

下面是核心方法中非递归方法：

public int place() {
    	z: for (int i = 0; i < 8; i++) {
    		for (int j = 0; j < 8; j++) {
    			num++;
    			a[i] = j;
    			if (check(i)) {
    // 如果i == 7，方案到底部，符合条件，进行打印。
    // 如果i != 7，进入下一行。
    				if (i == 7) {
    					times++;
    					System.out.println(Arrays.toString(a));
    					if (j == 7) {
    						j = a[i - 1];
    						i--;
    					}
    				} else {
    					break;
    				}
    			} else {
    				// 如果检查失败，则返回到上一行
    				// 如果上一行皇后位置在最后，则再向上移动一行
    				// 直到上移至最顶端
    				while (j == 7) {
    					if (i == 0) {
    						break z;
    					}
    					j = a[i - 1];
    					i--;
    				}
    			}
    		}
    	}
    	return times;
    }

因为是非递归方法，所以直接调用place()即可得到所有解决方案，其中check()方法与递归方法中的完全一致。通过两种方法的对比，可以很明显看出递归方法较非递归方法简单很多。

三、结果与拓展

通过上面的方法，需遍历15720次才能得到所有结果：八皇后问题一共有 92 个互不相同的解。

如果将旋转和对称的解归为一种的话，则一共有12个独立解（维基百科中有详细答案

http://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98）。

如果将棋盘的大小变为n×n，而皇后个数也变成n，则当且仅当 n = 1 或 n ≥ 4 时问题有解。