| 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.."
- ]
- ]
Can you do it without recursion?
Note
虽然Challenge要求不用recursion，但是我呢比较没出息，就写一种常规方法好了：
首先对于放皇后的流程有一个概念：
结果数组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呢？请看下一期走近科学，N-Queens II。
Solution- class Solution {
- ArrayList<ArrayList<String>> solveNQueens(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());
- helper(n, 0, cur, res);
- return res;
- }
- public void helper(int n, int row, ArrayList<String> cur, ArrayList<ArrayList<String>> res) {
- if (row == n) {
- ArrayList<String> toAdd = new ArrayList();
- for (int i = 0; i < cur.size(); i++) toAdd.add(cur.get(i));
- res.add(toAdd);
- return;
- }
- for (int j = 0; j < n; j++) {
- if (isValid(n, cur, row, j)) {
- StringBuilder sb = new StringBuilder(cur.get(row));
- sb.setCharAt(j, 'Q');
- cur.set(row, sb.toString());
- helper(n, row+1, cur, res);
- sb.setCharAt(j, '.');
- cur.set(row, sb.toString());
- }
- }
- }
- public boolean isValid(int n, ArrayList<String> cur, 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;
- }
- };
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;
- }
- }
|
