c - 我的 n 皇后拼图代码有什么错误？

Question

#include <stdio.h>
#include <math.h>
char a[10][10];
int n;
int feasible(int row,int col)
{
    int i,j,tcol;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]=='Q')
                break;
        }
        tcol=j;
        if(col==tcol || abs(row-i)==abs(col-tcol))
            return 0;
    }
    return 1;
}
void nqueen(int row)
{
    int i,j;
    if(row<n)
    {
        for(i=0;i<n;i++)
        {
            if(feasible(row,i))
            {
                a[row][i]='Q';
                nqueen(row+1);
                a[row][i]='.';
            }
        }
    }
    else
    {
        printf("\nThe solution is:\n");
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                printf("%c\t",a[i][j]);
            }
            printf("\n\n");
        }
    }
}
            int main()
{
    int i,j;
    printf("Enter the number of queens:");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            a[i][j]='.';
        }
    }
    nqueen(0);
    getch();
    return 0;
}

可行的功能是检查所传递的行和列中是否可以放置皇后。

函数nqueen给出了该问题的所有可能的解决方案。 我在屏幕上没有看到任何输出。请帮忙!

Answer 1

当您检查棋盘的可行性时，您应该只检查已经放置皇后的行:

int feasible(int row, int col)
{
    int i, j, tcol;

    for (i = 0; i < row; i++) {
        for (j = 0; j < n; j++) {
            if (a[i][j] == 'Q') break;
        }
        tcol = j;

        if (col==tcol || abs(row - i) == abs(col - tcol))
            return 0;
    }
    return 1;
}

对于每一行i与 i < row ，有一个女王。所有其他行还没有皇后并且 tcol等号 n ，它脱离循环时的值。我猜对角线检查有时会意外地为真，从而缩短了完全有效的皇后位置。

您可以检查所有行的三个路径 - 直线向上、左对角线 ( l ) 和右对角线 ( r )，而不是在每行中查找皇后:

int feasible(int row, int col)
{
    int l = col;
    int r = col;

    while (row--) {
        l--; r++;

        if (a[row][col] == 'Q') return 0;
        if (l >= 0 && a[row][l] == 'Q') return 0;
        if (r < n  && a[row][r] == 'Q') return 0;
    }

    return 1;
}

表示棋盘的另一种方法是保留每个文件的皇后排名，这样您就不必搜索。不过，这将使打印电路板稍微复杂一些。