时间戳

首页 > 解决方案 > 超过 9 皇后问题的分段错误

c - 超过 9 皇后问题的分段错误

问题描述

我正在阅读“c 上的指针”并发现非常有趣的 8-queen 问题。我为它编写了代码，它工作得很好，得到了正确的答案，92 个解决方案。

然后我想尝试或多或少的皇后。我发现一个非常奇怪的问题。对于 8 个或少于 8 个皇后，代码运行得非常完美。对于超过 8 个皇后，比如 9,10...，会出现分段错误。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define SIZE 9

int conflict(int (*chess)[SIZE],int row,int col);
int next_queen(int (*chess)[SIZE],int row,int col);
int clear_previous_col(int (*chess)[SIZE],int col);
void print_chess_board(int (*chess)[SIZE]);

int total_solutions=0;
int total_print_count=0;
int chess[SIZE][SIZE];

int main(void)
{

    int row,col;

    /* initialize the chess board */
    for(row=0;row<SIZE;row++)
    {
        for(col=0;col<SIZE;col++)
        {
            chess[row][col]=0;
        }
    }

    /* start chess */
    next_queen(chess,0,0);
    printf("Totally %d solutions\n",total_solutions);

    return 0;
}

int next_queen(int (*chess)[SIZE],int row,int col)
{
    if(conflict(chess,row,col))
    {
        /* if conflicts, place queen in next row, make sure next row is not out of bound */
        if(row<SIZE-1)
        {
            next_queen(chess,row+1,col);
        }
        else
        {
             if(col<1)
             {
                 return -1;
             }
             else
             {
                 col=col-1;
                 int previous_queen_row;
                 while(col>=0 && (previous_queen_row=clear_previous_col(chess,col))==SIZE-1)
                 {
                     col=col-1;
                 }
                 if(col==-1)
                 {
                     return -1;
                 }
                 else
                 {
                     next_queen(chess,previous_queen_row+1,col);
                 }
             }
        }
    }
    else
    {
        chess[row][col]=1;
        if(col<SIZE-1)
        {
            next_queen(chess,0,col+1);
        }
        else
        {
        total_solutions++;
        print_chess_board(chess);
        chess[row][col]=0;
        col=col-1;
        int previous_queen_row;
        while(col>=0 && (previous_queen_row=clear_previous_col(chess,col))==SIZE-1)
        {
            col=col-1;
        }
        if(col==-1)
        {
            return -1;
        }
        else
        {
            next_queen(chess,previous_queen_row+1,col);
        }
        }
    }
    return 1;
}

void print_chess_board(int (*chess)[SIZE])
{
    int i,j;
    total_print_count++;
    if(total_print_count==152)
    {
        printf("stop here!\n");
    }
    printf("print number: %d\n",total_print_count);
    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
        {
            printf("%d ",chess[i][j]);
        }
        printf("\n");
    }
    printf("\n\n");
}

int clear_previous_col(int (*chess)[SIZE],int col)
{
    int i;
    for(i=0;i<SIZE;i++)
    {
        if(chess[i][col]==1)
        {
            chess[i][col]=0;
            return i;
        }
    }
    printf("return -1 col = %d\n",col);
    return -1;
}

int conflict(int (*chess)[SIZE],int row,int col)
{
    int i;
    int j;

    if(row>SIZE-1 || col>SIZE-1)
    {
        return TRUE;
    }

    if(row<0 || col<0)
    {
        return TRUE;
    }

    /* same row conflic */
    for(i=0;i<SIZE;i++)
    {
        if(chess[row][i]==1)
        {
            return TRUE;
        }
    }
    /* same column conflict */
    for(i=0;i<SIZE;i++)
    {
        if(chess[i][col]==1)
        {
            return TRUE;
        }
    }
    /* diagonally confilic */
    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
        {
            if(abs(i-row)>0 && abs(i-row)==abs(j-col) && chess[i][j]==1)
            {
                return TRUE;
            }
        }
    }
    return FALSE;
}

非常感谢您的帮助。

谢谢。

标签： csegmentation-faultn-queens

解决方案

valgrind我在64 位 Ubuntu 19.10 系统上运行该程序。

我没有收到错误#define SIZE 9。

用#define SIZE 10它报告堆栈溢出。

接下来我以valgrind --num-callers=500最大值运行它并获得这样的堆栈跟踪

==31854== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==31854==    at 0x109531: conflict (queen.c:138)
==31854==    by 0x10924C: next_queen (queen.c:39)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x1092D7: next_queen (queen.c:66)
==31854==    by 0x1092D7: next_queen (queen.c:66)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x1092D7: next_queen (queen.c:66)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
==31854==    by 0x109271: next_queen (queen.c:44)
...

有 499 个条目next_queen。

在某些情况下，您可能会有无限递归，但我猜嵌套级别会随着电路板尺寸的增大而变得太深。

显然，可以使用您的算法计算的板大小限制取决于不同系统或编译器之间不同的可用堆栈大小。

推荐阅读