【回溯网格状态压缩】52. N 皇后 II

本文涉及知识点

回溯网格状态压缩

LeetCode52. N 皇后 II

n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。
示例 1：
在这里插入图片描述

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
在这里插入图片描述

输入：n = 1
输出：1

提示：
1 <= n <= 9

回溯

皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。也就是同一行、同一列、同一斜线只能有一个皇后。
同一行：y相同，同一列x相同。正对交线:x-y 相同，反对角线x+y相同。
x,y $\in$ [0,n) x-y $\in$ [-(n-1),n-1] $\rightarrow$ x-y+(n-1) $\in$ [0,2n-1) x+y $\in$ [0,2n-1)
用xs,ys,sub,and 分别对应的行列是否占用。
一行只能有一个皇后，n行放n个皇后，故每行有且只有一个皇后。
时间复杂度：不好计算，和数据相关性非常大。由于n最大是9。直接试试9是否超时。

代码

核心代码

class Solution {
public:int totalNQueens(int n) {this->m_iN = n;DFS(0);return m_iRet;}bool Fill(int y, int x) {if ((1 << y) & m_iYMask) { return false; };if ((1 << x) & m_iXMask) { return false; };if ((1 << (x + y)) & m_iAddMask) { return false; };const int iSub = m_iN - 1 + (x - y);if ((1 << iSub) & m_iSubMask) { return false; };m_iYMask |= (1 << y);m_iXMask |= (1 << x);m_iAddMask |= (1 << (x + y));m_iSubMask |= (1 << iSub);return true;};void UnFill (int y, int x) {const int iSub = m_iN - 1 + (x - y);m_iYMask &= ~(1 << y);m_iXMask &= ~(1 << x);m_iAddMask &= ~(1 << (x + y));m_iSubMask &= ~(1 << iSub);};void DFS (const int iHasDoRow) {if (iHasDoRow == m_iN) {m_iRet++;return;}for (int x = 0; x < m_iN; x++) {if (!Fill(iHasDoRow, x)) { continue; }DFS(iHasDoRow + 1);UnFill(iHasDoRow, x);}};int m_iN;int m_iRet = 0;int m_iXMask = 0, m_iYMask = 0, m_iSubMask = 0, m_iAddMask = 0;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{{Solution slu;auto res = slu.totalNQueens(1);Assert(1, res);}{Solution slu;auto res = slu.totalNQueens(2);Assert(0, res);}{Solution slu;auto res = slu.totalNQueens(3);Assert(0, res);}{Solution slu;auto res = slu.totalNQueens(4);Assert(2, res);}	{Solution slu;auto res = slu.totalNQueens(5);Assert(10, res);}{Solution slu;auto res = slu.totalNQueens(6);Assert(4, res);}{Solution slu;auto res = slu.totalNQueens(7);Assert(40, res);}{Solution slu;auto res = slu.totalNQueens(8);Assert(92, res);}{Solution slu;auto res = slu.totalNQueens(9);Assert(352, res);}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛