import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class NQueens {
public List> solveNQueens(int n) {
List> result = new LinkedList<>();
/**
* 这里f[i]表示第i行皇åŽåº”è¯¥æ”¾ç½®åœ¨ç¬¬å‡ åˆ—
*/
int[] f = new int[n];
dfs(f, result, 0);
return result;
}
private void dfs(int[] f, List> result, int row) {
if (row == f.length) {
List list = new LinkedList<>();
char[] c = new char[f.length];
for (int i = 0; i < f.length; i++) {
Arrays.fill(c, '.');
for (int j = 0; j < f.length; j++) {
if (j == f[i]) {
c[j] = 'Q';
break;
}
}
list.add(String.valueOf(c));
}
result.add(list);
}
/**
* 对于当å‰ç¬¬row行，一列一列地å°è¯•æ”¾ç½®çš‡åŽï¼Œçœ‹æ˜¯å¦åˆæ³•ï¼Œj表示列，如果åˆæ³•åˆ™ä¿å˜åˆ°fä¸
*/
for (int j = 0; j < f.length; j++) {
if (isValid(f, row, j)) {
/**
* 第row行皇åŽåº”该放置在第j列
*/
f[row] = j;
/**
* å†æ¥çœ‹ä¸‹ä¸€è¡Œ
*/
dfs(f, result, row + 1);
/**
* 这里ä¸ç”¨break，还è¦å°è¯•å…¶å®ƒå¯èƒ½
*/
}
}
}
private boolean isValid(int[] f, int row, int col) {
for (int i = 0; i < row; i++) {
if (f[i] == col) {
return false;
}
if (Math.abs(i - row) == Math.abs(f[i] - col)) {
return false;
}
}
return true;
}
}