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; } }算法的复杂度指标上其实是没有提升的,仍然是O(2n),主要是缩短了常数时间。
#include <stdio.h> typedef unsigned int uint; uint proc(uint mask, uint colPut, uint leftLim, uint rightLim) { if (mask == colPut) { return 1; } uint ans = 0, pos, mostRight; pos = mask & (~(colPut | leftLim | rightLim)); while (pos != 0) { mostRight = pos & (~pos + 1); pos -= mostRight; ans += proc(mask, colPut | mostRight, (leftLim | mostRight) << 1, (rightLim | mostRight) >> 1); } return ans; } int main(void) { int n; scanf("%d", &n); uint mask = (1 << n) - 1; printf("%u\n", proc(mask, 0, 0, 0)); return 0; }
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); } }
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { int cnt = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(new Main().totalNQueens(n)); } public int totalNQueens(int n) { if(n < 1){ return 0; } List<Integer> list = new ArrayList<>(); help(0,n,list); return cnt; } private void help(int row, int n, List<Integer> list){ //递归的第一步,列出终止条件,防止死循环 if(row == n){ cnt++; return; } //每一列都尝试一下 for (int col = 0; col < n; col++) { //当前列是否合法 if (!list.contains(col)) { //左斜与右协是否哈法 if(!isDiagonalAttack(list,col)){ list.add(col); help(row+1,n,list); //回溯 list.remove(list.size()-1); } } } } private boolean isDiagonalAttack(List<Integer> currentQueen, int i) { int currentRow = currentQueen.size(); int currentCol = i; //判断每一行的皇后的情况 for (int row = 0; row < currentQueen.size(); row++) { //左上角的对角线和右上角的对角线,差要么相等,要么互为相反数,直接写成了绝对值 if (Math.abs(currentRow - row) == Math.abs(currentCol - currentQueen.get(row))) { return true; } } return false; } }