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.
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.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Analysis
Code
public class Solution {
private void printres(List<List<String>> res, int[] state, int n){
List<String> list = new ArrayList<String>();
for (int i=0; i<n; i++){
char[] chars = new char[n];
Arrays.fill(chars, '.');
chars[state[i]] = 'Q';
String str = new String(chars);
list.add(str);
}
res.add(list);
}
private boolean isValid(int[] state, int r){
for (int i=0; i<r; i++){
if (state[i]==state[r] || (Math.abs(state[i]-state[r])==(r-i))) return false;
}
return true;
}
private void nqueens(List<List<String>> res, int[] state, int cur, int n){
if (cur==n) {printres(res, state, n); return;}
for (int i=0; i<n; i++){
state[cur]=i;
if (isValid(state,cur)){
nqueens(res, state, cur+1, n);
}
}
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<List<String>>();
int[] state = new int[n];
nqueens(res, state, 0, n);
return res;
}
}
Reference
Yu