1) 第一个皇后先放第一行第一列
2) 第二个皇后放在第二行第一列、然后判断是否OK[即判断是冲突]， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
3) 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
4) 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
（栈递归完成后，会返回上一个栈，根据上一次的结果继续计算）
5) 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤
package recursion; public class Queue8 { /*1) 第一个皇后先放第一行第一列 2) 第二个皇后放在第二行第一列、然后判断是否OK[即判断是冲突]， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适 3) 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解 4) 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到. 5) 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤 */ int max = 8;//一共8个皇后 int[] array = new int[max]; static int count = 0; static int judgeCount = 0; public static void main(String[] args) { //测试一把 ， 8皇后是否正确 Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("一共有%d解法", count); System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w } //放置第n个皇后 private void check(int n ){ if( n == max){ print(); return; } else{ //依次放入，判断是否有冲突 for(int i = 0; i < max;i++){ //先把当前这个皇后 n , 放到该行的第1列 //先从第一列试 array[n] = i ; //判断放置当前第n个皇后是否冲突 if(judge(n)){//不冲突 check(n+1);//接着放下一个皇后 /*比如第一个正确摆法确定了，最后一个皇后位置在i == 3，此时return返回到check(n+1);这里 * 此时if语句块中代码执行完，接着for循环，此时 i == 3 < max * i++ , i == 4 判断不冲突 ，然后再返回到check(n+1);这里 * i++ 直到最后一个八皇后没有合适的位置，再返回到上一层，即倒数第二个八皇后 * 一直重复，直到放在第一列的所有正确解，全部得到. * * 然后再从第二个位置开始，重复以上步骤*/ } //如果冲突的话，就试下一个位置，执行 array[i] = n ; } } } //判断该位置第n个皇后与之前n-1个皇后是否冲突 private boolean judge(int n){ for(int i = 0;i < n;i++){ judgeCount++; // 说明 //1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列 //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线 // n = 1 放置第 2列 1 n = 1 array[1] = 1 // Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1 //3. 判断是否在同一行, 没有必要，n 每次都在递增 if(array[n] == array[i] || Math.abs(array[n] - array[i]) == Math.abs(n - i)){ return false; } } return true; } private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
