问题描述:
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。
---------来自<维基百科>
个人思路:
max表示n个皇后 用array[n]表示皇后在第n+1行,array[n]列,比如array[0] = 8 意思为:该皇后位于第1行第8列的坐标;
排列树与子集树的区别在于子集树不需要初始化而排列树需要,此初始化内容为众多可能解集合(注:是可能解,不一定为正确解)中的一个
初始化为a[]数组(1-n随意排列);
将a数组的值向array中输出,初始传入n为0;表示该皇后在第一行,但具体哪列不确定,此时初始化的a数组就起到了作用,a[n]表示在n+1行的第a[n]列, 将其赋值给array,即: array[n] = a[i];
(因为a[]中只是可能性,所以要将所有可能性用for循环表示.即:for(int i = n;i < max ; i++);
然后更新a数组 swap(a,n,i) (意为 既然已经使用过a[i]那就用原本的a[n]替换a[i] 保证列值不重复)
更新后判断该位置是否与已经存在的皇后的位置冲突(同斜线) 已经通过a数组和n已经去除掉同行同列的可能;n保证不同行,a[i]保证不同列;
如果合法,则进入n+1;重复讨论n+2个皇后的位置 /如果不合法,交换回之前位置(只有合法之后才能占该列值) i++;
当i++到for循环结束,也就是说该皇后在这一行所有列中都没有找到合适自己的位置,回退,即该方法执行结束,重新讨论之前上个皇后的位置;
代码如下:
public class NQueen {
int max = 8;
int array[] = new int[max];
int[] a = { 8, 2, 3, 4, 5, 6, 7, 1 };
public void backtrack(int n) {
if (n == max) {
print();
return;
} else {
for (int i = n; i < max; i++) {
array[n] = a[i];
swap(a, n, i);
if (nice(n)) {
backtrack(n + 1);
}
swap(a, n, i);
}
}
}
public boolean nice(int n) {
for (int i = 0; i < n; i++) {
if (Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
public void swap(int[] a, int i, int j) {
int tem = a[i];
a[i] = a[j];
a[j] = tem;
}
int k = 0;
public void print() {
++k;
System.out.print("第" + k + "种解法:");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
new NQueen().backtrack(0);
}
}
网友评论