leetcode--51. N-Queens

1、问题描述：

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.."]
]

 2、边界条件：无

3、思路：先在第一行尝试放Q，放之前要判断下该位置是否安全，不会受到其他Q的攻击。安全的话，就在第二行尝试放Q。

当然第一行的N列，即N个位置挨个尝试放，放上去之后就放下一行，下一行是同样的方法，从而生成Level-(N-1)问题，形成递归。

base case: 放到第N行（从0开始），则该值有效，存起来；2、如果一行都不能放，不保存结果，结束，返回上一层。

4.代码实现

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        solveQueens(results, new ArrayList<String>(), n, 0);
        return results;
    }
    //implement base function first
    public void solveQueens(List<List<String>> results, List<String> cur, int n, int row) {
        if (row == n) {//finished when index == n
            results.add(new ArrayList<String>(cur));
            return;
        }
        char[] curLine = new char[n];
        for (int i = 0; i < n; i ++) {//初始化字符数组，有时遍历不到，所以提前赋为'.'
            curLine[i] = '.';
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(cur, n, row, col)) {
                curLine[col] = 'Q';
                cur.add(cur.toString()); //这里转换错误，应该用new String(curLine)
                solveQueens(results, cur, n, row + 1);
                curLine[col] = '.';
            } else {  //前面for循环已经赋值'.'，else可以去掉了
                curLine[col] = '.'; 
            }
        }
    }
    
    public boolean isSafe(List<String> result, int n, int row, int col) {
        for (int i = 0; i < row - 1; i++) {//i < row是从0-->row - 1，也就是row的前面的行
            if (result.get(i).charAt(col) == 'Q') {
                return false;
            }
            
            int temp = i + col - row;
            if (temp >= 0 && temp < n && result.get(i).charAt(temp) == 'Q') {
                return false;
            }
            temp = row + col - i;
            if (temp >= 0 && temp < n && result.get(i).charAt(temp) == 'Q') {
                return false;
            }
        }
        return true;
    }
}

 修改后：

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        solveQueens(results, new ArrayList<String>(), n, 0);
        return results;
    }
    //implement base function first
    public void solveQueens(List<List<String>> results, List<String> cur, int n, int row) {
        if (row == n) {//finished when index == n
            results.add(new ArrayList<String>(cur));
            return;
        }
        char[] curLine = new char[n];
        for (int i = 0; i < n; i ++) {
            curLine[i] = '.';
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(cur, n, row, col)) {
                curLine[col] = 'Q';
                cur.add(new String(curLine));
                solveQueens(results, cur, n, row + 1);
                curLine[col] = '.';
                cur.remove(cur.size() - 1);
            }
        }
    }
    
    public boolean isSafe(List<String> result, int n, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (result.get(i).charAt(col) == 'Q') {
                return false;
            }
            int temp = i + col - row;
            if (temp >= 0 && temp < n && result.get(i).charAt(temp) == 'Q') {
                return false;
            }
            temp = row + col - i;
            if (temp >= 0 && temp < n && result.get(i).charAt(temp) == 'Q') {
                return false;
            }
        }
        return true;
    }
}

解法2：先把台面设为二维数组char[][] board = new char[n][n]

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        char[][] board = new char[n][n];//把台面转为二维数组
        for (int i = 0; i < n; i++) {//初始化台面
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        solveQueens(results, board, 0);
        return results;
    }

    //implement base function first
    public void solveQueens(List<List<String>> results, char[][] board, int row) {
        if (row == board[0].length) {//finished when index == n
            saveResult(results, board);
            return;
        }
        for (int col = 0; col < board[0].length; col++) {//可以用board.length
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q';
                solveQueens(results, board, row + 1);
                board[row][col] = '.';//恢复现场
            }
        }
    }

    public void saveResult(List<List<String>> results, char[][] board) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < board[0].length; i++) {
            result.add(new String(board[i]));//将数组转为字符串对象 new String(char[] board[i])
        }
        results.add(result);
    }

    public boolean isSafe(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
            int length = board[0].length;
            int temp = i + col - row;//对角线，可以计算出来
            if (temp >= 0 && temp < length && board[i][temp] == 'Q') {
                return false;
            }
            temp = row + col - i;//对角线，可以计算出来
            if (temp >= 0 && temp < length && board[i][temp] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

5、时间复杂度：O(N^2)；空间复杂度： ~~

课外知识：将数组转为字符串对象 new String(char[] board[i])

还有其他几种解法，后面补充。