八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。
问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,因为她们会相互攻击,(harm!!)问有多少种摆法。高斯认为有76种方案。但在1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
下面咱们就进入这正题吧!算法类型:dfs爆搜+回溯
相信大家也熟知这个算法,加上剪枝的算法优化时间复杂度比O(2^n)小很多,空间复杂O(3*n)这里用了三个java集合类数据结构
代码如下:
import java.util.*;
public class N皇后 {
public static int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
if (row == n) return 1;
int count=0;
for (int i = 0; i < n; i++) {
if (columns.contains(i)) continue;
int diagonal1 = row - i;
if (diagonals1.contains(diagonal1)) continue;
int diagonal2 = row + i;
if (diagonals2.contains(diagonal2)) continue;
columns.add(i);
diagonals1.add(diagonal1);
diagonals2.add(diagonal2);
count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
columns.remove(i);
diagonals1.remove(diagonal1);
diagonals2.remove(diagonal2);
}
return count;
}
public static void main(String[] args) {
Set<Integer> column = new HashSet<Integer>();
Set<Integer> diagonal1 = new HashSet<Integer>();
Set<Integer> diagonal2 = new HashSet<Integer>();
System.out.print(backtrack(8,0,column,diagonal1,diagonal2));
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)