八皇后

1 public class EightQueen { 2  3     private static final int ROW = 4; 4     private static final int COL = 4; 5  6     private static int count = 0; // 八皇后的解的个数 7  8     private static boolean[][] maps = new boolean[ROW][COL]; // 初始化二维数组，模拟8*8棋盘,默认值是false表示没有皇后 9 10     // 如何去放皇后？11     /**12      * 放置第row行的皇后13      * @param row 从第0行开始放皇后14      */15     public static void putQueen(int row) {16 17         // 递归的出口18         if (row == ROW) { // row=8时，已经到了第9行，那么前面的8行就是OK的19             printQueen();20             return;21         }22 23         // 把皇后放到第row行的第j列24         for (int j = 0; j < COL; j++) {25             // 如果可以放，就将皇后放在该点26             if (isOK(row, j)) {27                 maps[row][j] = true;28                 putQueen(row + 1); // 该行放好之后放下一行【递归去放皇后】,算法已经跳转29                 maps[row][j] = false; // 回溯,当放row+1行棋子不满足的时候，会回溯到第row行30             }31         }32     }33 34     // 如果要将皇后放在(x,y)点，则需要先判断该点是否可以放35     public static boolean isOK(int x, int y) {36 37         // 遍历二维数组，判断4个方向是否存在皇后38         for (int i = 0; i < ROW; i++) {39             for (int j = 0; j < COL; j++) {40                 // 正斜边x-y定值，逆斜边x+y为定值41                 if (i == x || j == y || i - j == x - y || i + j == x + y) {42                     // 判断4个方向是否存在皇后43                     if (maps[i][j]) { // 如果该点放了一个皇后，则返回false44                         return false;45                     }46                 }47             }48         }49 50         return true;51     }52 53     public static void printQueen() {54 55         System.out.println("第" + (++count) + "个解");56         System.out.println("*******************");57         for (int i = 0; i < ROW; i++) {58             for (int j = 0; j < COL; j++) {59                 if (maps[i][j]) {60                     System.out.print("Q ");61                 } else {62                     System.out.print("* ");63                 }64             }65             System.out.println();66         }67     }68 69     /**70      * 穷举法求4皇后71      */72     private static void Queen(){73         74         for(int i = 0;i < 4;++i)75             for(int j = 0;j < 4;++j)76                 for(int k = 0;k < 4;++k)77                     for(int m = 0; m < 4;++m)78                         if (!conflusion(i,j,k,m)){79                             System.out.println("["+i+","+j+"," + k + "," + m +"]");80                         }81         82     }    83 84     private static boolean conflusion(int i, int j, int k, int m) {85         86         return j == i || k == i || m == i || k == j || m == j || k == m87                 || Math.abs(i - j) == 1 || Math.abs(i - k) == 288                 || Math.abs(i - m) == 3 || Math.abs(j - k) == 189                 || Math.abs(j - m) == 2 || Math.abs(k - m) == 1;90     }91 92     public static void main(String[] args) {93 94         System.out.println("回溯法求解4皇后");95         putQueen(0);    // 从第0行开始放皇后96         System.out.println("穷举法求解4皇后");97         Queen();98     }99 }