N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列也不再同一条斜线上，求给一个整数n，返回n皇后的摆法。 时间复杂度O（2^n），空间复杂度O（1）
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws Exception { int n = sc.nextInt(); int ans = 0; for(int i=0;i<n;i++){ boolean[] vis = new boolean[n]; // 每一行放置的元素 int[] columnNum = new int[n]; for(int k=0;k<n;k++){ columnNum[k] = -1; } vis[i] = true; columnNum[0] = i; dfs(vis, columnNum, n, 0); ans += cnt; cnt = 0; } System.out.println(ans); } static int cnt = 0; static void dfs(boolean[] vis, int[] columnNum, int n, int step){ if(step == n-1){ // for(int i =0;i<n;i++){ // System.out.print(columnNum[i] + " "); // } // System.out.println(); cnt++; return; } for(int i=0;i<n;i++){ if(!vis[i]){ if(isRightPos(columnNum, n, step + 1, i)){ vis[i] = true; columnNum[step + 1] = i; dfs(vis, columnNum, n,step + 1); vis[i] = false; } } } } static boolean isRightPos(int[] columnNum, int n, int step, int pos){ for(int i=0;i<step;i++){ int x = i; int y = columnNum[i]; if(columnNum[i] == -1){ continue; } int x2 = step; int y2 = pos; if(!isOk(x, y, x2, y2)){ return false; } } return true; } // 是否同行，同列，同斜线 static boolean isOk(int x, int y, int x2, int y2){ if(x == x2 || y == y2){ return false; } int xCha = Math.abs(x2 - x); int yCha = Math.abs(y2 - y); if(xCha == yCha){ return false; } return true; } } /* 8 92 */
pos & -pos 或pos &（~pos + 1）的意思就是取pos最右边的1,再组成二进制数
pos 原数 0 0 0 0 1 0 0 0 原数 0 1 0 1 0 0 1 1 取反 1 1 1 1 0 1 1 1 取反 1 0 1 0 1 1 0 0 加1 1 1 1 1 1 0 0 0 加1 1 0 1 0 1 1 0 1 pos & -pos 与运算 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
eg: 4皇后问题
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 int nextColLim = colLim | mostRightOne = 0 0 0 1 = 1 // 左下角，只考虑下一行，所以向左移动 // <<(向左位移) 针对二进制，转换成二进制后向左移动3位，后面用0补齐 int nextLeftDiaLim = (leftDiaLim | mostRightOne) << 1 = 0 0 1 0 = 2 // 右下角，只考虑下一行，所以向右移动 // >>>(无符号右移) 无符号右移，忽略符号位，空位都以0补齐 int nextRightDiaLim = (rightDiaLim | mostRightOne) >>> 1 = 0 0 0 0 = 0
canPos = 1 1 0 0 = 12
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 int nextColLim = colLim | mostRightOne = 0 1 0 1 = 5 // 左下角，只考虑下一行，所以向左移动 // <<(向左位移) 针对二进制，转换成二进制后向左移动3位，后面用0补齐 int nextLeftDiaLim = (leftDiaLim | mostRightOne) << 1 = 1 1 0 0 = 12 // 右下角，只考虑下一行，所以向右移动 // >>>(无符号右移) 无符号右移，忽略符号位，空位都以0补齐 int nextRightDiaLim = (rightDiaLim | mostRightOne) >>> 1 = 0 0 1 0 = 2
canPos = 0
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws Exception { int n = sc.nextInt(); num2(n); System.out.println(res); } /** * 哪些位置可以放皇后 * 8皇后问题，则初始为 00000000 00000000 00000000 11111111， 后8位是1 * 32皇后问题，则初始为 11111111 11111111 11111111 11111111， 32位是1 * @param n * @return */ static void num2(int n){ if(n < 1 || n > 32){ return; } int upperLim = n == 32 ? -1 : (1 << n) - 1; process(upperLim, 0, 0, 0); } static int res = 0; /** * colLim 表示递归上一行，已经放置了哪些列，1表示放置了,其对那些列有影响 * leftDiaLim 表示递归上一行，已经放置了的 对 左下脚的影响 * rightDiaLim 表示递归上一行，已经放置了的 对 右下脚的影响 */ static void process(int upperLim, int colLim, int leftDiaLim, int rightDiaLim){ if(colLim == upperLim){ res ++; return; } // canPos 记录了哪些列可以放皇后 int canPos = ~(colLim | leftDiaLim | rightDiaLim); canPos = canPos & upperLim; while (canPos != 0){ // 获取最右边是1的位置，并清除canPos的该位置 int mostRightOne = canPos & (~canPos + 1); canPos -= mostRightOne; int nextColLim = colLim | mostRightOne; int nextLeftDiaLim = (leftDiaLim | mostRightOne) << 1; int nextRightDiaLim = (rightDiaLim | mostRightOne) >>> 1; process(upperLim, nextColLim, nextLeftDiaLim, nextRightDiaLim); } } } /* 1 1 8 92 */
https://leetcode-cn.com/problems/n-queens/comments/
class Solution { public List<List<String>> solveNQueens(int n) { int upperLimit = (1 << n) - 1; // 最后n位是1,表示能放置的，dfs过程中不变 int colLimit = 0; int leftLimit = 0; int rightLimit = 0; List<Integer> rows = new ArrayList<>(); dfs(n, rows,0, upperLimit, colLimit, leftLimit, rightLimit); return ans; } String getOneRow(int n, int col){ int num = -1; for(int i=1;i<=n;i++){ if((col >>> i) == 0){ num = i-1; break; } } StringBuffer sb = new StringBuffer(); for(int i=0;i<num;i++){ sb.append("."); } sb.append("Q"); for(int i=num+1;i<n;i++){ sb.append("."); } return sb.toString(); } List<List<String>> ans = new ArrayList<>(); // 列，左斜线，右斜线 void dfs(int n, List<Integer> rows, int curRow, int upperLimit, int colLimit, int leftLimit, int rightLimit){ if(colLimit == upperLimit && curRow < n){ return; } if(colLimit == upperLimit && curRow == n){ // 构造一个结果 List<String> one = new ArrayList<>(); for(int i=0;i<n;i++){ int col = rows.get(i); String rowStr = getOneRow(n, col); one.add(rowStr); } ans.add(one); return; } // 已经不能放的取反,剩下的就是能放的, 能放的进行dfs int canPos = ~(colLimit | leftLimit | rightLimit); canPos = canPos & upperLimit; while (canPos != 0){ // 取最右边的一个1 int rightPos = canPos & (~canPos + 1); canPos -= rightPos; int nextColLimit = colLimit | rightPos; int nextLeftLimit = (leftLimit | rightPos) << 1; int nextRightLimit = (rightLimit | rightPos) >>> 1; int len = rows.size(); rows.add(rightPos); dfs(n, rows, curRow + 1, upperLimit, nextColLimit, nextLeftLimit, nextRightLimit); rows.remove(len); } } }