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; } }算法的复杂度指标上其实是没有提升的,仍然是O(2n),主要是缩短了常数时间。
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); } }