题目描述

52. N-Queens II

回溯法 

这道题与第51题是一样的。51. N-Queens-CSDN博客

class Solution {int columns;  //从低位到高位起算，第i位为0表示棋盘第i列可以放置皇后，第i位为1表示棋盘第i列不能放置皇后//边长为n的棋盘分别有2n-1条正斜线和反斜线。int diagnals1;//反斜线（从右上角到左下角）。第i位表示第i条反斜线能否放置皇后int diagnals2;//正斜线（从左上角到右下角）。含义同上int res = 0;
public:int totalNQueens(int n) {columns = 0;diagnals1 = 0;diagnals2 = 0;backtrack(n,0);return res;}void backtrack(int n,int row){if(row==n){res++;return;}for(int col = 0;col <n;col++){if(columns &(1<<col))continue;int diag1 = row+col;if(diagnals1 &(1<<diag1))continue;int diag2 = row-col+(n-1);if(diagnals2 &(1<<diag2))continue;columns |= (1<<col);diagnals1 |= (1<<diag1);diagnals2 |= (1<<diag2);backtrack(n,row+1);columns &= (~(1<<col));diagnals1 &= (~(1<<diag1));diagnals2 &= (~(1<<diag2)); }}
};