LeetCode51. N-Queens（递归 / 回溯）

Hard
Accepted：135,267
Submissions：351,395

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:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

链接

https://leetcode.com/problems/n-queens

题意

给定一个整数n，求n皇后问题所有可能的解。n皇后问题指把n个皇后放在一个n*n的棋盘山使得任意两个皇后都不在一行、一列或对角线上。

题解

一个非常经典的问题，可以使用递归（回溯）来解决。我们采取的策略是每次在一行中找一个位置，一行一行寻找下去直到第n行。

一个关键问题是如何判断当前皇后摆放的位置是否和之前已放好的皇后之间产生了冲突。显然我们每行找一个位置，那么行之间不会存在冲突，至于列，我们可以使用一个标记数组，标记之前已经使用了哪些列，对于两条对角线，有一个很巧妙的方法，我们可以找在同一条对角线上的共性。

(0, 0)	(0, 1)	(0,2)	(0,3)
(1, 0)	(1, 1)	(1, 2)	(1, 3)
(2, 0)	(2, 1)	(2, 2)	(2, 3)
(3, 0)	(3, 1)	(3, 2)	(3, 3)

从上述表格可以发现，对于正对角线（即 \）从右上到左下的同一条线上的两数差值分别为-3 -2 -1 0 1 2 3 ，对于反对角线（即/）从左上到右下的同一条线上的两数之和分别为0 1 2 3 4 5 6，所以可以添加两个对角线的标记数组对此进行判断。

如果递归寻找下去产生冲突无法得到答案，那么就要进行回溯，将之前相应的标记都取消。从另一个位置开始接着寻找。

代码

Time Submitted	Status	Runtime	Memory	Language
11 hours ago	Accepted	12 ms	10.4 MB	cpp

class Solution {
private:
    vector<vector<string>> ans;
    vector<bool> vis, dia1, dia2;
    vector<string> trans(vector <int> & row)
    {
        int n = row.size();
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; ++i)
            board[i][row[i]] = 'Q';
        return board;
    }
    void solve(int n, int index, vector <int> & row)
    {
        if (index == n)
        {
            ans.push_back(trans(row));
            return ;
        }
        for (int i = 0; i < n; ++i)
        {
            if (!vis[i] && !dia1[index + i] && !dia2[index - i + n - 1])
            {
                row.push_back(i);
                vis[i] = true;
                dia1[index + i] = true; // 对角线
                dia2[index - i + n - 1] = true;
                solve(n, index + 1, row);
                vis[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
                row.pop_back();
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        ans.clear();
        vis = vector<bool>(n + 1, false);
        dia1 = vector<bool>(2*n + 1, false);
        dia2 = vector<bool>(2*n + 1, false);
        vector<int> row;
        solve(n, 0, row);
        return ans;
    }
};

The end.
2019年4月14日星期日