关于八皇后问题

Question

有兴趣的朋友可以讨论下，八皇后问题怎么样才能尽可能少的减少资源的使用，还有就是大家说说解答的思路，我觉得思路比直接贴代码好多了

Answer 1

// 我的想法是吧8*8的棋盘看成8层 每层8个可选的值，然后对所有可能进行检查
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);// temp
list.add(1);// <--从1开始传入
// 其实八皇后的问题只需要解析前面4个值就可以了，我发现八皇后的解是对称的
// 比如说这个1,5,8,6,3,7,2,4 用9依次相减得到 9-1=8,9-5=4,1,3,6,2,7,5这个就是8开头的其中的一个解了
for (int i = 1; i < 9; i++) {
list.set(1, i);
test(list, 2);
}
} // result 用于存储已选结果 l为目标层数
public static void test(List<Integer> result, int l) {
if (l != 9) {
List<Integer> list = null;
list = check(result, l);
if (list != null && !list.isEmpty()) {
// 目标层数加1
l++;
// 遍历可选list
for (int i = 0; i < list.size(); i++) {
List<Integer> newResult = new ArrayList<Integer>();
newResult.addAll(result);
newResult.add(list.get(i));
test(newResult, l);
}
}
}
} // 检查函数
// 对已有结果进行解析，得出新的可选参数，返回的list就是新的可选项
// 比如说第一层选了1那么目标层就是2，第二层能选的结果就是3,4,5,6,7,8 然后通过循环吧结果作为新的result传进去
public static List<Integer> check(List<Integer> result, int l) {
int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
for (int i = 1; i < l; i++) {
int index = result.get(i);
if (a[index] != 0) {
a[index] = 0;
}
int t = 0;
if ((t = index - (l - i)) > 0) {
a[t] = 0;
}
if ((t = index + (l - i)) < 9) {
a[t] = 0;
}
}
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
list.add(a[i]);
}
}
return list;
}

Answer 2

n皇后问题已经有了最优的解决方法，即用二进制压缩状态并使用位运算。推荐这篇文章，虽然代码是Pascal的

Answer 3

我的思路就是：每次填充一个位置，就把不能再用的位置标记上；如果有任何后继行所有位置都被标记为不能用，就结束递归。
估计就是前面两楼提到的位运算。
没看文章，简单说下，反正是讨论。首先是个空表
1 2 3 4 5 6 7 8
2 O O O O O O O
3 O O O O O O O
4 O O O O O O O
5 O O O O O O O
6 O O O O O O O
7 O O O O O O O
8 O O O O O O O
放一个棋子用X表示，不能用的位置用-表示，第一次：
1 2 3 4 5 6 7 8
2 X - - - - - -
3 - - O O O O O
4 - O - O O O O
5 - O O - O O O
6 - O O O - O O
7 - O O O O - O
8 - O O O O O -
第二次，x表示之前放的，.表示之前标记不能用的
1 2 3 4 5 6 7 8
2 x . . . . . .
3 . . X - - - -
4 . - . - O O O
5 . O - . - O O
6 . O - O . - O
7 . O - O O . -
8 . O - O O O .
第三次：
1 2 3 4 5 6 7 8
2 x . . . . . .
3 . . x . . . .
4 . . . . X - -
5 . O . . . - O
6 . O . O . . -
7 . - . O - . .
8 . O . O - O .
第4次：
1 2 3 4 5 6 7 8
2 x . . . . . .
3 . . x . . . .
4 . . . . x . .
5 . X . . . . -
6 . - . O . . .
7 . . . - . . .
8 . - . O . O .
可以看到第7行一个O都没有了，所以这个位置【5，3】不能用。要换下一个。我画得有点问题，只是表示个想法。
类似这种“全0全1”用位运算很快，不用遍历。
我估计它的算法就是这个吧

Answer 4

刚学的，位运算，果然很快！
public class Queens {
/*
 * * 目前最快的N皇后递归解决方法* N Queens Problem* 试探-回溯算法，递归实现
 */ // sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。
private static long sum = 0, upperlim = (1 << 8) - 1; // 试探算法从最右边的列开始。
public static void test(long row, long ld, long rd) {
if (row != upperlim) {
// row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，
// 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1
// 也就是求取当前哪些列可以放置皇后
long pos = upperlim & ~(row | ld | rd);//所有可以放的位置
while (pos != 0) // 0 -- 皇后没有地方可放，回溯
{
// 拷贝pos最右边为1的bit，其余bit置0
// 也就是取得可以放皇后的最右边的列
long p = pos & -pos;//最右边的位置 // row + p，将当前列置1，表示记录这次皇后放置的列。
// (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。
// (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。
// 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归
// 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位
// 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线
// 上产生的限制都被记录下来了
test(row + p, (ld + p) << 1, (rd + p) >> 1);
// 将pos最右边为1的bit清零
// 也就是为获取下一次的最右可用列使用做准备，
// 程序将来会回溯到这个位置继续试探
pos -= p;
}
} else {
// row的所有位都为1，即找到了一个成功的布局，回溯
sum++;
}
}
public static void main(String[] args) {
test(0, 0, 0);
System.out.println(sum);
}

Answer 5

bit pattern technique，精巧