回溯算法示例2-n皇后问题

上次分享过回溯问题的示例数独问题求解，今天向大家介绍一个类似的问题，n皇后问题，问题的来源是国际象棋中的皇后的摆法，两个皇后不能直面水平，垂直，对角线，否则不满足皇后摆放的要求。

这里也采用回溯的思路，假设为8皇后问题，从第一行开始摆放，用变量记录当前摆放行的candidate位置（记为valid_pos_），并且记录从第一行到当前行摆放的位置记录（path，path[i]即为第i行摆放的皇后的位置值）。我们的第一个函数即为根据已经摆放的path（前面已经摆放的行）去获取当前行的candidates，实现逻辑即为针对每一个前面的行的位置，计算其在当前行不可行的位置（竖直，对角线的位置），具体的代码如下。

std::vector<bool> getCandidatePos(int n, std::vector<int>path)
{
    //std::vector<int>candidate_pos_;
    std::vector<bool>valid_pos_(n, true);
    for(int i = 0; i < path.size(); i++)
    {
        int his_row = i, his_col =path[i];
        int row_delta = path.size()-his_row;
        valid_pos_[his_col] = false;
        if(his_col -row_delta >= 0)
        {
            valid_pos_[his_col-row_delta] = false;
        }
        if(his_col + row_delta < n)
        {
            valid_pos_[his_col+row_delta] = false;
        }
    }
    return valid_pos_;
}

其中正式的递归回溯过程的示例代码如下：

void solveNQueensv1(int n, std::vector<int>path, std::vector<std::vector<int>>&valid_results)
{
    if(path.size() == n)
    {
        valid_results.push_back(path);
        return;
    }
    std::vector<bool>valid_pos_ = getCandidatePos(n, path);
    //bool has_valid_pos = false;
    for(int i = 0; i < valid_pos_.size(); i++)
    {
        if(valid_pos_[i] == true)
        {
            //has_valid_pos = true;
            path.push_back(i);
            solveNQueensv1(n, path, valid_results);
            path.pop_back();
        }
    }
}

最后完整串起来的代码为：

std::vector<std::vector<std::string>> solveNQueens(int n) {
    std::vector<std::vector<int>>valid_results;
    std::vector<int>path;
    std::vector<std::vector<std::string>> results;
    solveNQueensv1(n, path, valid_results);
    for(int i =0; i < valid_results.size(); i++)
    {
        std::cout << "**************" << i+1 << " solution is :" << std::endl;
        std::vector<std::string>cur_solution_;
        for(int j = 0; j <n; j++)
        {
            //cur_solution_ += valid_results[i][j]
            std::string row_pos_;
            for(int m = 0; m < n; m++)
            {
                if(valid_results[i][j] == m)
                {
                    row_pos_ +="Q";
                }else{
                    row_pos_ +="* ";
                }
            }
            cur_solution_.push_back(row_pos_);
            std::cout << row_pos_ << std::endl;
        }
        results.push_back(cur_solution_);
    }
    return results;
}

int main()
{
    std::vector<std::vector<std::string>>results;
    int n = 8;
    results = solveNQueens(n);
    return 0;
}

完整的代码请参考链接： data-structures-algorithms/backtracking/n-queens.cpp at main · kindlytree/data-structures-algorithms (github.com)