N-Queens 33

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.

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?

Solution

Recursion: 确定上一行Queen的位置，递归寻找下一行Queen的位置。寻找某一行Queen位置时，必须保证该行Queen占据的位置不和该行之前所有行的Queen有冲突，即不能在同一列，也不能在对角线。

Non-Recursion：之后补上

代码如下：

Recursion:

class Solution {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    ArrayList<ArrayList<String>> solveNQueens(int n) {
        // write your code here
        ArrayList<ArrayList<String>> resultList = new ArrayList<>();
        if (n <= 0) {
            return resultList;
        }
        int[] row = new int[n];
        //从第0行开始寻找Queen的位置
        solveNQueensCore(resultList, row, n, 0);
        return resultList;
    }

    private void solveNQueensCore(ArrayList<ArrayList<String>> resultList,
                              int[] row,
                              int n,
                              int index) {
        //前n行寻找完成，即找到一种solution
        if (index == n) {
            ArrayList<String> singleResult = translateString(row);
            resultList.add(singleResult);
            return;
        }
        //逐列寻找第index行Queen可能的位置
        for (int i = 0; i < n; i++) {
            if (isValid(row, index, i)) {
                //记录该行Queen可能的位置
                row[index] = i;
                //递归寻找下一行Queen可能的位置
                solveNQueensCore(resultList, row, n, index + 1);
                //将该位置复原，继续寻找下一个可能的答案
                row[index] = 0;
            }
        }
    }
    //将一种solution用string表示出来
    private ArrayList<String> translateString(int[] row) {
        ArrayList<String> resultList = new ArrayList<>();
        for (int i = 0; i < row.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < row.length; j++) {
                if (j == row[i]) {
                    sb.append('Q');
                }
                else {
                    sb.append('.');
                }
            }
            resultList.add(sb.toString());
        }
        return resultList;
    }
    //判断Queen在第rowNum行第columnNum列是否可行
    private boolean isValid(int[] row, int rowNum, int columnNum) {
        //需要保证和rowNum行之前所有行Queen不冲突
        for (int i = 0; i < rowNum; i++) {
            //判断列是否冲突
            if (row[i] == columnNum) {
                return false;
            }
            //判断对角线是否冲突
            if (Math.abs(row[i] - columnNum) == Math.abs(i - rowNum)) {
                return false;
            }
        }
        return true;
    }

}

Non-Recursion:

之后补上