Comment on page

51.N-Queens

51. N Queens

题目地址

题目描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other(Any two queens can't be in the same row, column, diagonal line).
​
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 '.' each indicate a queen and an empty space respectively.

代码

Approach 1: Recursion

Time: O(N!) Space: O(N)
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList();
if (n <= 0) return ans;
​
List<Integer> cols = new ArrayList();
dfs(ans, cols, n);
​
return ans;
}
​
private void dfs(List<List<String>> ans, List<Integer> cols, int n) {
if (cols.size() == n) {
ans.add(output(cols));
return;
}
​
​
for (int col = 0; col < n; col++) {
if (isValid(cols, col)) {
cols.add(col);
dfs(ans, cols, n);
cols.remove(cols.size() - 1);
}
}
}
​
private boolean isValid(List<Integer> cols, int col) {
int row = cols.size();
for (Integer r = 0; r < row; r++) {
Integer c = cols.get(r);
if (c == col) return false;
if (row - col == r - c) return false;
if (row + col == r + c) return false;
}
return true;
}
​
private List<String> output(List<Integer> cols) {
List<String> ans = new ArrayList();
int n = cols.size();
for (int r = 0; r < n; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < n; c++) {
if (c == cols.get(r)) {
sb.append("Q");
} else {
sb.append(".");
}
}
ans.add(sb.toString());
}
​
return ans;
}
}