博文中会简要介绍Leetcode P0051题目分析及解题思路。
“N-Queens”是其实算是p0052的变形题。p0052只需要统计解法个数，而这一道题需要统计所有的解法。和p0052一样，直接使用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 all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
以下是Java的题解代码实现。
class Solution {
public List<List<String>> solveNQueens(int n) {
if (n == 0)
return this.solutions;
List<StringBuilder> board = new ArrayList<>();
for (int count=0; count<n; ++count) {
StringBuilder row = new StringBuilder();
for (int itr=0; itr<n; ++itr)
row.append('.');
board.add(row);
}
this.dfs(board, 0);
return this.solutions;
}
private List<List<String>> solutions = new ArrayList<>();
// 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(List<StringBuilder> chessboard, int currRow) {
if (currRow >= chessboard.size()) {
List<String> solution = chessboard.stream().map((row) -> row.toString()).collect(Collectors.toList());
this.solutions.add(solution);
return;
}
for (int col=0; col<chessboard.size(); ++col) {
if (this.validate(chessboard, currRow, col, chessboard.size())) {
chessboard.get(currRow).setCharAt(col, 'Q');
this.dfs(chessboard, currRow+1);
}
chessboard.get(currRow).setCharAt(col, '.');
}
}
private boolean validate(List<StringBuilder> 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.get(nextRow).charAt(nextCol) == 'Q')
return false;
nextRow += di[0];
nextCol += di[1];
}
}
return true;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
if (n > 0)
this->Dfs(board, n, 0);
return solutions;
}
private:
vector<vector<string>> solutions;
bool Validate(const vector<string> &board, int cur_row, int cur_col) {
int dr[] = {-1, -1, 1, 1};
int dc[] = {-1, 1, 1, -1};
int bound = board.size();
// Validate diagonal
for (int di=0; di<4; ++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] == 'Q')
return false;
next_row += dr[di];
next_col += dc[di];
}
}
// Validate colume
for (int row=0; row<cur_row; ++row) {
if (board[row][cur_col] == 'Q')
return false;
}
return true;
}
void Dfs(vector<string> &board, int n, int cur_row) {
if (n == 0) {
solutions.push_back(board);
return;
}
else {
for (int col=0; col<board[0].length(); ++col) {
if (this->Validate(board, cur_row, col)) {
board[cur_row][col] = 'Q';
this->Dfs(board, n-1, cur_row+1);
board[cur_row][col] = '.';
}
}
}
return;
}
};