# N-Queens I &&II

N-Queens I

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

Solution 2. Non-Recursive

N-Queens II

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution 1. Recursive. DFS

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) {
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

Share