【n皇后】经典回溯算法问题

• The n-queens puzzle is the problem of placing n queens on an n x 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
• 利用回溯算法，对棋盘进行逐行遍历
• class Solution {private: vector> res; void backtracking(int n, int row, vector& chessboard) { if (row == n) { res.emplace_back(chessboard); return; } for (int col = 0; col < n; ++col) if (isValid(row, col, chessboard, n)) { chessboard[row][col] = ‘Q’; backtracking(n, row + 1, chessboard); chessboard[row][col] = ‘.’; } } bool isValid(int row, int col, vector& chessboard, int n) { for (int i = 0; i < row; ++i) if (chessboard[i][col] == ‘Q’) return false; for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i—, j—) if (chessboard[i][j] == ‘Q’) return false; for (int i = row - 1, j = col + 1; i >= 0 && j < n; i—, j++) if (chessboard[i][j] == ‘Q’) return false; return true; }public: vector> solveNQueens(int n) { res.clear(); vector chessboard(n, string(n, ‘.’)); backtracking(n, 0, chessboard); return res; }};