0

我正在解决 N Queen 问题，我们需要在 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);

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

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

我也无法决定结束递归的基本条件。我如何在这里选择它？

4

2 回答 2

1 
#include <stdio.h>

#define SIZE 4
int size=SIZE;
int arr[SIZE][SIZE] = { 0 };

void placeQueen(int col){
    int r,c;
    if(col == size){//all queen put!
        //print out
        for(r = 0;r<size;++r){
            for(c = 0;c<size;++c)
                printf("%d", arr[c][r]);
            printf("\n");
        }
        printf("\n");
        return ;
    }
    for(r=0;r<size;++r){
        if(isAvailable(col, r)==1){
            arr[col][r]=1;
            placeQueen(col+1);
            arr[col][r]=0;//reset
        }
    }
}

int isAvailable(int col,int row){
    int c;

    for(c=0;c<col;++c){
        int d = col - c;
        if(arr[c][row]==1)
            return 0;//queen already same row
        if(row+d < size && arr[c][row+d]==1 || row-d >= 0 && arr[c][row-d]==1)
            return 0;//queen already same slanting position
    }
    return 1;
}

int main(){
    placeQueen(0);
    return 0;
}
于 2012-07-14T13:37:14.300 回答
1

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

此外，您的代码中存在一些明显的逻辑错误，例如

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

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

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

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

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

于 2012-07-14T09:45:15.190 回答