N皇后问题

import java.util.Scanner;
public class Main {
    public static int count = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[]{0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596};
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            System.out.println(arr[n]);
        }
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(n < 1? 0: solve(0, new int[n], n));
    }
    
    private static int solve(int i, int[] record, int n) {
        if(i == n) return 1;      // 所有列都检查完了，找到了一种合法的摆法
        // 尝试列
        int count = 0;
        for(int j = 0; j < n; j++){
            if(isValid(i, j, record)){
                record[i] = j;
                count += solve(i + 1, record, n);
            }
        }
        return count;
    }
    
    private static boolean isValid(int i, int j, int[] record) {
        for(int k = 0; k < i; k++)
            if(record[k] == j || Math.abs(record[k] - j) == Math.abs(i - k)) return false;    // 共列或共斜线
        return true;
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(solve((1 << n) - 1, 0, 0, 0));     // 准备一个右边有n个1的数
    }
    
    private static int solve(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if(colLim == limit) return 1;      // 所有列都填完了，找到了一种合法的摆法
        int pos = limit & (~(colLim|leftDiaLim|rightDiaLim));      // 当前行可以摆皇后的位置
        int count = 0, mostRightOne = 0;
        while(pos != 0){
            mostRightOne = pos & (~pos + 1);       // 提取最右侧的1，表示从最右边能填的地方开始试
            pos -= mostRightOne;                   // 消掉最右侧试过的位置
            count += solve(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }
        return count;
    }
}

import java.util.*;

public class Main {
    
    public static int process(int checkerboard, int current, int leftDiagonal, int rightDiagonal) {
        if (checkerboard == current) {
            // 每一列都放了棋子，放完了
            return 1;
        }
        int res = 0;
        // 找可以放棋子的位置,位上为1可以放置
        // 00 1 0 0 0    leftDiagonal
        // 00 0 0 0 1    rightDiagonal
        // 00 0 0 1 0    current
        // 00 1 0 1 1
        // 11 0 1 0 0
        // 00 1 1 1 1    checkerboard
        // 00 0 1 0 0    pos
        // 00 0 1 0 0    rightmost
        int pos = checkerboard & (~ (leftDiagonal | rightDiagonal | current));
        while (pos != 0) {
            int rightmost = (~pos + 1) & pos;
            pos ^= rightmost;
            // 放棋子，影响后面放置的位置
            res += process(checkerboard, current | rightmost, 
                           (leftDiagonal | rightmost) << 1, (rightDiagonal | rightmost) >>> 1);
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n < 1 || n > 32) {
            System.out.println(0);
            return;
        }
        // 位上为1，可以放棋子
        int checkerboard = n == 32 ? -1 : (1 << n) - 1;
        int result = process(checkerboard, 0, 0, 0);
        System.out.println(result);
    }
}