public class Queen_Java {
    
    int QUEEN_COUNT = 8;    //隨便你定義幾個皇后了，你可以循環產生a個到b個皇后的解
    static final int EMPTY = 0;  //如果count[x][y] == EMPTY ,則可以放置皇后；反之，其正上方或斜上方必己放置皇后
    int[][] count = new int[QUEEN_COUNT][QUEEN_COUNT]; //
    int[] QueenIndex = new int[QUEEN_COUNT]; //第index行的皇后放置位置是QueenIndex [index]
    int resultCount = 0; //記錄皇后放置方法的數量
    
    public void putQueenIndex(int index) {
        int row = index;
        for (int col = 0; col < QUEEN_COUNT; col++) {
            if (count[row][col] == EMPTY) { //該位置可以放置皇后
                for (int iRow = row+ 1; iRow < QUEEN_COUNT; iRow++) { //增加該位置的正下面/斜下面的count，使之不為0
                    count[iRow][col]++;
                    if ((col - iRow + row) >= 0) {
                        count[iRow][col - iRow + row]++;
                    }
                    if ((col + iRow - row) < QUEEN_COUNT) {
                        count[iRow][col + iRow - row]++;
                    }
                }
                QueenIndex[row] = col;
                if (row == QUEEN_COUNT - 1) { //第QUEEN_COUNT個皇后己放置好，打印出這種皇后布局
                    print(++resultCount);
                } else { //繼續放置下一行的皇后
                    putQueenIndex(row + 1);
                }
                for (int iRow = row+ 1; iRow < QUEEN_COUNT; iRow++) { //回溯，在此行的皇后不放此列col ，恢復該位置的正下面/斜下面的count
                    count[iRow][col]--;
                    if ((col - iRow + row) >= 0) {
                        count[iRow][col - iRow + row]--;
                    }
                    if ((col + iRow - row) < QUEEN_COUNT) {
                        count[iRow][col + iRow - row]--;
                    }
                }
            }
        }
        if (row == 0) {
            System.out.println(QUEEN_COUNT + "皇后共有 " + resultCount + " 個解");
        }
    }
    
    public void print(int n) { //打印皇后布局
        System.out.println(QUEEN_COUNT + "皇后的第 " + n + " 個解：");
        for (int i = 0; i < QUEEN_COUNT; i++) {
            for (int j = 0; j < QUEEN_COUNT; j++) {
                System.out.print(QueenIndex[i] == j ? " * " : " - ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        new Queen_Java().putQueenIndex(0);
    }
}