Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode N-Queens

Leetcode algorithms 第 51 题:N-Queens。

题目

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:

解答

N皇后问题,输出所有的答案。直接使用回溯算法,N皇后问题只需要在n的全排列中寻找合适的解即可,全排列中第i个位置的数表示第i行中皇后的位置,这样皇后的在每一行上肯定不会冲突,因为她们处于不同的行内,但她们在列上以及两条对角线上可能冲突,需要记录哪些列及哪些对角线上的位置是合法的:

  • 列:vsy[i]表示第i列是否有皇后
  • 主对角线:vsd1[i]表示行数和列数之和为i的主对角线上是否有皇后
  • 副对角线:vsd2[i]表示行数和列数之差再加上n-1为i的副对角线上是否有皇后

于是可以在根据这三个数组找到每次搜索中可以选择的位置,然后进行回溯搜索。

具体代码如下:

class Solution {
public:
    vector<bool> vsy, vsd1, vsd2; //列、主对角线、副对角线是否已有皇后
    vector<int> cur; //cur[i]:第i行皇后的位置
    
    void dfs(int x, int n, vector<vector<string>> &ans)
    { //当前行数,N大小,答案
        if (x == n) //找到一组解
        {
            vector<string> tem;
            for (int i = 0; i < n; i++)
            {
                string s;
                if (cur[i] > 0) s += string(cur[i], '.');
                s += "Q";
                if (n-1-cur[i] > 0) s += string(n-1-cur[i], '.');
                tem.push_back(s);
            }
            ans.push_back(tem);
            return ;
        }
        
        for (int i = 0; i < n; i++)
        {
            if (!vsy[i] && !vsd1[x+i] && !vsd2[n+x-i-1]) //列及两条对角线均没有皇后
            {
                vsy[i] = vsd1[x+i] = vsd2[n+x-i-1] = true;
                cur[x] = i;
                dfs(x+1, n, ans);
                vsy[i] = vsd1[x+i] = vsd2[n+x-i-1] = false; //回溯
            }
        }
    }
    vector<vector<string> > solveNQueens(int n) {
        cur.resize(n);
        
        vsy.resize(n); //初始化vsy
        for (int i = 0; i < n; ++i)
            vsy[i] = false;
        
        vsd1.resize(2*n); //初始化vsd1和vsd2
        vsd2.resize(2*n);
        for (int i = 0; i < 2 * n; ++i)
            vsd1[i] = vsd2[i] = false;
        
        vector<vector<string> > ans;
        dfs(0, n, ans);
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论