2 sss550c sss550c 于 2015.06.23 16:08 提问

关于java八皇后的问题

public class Queen {

int num; // 记录方案数
int[] queenline = new int[8]; // 记录8个皇后所占用的列号
boolean[] col = new boolean[8]; // 列安全标志
boolean[] diagonal = new boolean[16]; // 对角线安全标志
boolean[] undiagonal = new boolean[16]; // 反对角线安全标志

void solve(int i) {
for (int j = 0; j < 8; j++) {
if (col[j] && diagonal[i - j + 7] && undiagonal[i + j]) {
// 表示第i行第j列是安全的可以放皇后
queenline[i - 1] = j + 1;
col[j] = false; // 修改安全标志
diagonal[i - j + 7] = false;
undiagonal[i + j] = false;

if (i < 8) // 判断是否放完8个皇后
{
 solve(i + 1); // 未放完8个皇后则继续放下一个

} else // 已经放完8个皇后
{
 num++;
 System.out.println("\n皇后摆放第" + num + "种方案:");
 System.out.println("行分别为1 2 3 4 5 6 7 8 ");
 System.out.print("列分别为");
 for (int i1 = 0; i1 < 8; i1++)
  System.out.print(queenline[i1] + " ");
}
col[j] = true; // 修改安全标志,回溯
diagonal[i - j + 7] = true;
undiagonal[i + j] = true;

}

}

}

public static void main(String[] args) {
Queen q = new Queen();
System.out.println("////八皇后问题////");
q.num = 0; // 方案初始化
for (int i = 0; i < 8; i++)
// 置所有列为安全
q.col[i] = true;
for (int i0 = 0; i0 < 16; i0++)
// 置所有对角线为安全
q.diagonal[i0] = q.undiagonal[i0] = true;
q.solve(1);
}
}

这是一段八皇后的代码 输出结果一共有92个
求教大神个问题:
col[j] = true; // 修改安全标志,回溯
diagonal[i - j + 7] = true;
undiagonal[i + j] = true;
他是怎么通过这三行代码实现回溯的。这三行代码什么时候执行?

1个回答

fanst_
fanst_   2015.06.23 21:22

可以简单理解为先深度优先查找到最后一行,循环当前行所有解,当前行循环完成后,回溯到上一行继续循环。
递归是在solve中实现的:
if (i < 8) // 判断是否放完8个皇后
{
solve(i + 1); // 未放完8个皇后则继续放下一个

回溯是递归+循环实现的,比如最后一行i=7,solve(7)中所有的j循环结束,递归返回到上一层方法solve(6)中,
solve(6)方法继续j的循环,循环结束返回到solve(5):
for (int j = 0; j < 8; j++)

另外几个标志位是为了判断当前位置是否可以放置皇后用的,上下左右以及斜线都没有放置皇后。

这一篇里面的写法+注释可能更容易理解:
http://blog.csdn.net/fanst_/article/details/44877301

Csdn user default icon
上传中...
上传图片
插入图片