N-Queens
Problem
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:
[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]
Challenge
Can you do it without recursion?
Note
写一种常规方法好了：
首先对于放皇后的流程有一个概念：
结果数组
res的形式：包含所有满足条件的，长度为n(row行)的字符串数组cur；每个字符串代表一行的皇后摆法；首先，在主函数中向结果数组
res的一个子集cur，并初始化这个cur中所有元素为长度为n且所有字符都是'.'的字符串；然后调用helper函数；在
helper函数中，结果数组res，目标行数n，和基本子集cur都是确定的，唯一的变量是会被递归的当前行数row，我们会从基本子集cur中取出这一行进行修改：遍历这一行的每个元素，即遍历列数j，然后在第row行第j列的这个元素为'Q'时满足N皇后条件isValid(n, cur, row, j)的情况下，将这个元素设为'Q'。有点拗口？这样吧，先看看isValid(n, cur, row, col)的意思：isValid()就是当我们想在第i行j列放上Queen的时候，先遍历上面的i-1行，判断有没有能攻击到当前皇后的皇后。所以在
helper函数中，若之前的行中没有威胁到当前遍历到的第row行第j列这个皇后的其它皇后的话，就更新这一行并存入子集cur，然后递归下一行。递归之后，再将这个皇后换成字符'.'，以便在下一个循环中将第j+1个字符设为皇后并递归。当
helper函数第n-1次递归的时候，row == n，此时将已经完成皇后排列的当前子集cur放入res；那么res中总共有多少个子集cur呢？Move on to N-Queens II.
Solution
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
List<String> cur = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append('.');
for (int i = 0; i < n; i++) cur.add(sb.toString());
dfs(n, 0, cur, res);
return res;
}
public void dfs(int n, int row, List<String> cur, List<List<String>> res) {
if (row == n) {
List<String> copy = new ArrayList<>();
for (int i = 0; i < n; i++) copy.add(cur.get(i));
res.add(copy);
return;
}
for (int j = 0; j < n; j++) {
if (isValid(cur, n, row, j)) {
StringBuilder sb = new StringBuilder();
sb.append(cur.get(row));
sb.setCharAt(j, 'Q');
cur.set(row, sb.toString());
dfs(n, row+1, cur, res);
sb.setCharAt(j, '.');
cur.set(row, sb.toString());
}
}
}
public boolean isValid(List<String> cur, int n, int row, int col) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < n; j++) {
if (cur.get(i).charAt(j) == 'Q' && (j == col || Math.abs(row-i) == Math.abs(col-j))) return false;
}
}
return true;
}
}Better Solution, WAY BETTER...
public class Solution {
private List<List<String>> res;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
StringBuilder[] board = new StringBuilder[n];
for(int i =0;i<n;i++){ //initialize
board[i] = new StringBuilder();
for(int j=0;j<n;j++) board[i].append('.');
}
int [] visited = new int[n];
int[] set1 = new int[2*n]; // i+j
int[] set2 = new int[2*n]; // i-j
dfs(board,set1,set2,visited,0);
return res;
}
public void dfs(StringBuilder[] board,int[] set1,int[] set2,int [] visited,int idx){
int n = board.length;
if(idx==n){
List<String> a = new ArrayList<>();
for(int i =0;i<n;i++){
a.add(board[i].toString());
}
res.add(a);
return;
}
for(int j = 0;j<n;j++){
if(visited[j]==0&&set1[idx+j]==0&&set2[n+idx-j]==0){
visited[j] = 1;
set1[idx+j] = 1;
set2[n+idx-j] = 1;
board[idx].setCharAt(j,'Q');
dfs(board,set1,set2,visited,idx+1);
visited[j] = 0;
set1[idx+j] = 0;
set2[n+idx-j] = 0;
board[idx].setCharAt(j,'.');
}
}
}
}N-Queens II
Problem
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Example
For n=4, there are 2 distinct solutions.
Note
和N-Queens一模一样，用计数器统计能完整递归的次数：每次对子集cur递归到row == n时，只要计数器count++即可。
Solution
class Solution {
int count = 0;
int totalNQueens(int n) {
ArrayList<ArrayList<String>> res = new ArrayList();
ArrayList<String> cur = new ArrayList();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append('.');
for (int i = 0; i < n; i++) cur.add(sb.toString());
return helper(0, n, cur);
}
int helper(int row, int n, ArrayList<String> cur) {
if (row == n) count++;
for (int j = 0; j < n; j++) {
if (isValid(row, j, n, cur)) {
StringBuilder sb = new StringBuilder(cur.get(row));
sb.setCharAt(j, 'Q');
cur.set(row, sb.toString());
helper(row+1, n, cur);
sb.setCharAt(j, '.');
cur.set(row, sb.toString());
}
}
return count;
}
boolean isValid(int row, int col, int n, ArrayList<String> cur) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < n; j++) {
if (cur.get(i).charAt(j) == 'Q' && (col == j || Math.abs(row-i) == Math.abs(col-j))) return false;
}
}
return true;
}
}
Better Solution
public class Solution {
public static int count;
public int totalNQueens(int n) {
count = 0;
int[] visited = new int[n];
int[] set1 = new int[2*n]; //i+j
int[] set2 = new int[2*n]; // i-j
dfs(n, set1, set2, visited, 0);
return count;
}
public void dfs(int n, int[] set1,int[] set2,int[] visited, int idx){
if(idx == n){
count++;
return;
}
for(int j = 0;j < n;j++){
if(visited[j] == 0 && set1[idx+j] == 0 && set2[n+idx-j] == 0){
visited[j] = 1;
set1[idx+j] = 1;
set2[n+idx-j] = 1;
dfs(n,set1,set2,visited,idx+1);
visited[j] = 0;
set1[idx+j] = 0;
set2[n+idx-j] = 0;
}
}
}
}
