在8*8的的国际象棋中摆上八个皇后 使其不能相互攻击
问题的解向量:(x0,x2,x3,….,x7)
采用数组的下标i 表示皇后的所在行采用数组元素x[i]表示皇后的所在列向量约束条件
显示约束 (对解向量的直接约束) xi=1,2,3…n隐示约束1 :任意两个皇后不同列 : xi=≠xj x i =≠ x j 隐示约束2 :两个皇后不处于同一对角线 : |i−j|≠|xi−xj| | i − j | ≠ | x i − x j |最后的整体调用和类的实现代码如下(完整代码)
public class Queen { private int count =0; private int[] x = new int [8]; public static void main(String [] args) { Queen q = new Queen(); q.Backtrack(0); System.out.println(q.count); } /** * 判断当前放置的 k = i 是否在约束条件中 * @param k 第几行要放置皇后 * @return */ public boolean Bound(int k ) { for(int i =0;i<k ;i++) { if((Math.abs(k-i)==Math.abs(x[k]-x[i]))||x[i]==x[k]) { return false; } } return true; } /** *递归调用函数 放置第t 行的皇后 * @param t */ public void Backtrack(int t) { //递归终止条件 即第九行的皇后即结束(八皇后问题 注意数组的下标从0开始) if (t>7) { //输出放置皇后情况并且count++ output(x); } else { //循环是遍历在第一行上放置皇后 for(int i=0;i<8;i++) { x[t] = i; //如果符合约束条件 就放置下一行的皇后 if(Bound(t)) { Backtrack(t+1); } } } } private void output(int []x) { count++; for(int x1 :x) { System.out.print(x1+" "); } System.out.println(); } }