N皇后问题——记录下那些老死不相往来的N个女人的位置吧

于是在N个女人的老死不相往来-n皇后问题代码的基础上,增加了输出那N个老死不相往来的女人的位置的代码~

简单来说就是在每次尝试第 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;
}

“N皇后问题——记录下那些老死不相往来的N个女人的位置吧”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.