用回溯但以不同的方式解决 N-Queens

Solving N-Queens with Backtracking but in different way

我是一个 16 岁的人，最近我正在解决 n-queens 问题，但我的代码给出了不同的 answers.Basically 我的代码的目的是将一个皇后放在特定的行上，然后标记左对角线以及右对角线和标记为 danger.And 的列，然后将其他皇后放在没有 danger.Please 的其他位置，简要解释我的代码中的问题是什么。

vector<vector<int>> v;
int c=0;

void solve(int y){
    if(y==v.size()){// base case
        c++;
        return ;
    }
    else{
        for(int i=0;i<v.size();i++){
            if(v[y][i]!= -1) continue;
            else{
                int a=y,b=i;
                while(a<v.size() && b<v[y].size()){// marking all right diagonals as danger
                    v[a][b]=y;
                    ++a;
                    ++b;
                }
                a=y,b=i;
                while(a<v.size() && b>=0){ // marking left diagonals as danger
                    v[a][b]=y;
                    ++a;
                    --b;
                }
                a=y,b=i;
                while(a<v.size()){// marking columns as danger
                    v[a][b]=y;
                    ++a;
                }
                solve(y+1);//recursive call and also the starting point of backtracking 
                a=y,b=i;
                while(a<v.size() && b<v[y].size()){
                    v[a][b]=-1;
                    ++a;
                    ++b;
                }
                a=y,b=i;
                while(a<v.size() && b>=0){
                    v[a][b]=-1;
                    ++a;
                    --b;
                }
                a=y,b=i;
                while(a<v.size()){
                    v[a][b]=-1;
                    ++a;
                }
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    v.resize(n,vector<int>(n,-1);
    solve(0);
    cout<<c<<endl;
}

编辑： 我修改了我的代码，然后我检查了回溯，我的问题是为什么我每次都进行 2 次调用

vector<vector<int>> v;
int c=0;

void solve(int y){
    if(y==v.size()){
        c++;
        return ;
    }
    else{
        for(int i=0;i<v.size();i++){
            if(v[y][i]!= -1) continue;
            
            for(int j=0;j<v[y].size();j++){
                v[y][j]=y; 
            }
            int a=y,b=i;
            while(a<v.size() && b<v[y].size()){
                v[a][b]=y;
                a++;
                b++;
            }
            a=y,b=i;
            while(a<v.size() && b>=0){
                v[a][b]=y;
                a++;
                b--;
            }
            a=y,b=i;
            while(a<v.size()){
                v[a][b]=y;
                a++;
            }
            // Inspecting before the recursion call
            cout<<"When y is "<<y<<endl;
            for(auto i:v){
                    for(int j:i){
                        cout<<j<<"  ";
                    }
                    cout<<endl;
            }
            solve(y+1);
            a=y,b=i;
            while(a<v.size() && b<v[y].size()){
                v[a][b]=-1;
                a++;
                b++;
            }
            a=y,b=i;
            while(a<v.size() && b>=0){
                v[a][b]=-1;
                a++;
                b--;
            }
            a=y,b=i;
            while(a<v.size()){
                v[a][b]=-1;
                a++;
            }
            for(int j=0;j<v[y].size();j++){
                v[y][j]=-1; 
            }
            // this is basically for seeing what is happening after the recursive call
            cout<<"When y is "<<y<<endl;
            for(auto i:v){
                    for(int j:i){
                        cout<<j<<"  ";
                    }
                    cout<<endl;
            }
        }
    }
}

请解释为什么每个 i 打印 4 次 :(

无需深入挖掘，您就会遇到一个根本问题：

你用你当前的递归深度标记从当前字段可到达的所有其他字段，并将所有这些无条件地重置为 -1。因此，您也清除了标记但未完成的先前递归。

没有深入研究代码，我注意到您没有标记列。

但是，引入它，您将面临非法覆盖之前专栏中设置的标记的风险：

q _ _ _ _ _ _ _
- + _ Q _ _ _ _
- - X - * - - -
- * - + - * - -
...

-: free field
_: implicit danger of any queen
q: first queen
+: danger of first queen
Q: second queen
*: danger of second queen
X: danger of second queen overwriting danger of previous queen

此外，您没有标记队列的列字段（只是从当前皇后向下）。引入这个，问题就更严重了。

因此您需要进行一些更改：

  1. 也要标记列。
  2. 仅当字段包含 -1 时才标记该字段
  3. 仅当它等于当前递归深度（相当于当前行）时才删除标记。
while(/*...*/) // for any loop before recursive call:
{
    if(v[a][b] == -1)
        v[a][b] = y;
}

同理，如果只有设置了当前递归，才需要去掉标记：

while(/*...*/) // for any loop after recursive call:
{
    if(v[a][b] == y)
        v[a][b] = -1;
}

顺便说一下（核心问题在这里解决，从现在开始遵循一些建议来改进你的代码——包括一个没有遭受覆盖问题的修改算法）：你可以组合你所有的 while 循环——在递归调用之前和之后分别 - 进入一个循环：

int a = i, b = i, max = v[y].size() - 1;
for(int j = y + 1; j < v.size(); ++j)
{
    if(v[j][i] == -1)
        v[j][i] = y;
    if(a > 0)
    {
        --a;
        if(v[j][a] == -1)
            v[j][a] = y;
    }
    if(b < max)
    {
        ++b;
        if(v[j][b] == -1)
            v[j][b] = y;
    }
}

如果你仔细观察，你会注意到循环在递归调用之前和之后没有区别——除了 -1 和 y 被交换。

因此您可以组合成一个单独的函数（或本地 lambda 以避免在外部可见），提供 -1, y 或 y, -1 作为参数：

// lambda example 
auto markFields = [](int row, int column, condition, value)
{
    // combined loops with y being row, i being column
    // or separate ones from your solution, just as you prefer
}

for(/*...*/)
{
    // ...
    markFields(y, i, -1, y);
    solve(y + 1);
    markFields(y, i, y, -1);
}

(如果你稍后在某个时候引入 class，更喜欢 private 辅助函数而不是 lambda；因为是私有的，它仍然对外部不可见，但 solve 函数的复杂性降低了。）

您可以避免覆盖以前迭代的标记的问题，同时如果您更改您的板表示，则可以提高效率：

  1. 行仍然被隐式标记
  2. 列由长度为 n
    3. 的单个数组表示
  3. NW-SE1 条对角线由长度为 2*n - 1
    4. 的数组表示
  4. NE-SW1 条对角线由长度为 2*n - 1
    5. 的数组表示

[1]罗盘点

您现在只需在适当的数组中设置一个标志（然后甚至不需要在递归之间进行区分）即可一次标记整个列或对角线。

列数组中的索引是微不足道的，只是我们循环计数器的值：columns[i]。

两个对角数组的索引有点复杂；同一 NW-SE 对角线上的字段的共同点是行和列之间的差异相同，因此您可以通过 y - i + n - 1 获得它们（您可以通过将数组扩大 1 并使用索引 0 来跳过 1 的减法作为哨兵）。

同一 NE-SE 对角线上的字段具有相同的行列总和，因此您可以通过 y + i 来识别这些字段。

你的循环可能如下所示（假设布尔值 arrays/vectors/...，初始化为全真，意味着 'free' 并且诊断数组扩大为一个标记）：

for(int i = 0; i < n; ++i)
{
    int nwse = y - i + n;
    int nesw = y + i;
    if(column[i] && nwseDiagonals[nwse] && neswDiagonals[nesw])
    {
        // can place a queen!
        column[i] = false;
        nwseDiagonals[nwse] = false;
        neswDiagonals[nesw] = false;
        solve(y + 1);
        column[i] = true;
        nwseDiagonals[nwse] = true;
        neswDiagonals[nesw] = true;
    }
}

我建议将此基础结构打包到 class 中，这样您可以获得更好的封装：

class Solver
{
public:
    Solver(size_t n)
        : n(n), c(0)
    {
        // vectors already constructed here
        columns.reserve(n);
        n *= 2;
        nwseDiagonals.reserve(n);
        neswDiagonals.reserve(n - 1);
    };

    void solve()
    {
        solve(0);
    }

private:
    size_t n;
    size_t c;

    // std::vector<bool> has a specialization packing multiple bits into
    // a single byte – saves memory, costs runtime as bits need to be
    // unpacked; choice left upon to you, but please the same for all...
    std::vector<char /* or bool */> columns;
    std::vector<char /* or bool */> nwseDiagonals;
    std::vector<char /* or bool */> neswDiagonals;

    void solve(size_t row)
    {
        // your implementation
    }
};

void demo()
{
    Solver s(8); // classic chess board...
    s.solve();
}

如果愿意，您也可以将 solve 函数设为静态。然后它看起来像这样：

static void solve(size_t n)
{
    Solver s(n);
    s.solve();
}

void demo()
{
    Solver::solve(8); // classic chess board
}

然后应该将构造函数移动到私有部分。

在这两种变体中，不希望 Solver 做任何输出，但 solve 函数 return 一些适当的结果（找到的解决方案的数量，所有解决方案的向量，. ..). IO 通常应该在外部完成，这提高了 class.

的可重用性