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.
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
if(n == 0) return result;
backtrace(result, new ArrayList<String>(), 0, n, new boolean[n]);
return result;
}
public static void backtrace(List<List<String>> result, List<String> list, int level, int n, boolean[] used){
if(level == n) result.add(new ArrayList<String>(list));
else{
for(int i = 0; i < n; i++){
if(used[i]) continue;
if(isValid(list, level, i, n)){
list.add(createQueen(n, i));
used[i] = true;
backtrace(result, list, level + 1, n, used);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
}
public static boolean isValid(List<String> list, int row, int column, int n){
if(row > 0){
String cmp = list.get(row - 1);
for(int i = 0; i < row; i++)
if(list.get(i).charAt(column) == 'Q') return false;
int tempRow = row;
int tempCol = column;
while(--tempRow >= 0 && --tempCol >= 0){
if(list.get(tempRow).charAt(tempCol) == 'Q') return false;
}
tempRow = row;
tempCol = column;
while(--tempRow >= 0 && ++tempCol <= n-1)
if(list.get(tempRow).charAt(tempCol) == 'Q') return false;
}
return true;
}
private static String createQueen(int n, int index){
StringBuilder sb = new StringBuilder();
int i = 0;
for(; i < index; i++)
sb.append('.');
sb.append('Q');
for(++i; i < n; i++){
sb.append('.');
}
return sb.toString();
}
}这是一道基础的回溯问题，这次一开始就创建了char[][] map并全部设置为 '.'，然后通过回溯向中间插入‘Q’
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new LinkedList<>();
char[][] map = new char[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = '.';
}
}
backtrace(result, map, 0, n);
return result;
}
private void backtrace(List<List<String>> result, char[][] map, int i, int n){
if(i == n){
List<String> res = new LinkedList<>();
for(int p = 0; p < n; p++)
res.add(new String(map[p]));
result.add(res);
}else{
for(int j = 0; j < n; j++){
if(check(map, i, j)){
map[i][j] = 'Q';
backtrace(result, map, i + 1, n);
map[i][j] = '.';
}
}
}
}
private boolean check(char[][] map, int row, int col){
for(int i = 0; i < row; i++) if(map[i][col] == 'Q') return false;
for(int i = 0; i < col; i++) if(map[row][i] == 'Q') return false;
int i = row, j = col;
while(--i >= 0 && --j >= 0) if(map[i][j] == 'Q') return false;
while(--row >= 0 && ++col < map.length) if(map[row][col] == 'Q') return false;
return true;
}
}- Method 1: Search + bfs 3ms
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new LinkedList<>();
char[][] table = new char[n][n];
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) table[i][j] = '.';
dfs(result, table, 0, n);
return result;
}
public void dfs(List<List<String>> result, char[][] table, int row, int n){
if(row == n){
List<String> temp = new LinkedList<>();
for(int i = 0; i < n; i++){
temp.add(new String(table[i]));
}
result.add(temp);
return;
}
for(int i = 0; i < n; i++){
if(check(table, row, i, n)){
table[row][i] = 'Q';
dfs(result, table, row + 1, n);
table[row][i] = '.';
}
}
}
private boolean check(char[][] table, int row, int col, int n){
for(int i = 0; i < n; i++){
if(table[row][i] == 'Q') return false;
if(table[i][col] == 'Q') return false;
}
int tempRow = row, tempCol = col;
while(tempRow >= 0 && tempCol >= 0) if(table[tempRow--][tempCol--] == 'Q') return false;
while(row >= 0 && col < n) if(table[row--][col++] == 'Q') return false;
return true;
}
}- Method 1: dfs
class Solution { private: vector<vector<string>> res_; bool check(vector<string>& board, int row, int col, int n){ for(int i = 0; i < n; ++i){ if(board[row][i] == 'Q') return false; if(board[i][col] == 'Q') return false; } int tx = row, ty = col; while(tx >= 0 && ty >= 0) if(board[tx--][ty--] == 'Q') return false; tx = row; ty = col; while(tx >= 0 && ty < n) if(board[tx--][ty++] == 'Q') return false; return true; } void dfs(int row, vector<string>& board, int n){ if(row == n) res_.emplace_back(board); else{ for(int i = 0; i < n; ++i){ if(check(board, row, i, n)){ board[row][i] = 'Q'; dfs(row + 1, board, n); board[row][i] = '.'; } } } } public: vector<vector<string>> solveNQueens(int n) { res_ = vector<vector<string>>(); string line = ""; for(int i = 0; i < n; ++i) line += "."; vector<string> temp(n, line); dfs(0, temp, n); return res_; } };