NoThings

想法就是說每列每列找適合的位置，如果找得到的話就把衝突的位置標記起來，然後繼續往下找。

舉例來說：

4X4

一開始：
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

找第一列：
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

標記：
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 1

找到了換下一列：
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 1

標記：
0 1 1 1
0 1 2 0
0 0 1 0
0 0 2 1

然後第三列找不到，因此把第二列清掉：（直接掃整個陣列，把標2的清掉，就不會影響到之前標記的）
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 1

再找下一個位置：
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 1

標記：
0 1 1 1
0 1 0 2
0 0 1 0
0 0 0 1

......以此類推，如果找不到的話就回上一列，如果走到最下列還可以放的話，就代表這種方法是可行的，總方法數+1

另外就是因為一列也只能放一個皇后，因此直接省掉向上、向下、向左的標記了，直接往右標記就好，

人家車子都停在停車格裡了，你晚到的不需要去跟他說你不能停哪個位置呀。

每列往後的標號不一樣是為了清除用，不然全部都標1的話，就會清到之前衝突的位置，造成以後錯亂。

舉例：
0 1 0 0
0 1 1 1
0 1 1 1
0 0 1 0
會衝突到


以下為JAVA程式碼

import java.util.Scanner;
public class eight_queen{
    private static int sum = 0, total;
    private static int[][] checkQueen; //確定位置是否可以放置的陣列，使用大小[n+1][n+1]，因為第0行跟第0列不想用= =a

    private static void record(int n, int m){ //放置皇后後，將右手邊的其他列會衝到的地方標記起來
        boolean check = true;
        int i = n, j = m;
        while(check){       // Right
            if(j >= total)
                break;
            else
                if(checkQueen[i][++j] == 0)
                    checkQueen[i][j] = m;  // 原本位置在第幾列就把衝突的值設為多少
        }

        i = n;
        j = m;
        while(check){       // Right-down
            if(j >= total || i <= 1)
                break;
            else
                if(checkQueen[--i][++j] == 0)
                    checkQueen[i][j] = m;  //同上
        }
        i = n;
        j = m;
        while(check){       // Right-top
            if(j >= total || i >= total)
                break;
            else
                if(checkQueen[++i][++j] == 0)
                    checkQueen[i][j] = m;   //同上
        }

    }

    private static void clear(int n, int m){
        for(int i = 1; i <= total; i ++)
            for(int j = 1; j <= total; j ++)
                if(checkQueen[i][j] == m)
                    checkQueen[i][j] = 0;    //把衝突的記錄清掉，這樣才不會清到別人以經加入的位置。如果該格不是0是n的話就代表他跟第n行的皇后衝到。
    }


    private static void queen(int n){  //
        if(n == total){    //  如果N在最後一列就看能不能放，可以的話sum+1
            for(int i = 1; i <= total; i ++)
                if(checkQueen[i][n] == 0){
                    sum += 1;
                    break;
                }
        }
        else{                // 如果N不在最後一列的話就找個0的位置放，然後再把會衝到的位置標記起來
            for(int i = 1; i <= total; i ++)
                if(checkQueen[i][n] == 0){
                    record(i, n);
                    queen(n + 1);
                    clear(i, n);
                }
        }
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        total = scanner.nextInt();
        //輸入total
        checkQueen = new int[total+1][total+1];
        queen(1);
        System.out.println(sum);
        //印出結果
    }
}