1

NQueen 问题是回溯的一个著名例子。从源代码阅读后，我尝试了以下代码片段。

int isSafe(int k,int i,int *x)
{
    int j;
    for(j=0;j<k;j++)
    {
              //old queen is placed at jth row of x[j] column
              //new queen to be placed at kth row of ith column
            if(i==x[j] || abs(k-j)==abs(i-x[j]))
                    return 0;
    }
    return 1;
}

int Nqueen(int k, int* sol, int N)
{
    int col;
    if( k == N )
    {
            printSol(sol,N);
            return 1;
    }
    else
    {
            for(col = 1;col <= N; col++)  //determines appropriate column number of the kth queen to be placed
            {
                    if( isSafe(k,col,sol) )
                    {
                            sol[k] = col;
                            if( Nqueen(k+1, sol, N) )
                                    return 1;
                            sol[k] = 0; // backtrack
                    }
            }
            return 0; // solution not possible
    }
}

我得到的输出为： 

1 5 8 6 3 7 2 4

但是，当我评论回溯的语句时，我会毫无问题地得到相同的输出。

int Nqueen(int k, int* sol, int N)
{
    int col;
    if( k == N )
    {
            printSol(sol,N);
            return 1;
    }
    else
    {
            for(col = 1;col <= N; col++)  //determines appropriate column number of the kth queen to be placed
            {
                    if( isSafe(k,col,sol) )
                    {
                            sol[k] = col;
                            if( Nqueen(k+1, sol, N) )
                                    return 1;
                            // sol[k] = 0; <-------------- Notice this change
                    }
            }
            return 0;
    }
}

究竟是什么让 NQueen 成为回溯问题？

这不是一个简单的递归方法吗？

4

3 回答 3

6

这sol[k] = 0不是回溯部分。回溯是在递归调用中完成的：if( Nqueen(k+1, sol, N) ).

回溯的想法是一种详尽的搜索——你试图搜索所有的可能性，直到找到一个。在这里，您正在尝试棋盘中所有可能的皇后分配，如果仍然安全，请“继续”。如果你发现它不安全，你会从递归中返回失败，并尝试下一个选项。

我相信注释掉的行只确保如果没有找到解决方案，则结果数组是[0,...,0]，而不是一些无意义的数组。

于 2012-08-22T10:06:44.360 回答
1

回溯问题是一种编程范式，您可以在其中尝试每一种可能的组合。然后对于每个组合，您检查到目前为止的组合是否正确。以下是 N（或 8）皇后问题的几个步骤。

  1. 从第 0 行开始，将第 1 个皇后放置在第 0 列。
  2. 现在将第二个皇后放在第 1 行和第 0 列。
  3. 检查位置是否安全
  4. 如果不安全，请在第 1 行第 1 列放置第二个皇后。
  5. 不安全，现在将第二个皇后放在第 1 行第 2 列。

通过在每个可能的列上放置女王并检查它是否安全，这样继续下去。您可以省略明显的错误条件，例如您不会将 2 个皇后放在同一行。下面是我的 8 皇后问题代码，打印所有可能的解决方案。

#include<stdio.h>


int abs(int a){
        return a>0? a : -a;
}

int isSafe(int col[],int row){
        int row2,col2,i,yDiff,xDiff;
                if(row == 0) return 1;


    for(row2=0;row2<row;row2++){
                    if(col[row2] == col[row])
                            return 0;

                    xDiff = col[row2] - col[row];
                    xDiff = abs(xDiff);
                    yDiff = row - row2;
                    if(xDiff == yDiff)
                                    return 0;
            }

    return 1;

}

int Nqueen(int col[],int n, int row){
        int i;
        if(row==n){
                printf("\n");
                for(i=0;i<n;i++)
                        printf("%d ",col[i]+1);

        }else{
                for(i=0;i<n;i++){
                    col[row] = i;
                    if(isSafe(col,row)){
                            queen(col,n,row+1);
                    }

            }
    }

}

int main(){
        int col[8];
        queen(col,8,0);

}
于 2012-08-24T07:12:14.373 回答
0

首先，您确实需要了解算法（这将告诉您将这些内容注释掉并不重要）。正如您所注意到的，此算法是递归的。这是回溯，因为你

  • 将第 k 个皇后设置为一个位置
  • 探索皇后 k+1,k+2,... 的可能位置
  • 然后你回到第k个皇后，把它放在别的地方，然后重复

看，在第 3 步中，我们“返回”到第 k 个皇后。这就是我如何解释为什么它被称为回溯。

于 2012-08-22T10:09:09.047 回答