c - 确定回溯递归算法中的基本条件

Question

我正在解决 N 皇后问题，我们需要在 4 X 4 的棋盘上放置 4 个皇后，这样任何两个皇后都不能互相攻击。我之前试过这个，但我的方法不涉及回溯，所以我又试了一次。代码片段是

int size=4,i,j;
int arr[4][4];
int lastjindex[4]; // to store the last location which we may need to backtrack



void placeQueen(int i,int j)
{
    int availableornot=0;

    for(j=0;j<size;j++)
    {
        if(isAvailable(i,j)==1)
        {
            availableornot=1;
            break;
        }
    }

    if(availableornot==1)
    {
        arr[i][j]=1;
        lastjindex[i]=j;

        if((i+1)!=size)
        {
            placeQueen(i+1,0);
        }
    }

    else
    {
        // no column was availabe so we backtrack
        arr[i-1][lastjindex[i-1]]=0;
        placeQueen(i-1,lastjindex[i-1]+1);
    }
}

如果 arr[i][j] 没有受到攻击，isAvailable() 方法返回 1，否则返回 0。

int isAvailable(int i,int j)
{
    int m,n,flag=0;

    for(m=0;m<i;m++)
    {
        for(n=0;n<size;n++)
        {
            int k=abs(i-m);
            int l=abs(j-n);

            if(arr[m][j]==0 || arr[k][l]==0)
            {
                flag=1;
                break;
                // means that spot is available
            }
        }
    }
    return flag;
}

---

我从 main 中调用上面的方法

placeQueen(0,0);

我的程序编译成功，但打印全为零。

---

我的递归有问题吗？请帮助我更正我的代码，因为我正在尝试学习如何实现回溯算法!

---

此外，我无法确定结束递归的基本条件。这里怎么选择呢？

Answer 1

您发布的代码中没有打印。如果在回溯之后再打印，就会回到棋盘上没有皇后的初始状态。放置N个皇后后打印，这也是递归的结束条件。如果您只想打印一个解决方案，请在打印后退出，或者设置一个标志告诉调用者您已完成，因此您会一直弹出。如果您打印所有解决方案，那将包括反射和旋转。您可以通过在第一层仅将皇后放置在 size/2 以内来消除一个反射轴。

另外，你的代码有一些明显的逻辑错误，比如

arr[m][j]==0 || arr[k][l]==0

只有在文件并且没有沿对角线受到攻击时，才能放置皇后。使用调试器或将 printfs 添加到您的代码以跟踪它试图放置皇后的位置——这将帮助您找出它做错了什么。

除了错误之外，你的 isAvailable效率很低。您想知道 [i,j] 正方形是沿着文件还是对角线受到攻击。为此，您应该对前一个皇后的行进行一次循环 for (m = 0; m < i; m++) ，但你只需要三个测试，而不是一个循环，来检查文件和对角线。一旦您在文件或对角线上找到任何先前的皇后，您就完成了，并且正方形不可用——返回 false。 (忽略那些告诉你一个函数应该只有一个返回值的人——他们错了，在 SO 上进行了长时间的讨论，甚至对代码错误率的科学研究也证明了这一点。)只有在没有前任女王的情况下found 是可用的正方形。

你的 placeQueen也是错误的。对于一行中的每个 可用方 block ，您需要放置一个皇后然后递归，但您只是找到第一个可用方 block 。回溯是通过移除你放置的皇后然后返回来实现的……上一层的 placeQueen 将尝试下一个可用的位置。

再次跟踪代码以查看它在做什么。而且，更重要的是，仔细考虑所需的逻辑。用文字写下您的算法，说服自己它会解决问题，然后编写代码来执行该算法。