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
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],
[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
Solution1: Recursion DFS, Permutation模板，判断条件换一下
ArrayList<ArrayList<String>> solveNQueens(int n) {
ArrayList<ArrayList<String>> result = new ArrayList<>();
if (n <= 0) {
return result;
}
int[][] chessBoard = new int[n][n];
solveNQueensHelper(chessBoard, 0, result);
return result;
}
//DFS
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<ArrayList<String>> result) {
if (row == chessBoard.length) {
result.add(toStringList(chessBoard));
return;
}
for (int col = 0; col < chessBoard[row].length; col++) {
if (isValid(chessBoard, row, col)) {
chessBoard[row][col] = 1;
solveNQueensHelper(chessBoard, row + 1, result);
chessBoard[row][col] = 0;
}
}
}
public boolean isValid(int[][] chessBoard, int row, int col) {
for (int i = 1; i <= row; i++) {
if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
(col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
chessBoard[row - i][col] == 1) {
return false;
}
}
return true;
}
public ArrayList<String> toStringList(int[][] chessBoard) {
ArrayList<String> result = new ArrayList<>();
for (int i = 0; i < chessBoard.length; i++) {
StringBuilder row = new StringBuilder();
for (int j = 0; j < chessBoard[i].length; j++) {
if (chessBoard[i][j] == 0) {
row.append('.');
} else {
row.append('Q');
}
}
result.add(row.toString());
}
return result;
}
Solution 2. Non-Recursive
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
For n=4, there are 2 distinct solutions.
Solution 1. Recursive. DFS
这里要注意的是 因为java的int和Integer类型都是传值不传reference，所以不能直接把int传进递归方法里，还是需要用一个链表, 或者用一个static variable
Solution 1. Recursive
public int totalNQueens(int n) {
ArrayList<Integer> result = new ArrayList<>();
if (n <= 0) {
return 0;
}
int[][] chessBoard = new int[n][n];
solveNQueensHelper(chessBoard, 0, result);
return result.size();
}
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<Integer> result) {
if (row == chessBoard.length) {
result.add(result.size() + 1);
return;
}
for (int col = 0; col < chessBoard[row].length; col++) {
if (isValid(chessBoard, row, col)) {
chessBoard[row][col] = 1;
solveNQueensHelper(chessBoard, row + 1, result);
chessBoard[row][col] = 0;
}
}
}
public boolean isValid(int[][] chessBoard, int row, int col) {
for (int i = 1; i <= row; i++) {
if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
(col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
chessBoard[row - i][col] == 1) {
return false;
}
}
return true;
}
Solution 2. Non-Recursive
