博文中会简要介绍Leetcode P0052题目分析及解题思路。
“N-Queens II”是一道经典的深度优先搜索问题，即回溯法问题。直接使用DFS算法探索即可。
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
以下是Java的题解代码实现。
class Solution {
public int totalNQueens(int n) {
if (n <= 1)
return 1;
boolean[][] chessboard = new boolean[n][n];
this.dfs(chessboard, 0);
return this.solutions;
}
private int solutions = 0;
// Directions Mapping
// private int[][] directions = new int[][]
//{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1};
private void dfs(boolean[][] chessboard, int currRow) {
if (currRow >= chessboard.length) {
++this.solutions;
return;
}
for (int col=0; col<chessboard.length; ++col) {
if (this.validate(chessboard, currRow, col, chessboard.length)) {
chessboard[currRow][col] = true;
this.dfs(chessboard, currRow+1);
}
chessboard[currRow][col] = false;
}
}
private boolean validate(boolean[][] chessboard, int currRow, int currCol, int size) {
for (int[] di: directions) {
int nextRow = currRow+di[0];
int nextCol = currCol+di[1];
while (nextRow >= 0 && nextRow < size
&& nextCol >=0 && nextCol < size) {
if (chessboard[nextRow][nextCol])
return false;
nextRow += di[0];
nextCol += di[1];
}
}
return true;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int totalNQueens(int n) {
vector<vector<bool>> board(n, vector<bool>(n, false));
if (n > 0)
this->Dfs(board, n, 0);
return solutions;
}
private:
int solutions = 0;
bool Validate(const vector<vector<bool>> &board, int cur_row, int cur_col) {
int dr[] = {-1, -1, 1, 1, -1, 1, 0, 0};
int dc[] = {-1, 1, 1, -1, 0, 0, 1, -1};
int bound = board.size();
for (int di=0; di<8; ++di) {
int next_row = cur_row+dr[di];
int next_col = cur_col+dc[di];
while (next_row >= 0 && next_row < bound
&& next_col >= 0 && next_col < bound) {
if (board[next_row][next_col])
return false;
next_row += dr[di];
next_col += dc[di];
}
}
return true;
}
void Dfs(vector<vector<bool>> &board, int n, int cur_row) {
if (n == 0) {
this->solutions += 1;
return;
}
else {
for (int col=0; col<board[0].size(); ++col) {
if (this->Validate(board, cur_row, col)) {
board[cur_row][col] = true;
this->Dfs(board, n-1, cur_row+1);
board[cur_row][col] = false;
}
}
}
return;
}
};