N-Queen

Java code:

import java.util.Scanner;

public class N_Queen {
    static int n;
    static int countQueen = 0;
    static int ansCount = 0;
    static boolean[] colHasQueen, leftSlashHasQueen, rightSlashHasQueen;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        try {
            System.out.print("請輸入n: ");
            n = sc.nextInt();
        } finally {
            sc.close();
        }
        colHasQueen = new boolean[n];
        leftSlashHasQueen = new boolean[2 * n - 1];
        rightSlashHasQueen = new boolean[2 * n - 1];
        findQueen(0, 0);
        System.out.println("總共有" + ansCount + "組解");
    }

    private static void findQueen(int row, int col) {
        if (countQueen == n)
            ansCount++;
        else if (col < n) {
            if (!colHasQueen[col] && !leftSlashHasQueen[row - col + n - 1] &&
                    !rightSlashHasQueen[row + col]) {
                colHasQueen[col] = true;
                leftSlashHasQueen[row - col + n - 1] = true;
                rightSlashHasQueen[row + col] = true;
                countQueen++;
                findQueen(row + 1, 0);
                colHasQueen[col] = false;
                leftSlashHasQueen[row - col + n - 1] = false;
                rightSlashHasQueen[row + col] = false;
                countQueen--;
            }
            findQueen(row, col + 1);
        }
    }
}

範例輸入輸出:

---

此程式解決的問題是經典的n-queen問題，三個布林陣列存的分別是行,  左斜線, 右斜線有沒有被擺過皇后，之所以沒有存列有無擺過皇后是因為這列擺過皇后之後，直接換下一列，所以沒有會碰到同一列的可能。若放置此位置後無法找到皇后共存的組合，則此皇后會往右移一格，若皇后移到此列的盡頭都沒有位置可以擺放則直接回到上一列更改皇后的位置，因為是在n*n的棋盤上擺放n個皇后，所以不可能有任何一列沒有被擺到皇后。

輸入為一個整數n，輸出則為總共有多少種擺放的方式，並沒有去除掉對稱的情況。