# 51.N-Queens

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/n-queens/

https://www.lintcode.com/problem/n-queens/description

## ้ข็ฎๆ่ฟฐ

``````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) {
return;
}

for (int col = 0; col < n; col++) {
if (isValid(cols, 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(".");
}
}