Question
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.."] ]
Stats
| Frequency | 3 |
| Difficulty | 4 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is one of the most classic problems of NP (to be precise, NP-hard).
A lot of NP problems are be solved using similar approach, for example: Sudoku, Combinations, Combination Sum, Permutation, Work Break II, Palindrome Partitioning…
I posted my code below. It is very standard solution.
Solution
My solution is similar to the one written in this post.
My code
public class Solution {
public List<String[]> solveNQueens(int n) {
List<String[]> ans = new ArrayList<String[]>();
if (n <= 0) {
return ans;
}
int[] map = new int[n];
helper(ans, map, 0, n);
return ans;
}
private void helper(List<String[]> ans, int[] map, int row, int n) {
if (row == n) {
ans.add(convert(map, n));
return;
}
for (int i = 0; i < n; i++) {
map[row] = i;
// check if map[row] conflicts with any row above
boolean valid = true;
for (int k = 0; k < row; k++) {
if (Math.abs(map[k] - map[row]) == row - k || map[k] == map[row]) {
// not valid!
valid = false;
break;
}
}
if (valid) {
helper(ans, map, row + 1, n);
}
}
}
private String[] convert(int[] map, int n) {
String[] strs = new String[n];
for (int i = 0; i < n; i++) {
StringBuilder str = new StringBuilder();
for (int a = 0; a < map[i]; a++) {
str.append('.');
}
str.append('Q');
for (int a = map[i] + 1; a < n; a++) {
str.append('.');
}
strs[i] = str.toString();
}
return strs;
}
}