八皇后VC图形演示

八皇后VC图形演示

    这几天学VC界面编程，在VC在线上狂看教程，觉得有所长进，于是把以前的Java代码用VC改写了一下。问题还是那个老掉牙的问题，八皇后问题，老归老，但我很喜欢，并试图用各种方法来实现求解，出乎意料的是，同样的算法，非递归实现的速度竟然比递归实现慢！下面是当时关于算法一些说明，是用Java实现的，不过用C还是J在思想上都是一样的，如果需要J版的source可已发mail给我。

算法思想：回溯法，先在第1行放上一个皇后，然后在第2行合适的位置放上一个皇后，依次类推，如果8行都放满了，说明找到了一个解，如果第好第i行的皇后后，第i+1行找不到合适的位置，这时就回到第i行，把第i行的皇后放到下一个位置，继续尝试下一行。如此反复，知道找到所有的解。注意，这种算法找的解可能有等价的，某些解可由别的解经过旋转棋盘得到。

实现1：EightQueen.java

这是对上面的思想的一种经典实现方式，它使用了问题一个这样的特性：假设棋盘上一条从左上到右下的斜线上的位置的坐标用（i，j）表示，那么这个i，j满足下面方程：

(i-i0)/(j-j0) =1，即，i-j = i0-j0

其中i0，j0是这条线上任意一个位置。也就是说i-j的值只和斜线的起始位置有关，因此可以用一个数组来表示2n-1条左上到右下的斜线上是否有皇后。同样可以确定一个表示从右上到左下的斜线的数组和竖线的数组：

  int[] queen;   /大小为n，queen[i] 表示第i行皇后的列的位置。

  boolean[] rk;  //大小2n-1，表示从右上到左下的斜线上有没有皇后。

  boolean[] lk;  //大小2n-1，表示从左上到右下的斜线上有没有皇后。

  boolean[] mk;  //大小n，mk[i]表示第第i列没有皇后。

有了这3个数组，每放一个皇后就把相应位置的值设为真，当放下一个皇后时就可以参考这个数组来判断某个位置能否放皇后。

实现2：QuickEightQueen.java

上面的算法可以做个小小的改进，每当我们在第i的某列放上一个皇后后，第i+1行改列就不可能再放了，因此每增加一行，要考虑的列就减少了一列，当回溯时再增加这列。为了高效实现增加和删除，这里使用了整数链表来实现。

试验结果：这是各个实现在14*14的棋盘上的运行结果（P4 2.4G/win2000/JDK1.5）：

其中以NR开头的是非递归算法。EQueen.java是网上拷贝的一个非递归算法，没有使用的EightQueen.java的思想。

此外，GraphEightQueen.java实现了一个图形演示EightQueen.java工具。

原文转自：http://www.ltesting.net