N皇后与回溯递归

题目具体思路以行(row)为基准开始递归回溯1、引入哈希集合进行快速“查重”2、利用N位二进制整数辅助“查重” p.s.:回溯算法汇总经典例题单词搜索 链接: LeetCode51题N皇后.

题目

N×N的棋盘里要放N个皇后，确保所有皇后都不在同一行、同一列、同一主对角线和同一副对角线上。 求所有可能的不同摆放方案。 图例：8皇后的一种解 每一种解法包含一个明确的 n 皇后问题的棋子放置方案， 该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

具体思路

以行(row)为基准开始递归回溯

回溯的具体做法是： 1、初始化：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。 2、递归：每次新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。 3、保存解：当 N 个皇后都放置完毕，则找到一个可能的解。 4、回溯：对最近的一行进行清空，查看是否有可用的解，继续进行配置。

由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有 N−1列可以选择，第三个皇后最多有 N−2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N! 种，遍历这些情况的时间复杂度是 O(N!)。 以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在 O(1) 的时间内判断一个位置是否可以放置皇后，算法的总时间复杂度都是 O(N!)。

1、引入哈希集合进行快速“查重”

哈希集合的方法：

class Solution { public: vector<vector<string>> solveNQueens(int n) { // 给出一个矩阵数组容器 auto solutions = vector<vector<string>>(); // 给出记录各行 皇后 所在列的数组 auto queens = vector<int>(n, -1); // 分别建立列、对角线1、2的哈希集合（存储嫌弃皇后位置） auto columns = unordered_set<int>(); auto diagonals1 = unordered_set<int>(); auto diagonals2 = unordered_set<int>(); // 回溯（答案、已安置皇后列位置、剩余皇后数量、目前皇后行序号、列集合、对角线1、2集合） backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2); return solutions; } void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) { // 到达第n行时，保存结果 if (row == n) { vector<string> board = generateBoard(queens, n); solutions.push_back(board); } else { for (int i = 0; i < n; i++) { // 如果列上已有 if (columns.find(i) != columns.end()) { continue; } // 如果主对角线上有 int diagonal1 = row - i; if (diagonals1.count(diagonal1)==1) { continue; } // 如果副对角线上有 int diagonal2 = row + i; if (diagonals2.count(diagonal2)) { continue; } // 满足都没有则保存 // 并将列、对角线1、2计入哈希集合 queens[row] = i; columns.insert(i); diagonals1.insert(diagonal1); diagonals2.insert(diagonal2); // 行数加1，继续 backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2); // 回溯还原操作(实现寻找多解) queens[row] = -1; columns.erase(i); diagonals1.erase(diagonal1); diagonals2.erase(diagonal2); } } } // 将queen记录列序号的数组转换成矩阵 vector<string> generateBoard(vector<int> &queens, int n) { auto board = vector<string>(); for (int i = 0; i < n; i++) { string row = string(n, '.'); row[queens[i]] = 'Q'; board.push_back(row); } return board; } };

2、利用N位二进制整数辅助“查重”

位运算的方法：

class Solution { public: vector<vector<string>> solveNQueens(int n) { // 给出一个矩阵数组容器 auto solutions = vector<vector<string>>(); // 存放皇后的摆放位置 auto queens = vector<int>(n, -1); // 四个零分别代表，正在处理的皇后标号，列记录、主副对角线记录 solve(solutions, queens, n, 0, 0, 0, 0); return solutions; } void solve(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, int columns, int diagonals1, int diagonals2) { // 输出 if (row == n) { auto board = generateBoard(queens, n); solutions.push_back(board); } else { // ((1 << n) - 1)：取n个1;(32位处理器中，n最大等于31) int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2)); // 每次获得可以放置皇后的位置中的最低位，并将该位的值置成 0，尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置 while (availablePositions != 0) { // x & (−x) 可以获得 x 的二进制表示中的最低位的 1 的位置 int position = availablePositions & (-availablePositions); // x & (x−1) 可以将 x 的二进制表示中的最低位的 1 置成 0。 availablePositions = availablePositions & (availablePositions - 1); // __builtin_ctz一种高效位运算方法：返回从低位开始的连续零的个数 int column = __builtin_ctz(position); // 放入皇后 queens[row] = column; // 递归，查重二进制数与position进行或运算，主斜线向右移动，副斜线向左移动 solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) >> 1, (diagonals2 | position) << 1); // 回溯 queens[row] = -1; } } } vector<string> generateBoard(vector<int> &queens, int n) { auto board = vector<string>(); for (int i = 0; i < n; i++) { string row = string(n, '.'); row[queens[i]] = 'Q'; board.push_back(row); } return board; } };

p.s.:

<stdio.h>库中的位运算高效函数：

•int __builtin_ffs (unsigned int x) 返回x的最后一位1的是从后向前第几位 比如7368（1110011001000）返回4。

•int __builtin_clz (unsigned int x) 返回前导的0的个数。 比如7368（1110011001000）返回0。

•int __builtin_ctz (unsigned int x) 返回后面的0个个数，和__builtin_clz相对。 比如7368（1110011001000）返回3。

•int __builtin_popcount (unsigned int x) 返回二进制表示中1的个数。 比如7368（1110011001000）返回6。

•int __builtin_parity (unsigned int x) 返回x的奇偶校验位，也就是x的1的个数模2的结果。 比如7368（1110011001000）返回0。

此外，这些函数都有相应的usigned long和usigned long long版本，只需要在函数名后面加上l或ll就可以了，比如int __builtin_clzll。

转载自: https://blog.csdn.net/yuer158462008/article/details/46383635.

回溯算法汇总

回溯算法可以看成是暴力算法的升级版 1其目的是从解决问题每一步的所有可能选项里系统地选出一个可行的解决方案 2适合于解决多个步骤组成的问题，且每个步骤包含多个选项。

经典例题

单词搜索

链接：LeetCode76. 描述：给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例： board = [ [‘A’,‘B’,‘C’,‘E’], [‘S’,‘F’,‘C’,‘S’], [‘A’,‘D’,‘E’,‘E’] ]

给定 word = “ABCCED”, 返回 true 给定 word = “SEE”, 返回 true 给定 word = “ABCB”, 返回 false

1、针对word首字母对board进行循环并递归 1.1、若对word首字母的递归结果返回true，则查到word 1.2、若对word首字母的递归结果返回false，则更新board下一值为word开头 2、若board遍历完仍未true，则返回false

递归、[board， word， i， j， wordcnt] (1)、越界与不匹配的判断 (2)、查到最终项的判断 (3)、缓存并更改当前board为不可用 (4)、对4邻域进行递归查询 (4.1)、若存在一个true， 则恢复并返回true(一定由(2)触发) (5)、恢复并返回false

class Solution { public: bool exist(vector<vector<char>>& board, string word) { // unnecessary int len = word.size(); if (!len) return false; int row = board.size(); if (!row) return false; int col = board[0].size(); for (int i=0; i<row; i++){ for (int j=0; j<col; j++){ if(dfs(board, word, i, j, 0)) return true; } } return false; } bool dfs(vector<vector<char>>& board, string word, int i, int j, int cnt){ // 越界与匹配判断 if (i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j]!=word[cnt]) return false; // 中止判断 if (cnt == word.size()-1) return true; char temp = board[i][j]; board[i][j] = '\0'; if (dfs(board, word, i+1, j, cnt+1) ||dfs(board, word, i-1, j, cnt+1) ||dfs(board, word, i, j+1, cnt+1) ||dfs(board, word, i, j-1, cnt+1)) { board[i][j] = temp; return true; } board[i][j] = temp; return false; } };