1 package com.gxf.backtracking; 2  3 /** 4  * n皇后问题 5  * @author Administrator 6  * 7  */ 8 public class Queen { 9     int num_queen;                                    //皇后个数10     int solution[];                                    //solution[i] = k表示第i行皇后在第k列    ,solution为解空间11     int sum = 0;12     13     public Queen(int num){14         num_queen = num;15         solution = new int[num_queen + 1];16     }17     18     /**19      * 第k个皇后的位置是否有效20      * 第k个皇后的列保存在solution[k]中，与前面k-1个皇后比较21      * @param k22      * @return23      */24     boolean isValid(int k){25         for(int i = 1; i < k; i++){26             if(solution[i] == solution[k] || Math.abs(k - i) == Math.abs(solution[k] - solution[i]))27                 return false;            28         }29         return true;30     }31     32     /**33      * 开始放第n个皇后34      * @param queen35      */36     public void placeQueen(int n){37         if(n > num_queen)38         {39             showSolution();40             System.out.println();41             sum++;42         }43         else44             for(int i = 1; i <= num_queen; i++){45                 solution[n] = i;                        //n个皇后放到i列 46                 if(isValid(n))47                     placeQueen(n + 1);48             }49     }50     51     /**52      * 将结果打印出来53      */54     public void showSolution(){55         for(int i = 1; i <= num_queen; i++){56             for(int j = 1; j <= num_queen; j++){57                 if(j == solution[i])58                     System.out.print(‘Q‘ + " ");59                 System.out.print(0 + " ");60             }61             System.out.println();62         }63     }64     65     public static void main(String[] args) {66         Queen queen = new Queen(4);67         68         queen.placeQueen(1);69         System.out.println("sum = " + queen.sum);70     }71 72 }