简单来说就是在每次尝试第 i 行新的摆法、并且递归的 trying 了它的下一行之后,需要还原第 i 行的状态。输出棋盘则可以直接在每次判断是可行解之后w
#include <cmath> #include <iostream> #include <vector> using namespace std; // total:记录解;finishline:确认的行 int total = 0, finishline = 1; // row:竖直攻击; ls:斜杠攻击; rs:反斜杠攻击 void trying(long row, long ls, long rs, int current_row, vector<vector<bool>> &board) { if (row != finishline) // 开始新行 { long position = finishline & ~(row | ls | rs); while(position) // 若行间无位可放... { long pointline = position & -position; position -= pointline; // 放上皇后 board[current_row][(int)log2(pointline)] = 1; trying(row + pointline, (ls + pointline) << 1, (rs + pointline) >> 1, current_row + 1, board); // 不论上面的 trying 是否成功 // 我们都需要把这一行还原到之前的状态 board[current_row][(int)log2(pointline)] = 0; } } else { total++; // 输出棋盘 for (auto &row : board) { for (auto col : row) { cout << col; } cout << '\n'; } cout << '\n'; } } int main(int argc, char *argv[]) { int grid = 8; // 修改grid的话,1~31皇后都能解w finishline = (finishline << grid) - 1; // 初始化棋盘 调整好棋盘的大小 vector<vector<bool>> board; board.resize(grid); for_each(board.begin(), board.end(), [grid](vector<bool> &row) { row.resize(grid); }); trying(0, 0, 0, 0, board); cout << total << endl; }