首页 文章

函数调用在n-queen问题中自动发生

提问于
浏览
-4

我发现这段代码可以找到n-queen问题的所有可能解决方案:

#include<stdio.h>
#include<math.h>

int board[20], count;

int main()
{
    int n, i, j;
    void queen(int row, int n);

    printf(" - N Queens Problem Using Backtracking -");
    printf("\n\nEnter number of Queens:");
    scanf("%d", &n);
    queen(1, n);
    return 0;
}

//function for printing the solution
void print(int n)
{
    int i, j;
    printf("\n\nSolution %d:\n\n", ++count);

    for (i = 1; i <= n; ++i)
        printf("\t%d", i);

    for (i = 1; i <= n; ++i)
    {
        printf("\n\n%d", i);
        for (j = 1; j <= n; ++j) //for nxn board
        {
            if (board[i] == j)
                printf("\tQ"); //queen at i,j position
            else
                printf("\t-"); //empty slot
        }
    }


}

/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row, int column)
{
    int i;
    for (i = 1; i <= row - 1; ++i)
    {
        //checking column and digonal conflicts
        if (board[i] == column)
            return 0;
        else
            if (abs(board[i] - column) == abs(i - row))
                return 0;
    }

    return 1; //no conflicts
}

//function to check for proper positioning of queen
void queen(int row, int n)
{
    int column;
    for (column = 1; column <= n; ++column)
    {
        if (place(row, column))
        {
            board[row] = column; //no conflicts so place queen
            if (row == n) //dead end
                print(n); //printing the board configuration
            else //try queen with next position
                queen(row + 1, n);
        }
    }
}

我的困惑是main()函数只调用函数queen()一次,但是当queen()函数的for循环结束时,queen()函数再次启动 . 我通过调试看到它,当for循环中的value列达到最大值时for循环结束,执行转到queen()函数的最后一行,然后再次进入for循环的开始 . 当for循环结束时,不会发生递归 . 这怎么可能?

1 回答

  • 0

    这是因为递归 . 你正在调用queen(第1行,第n行),这会将控件带到函数的开头 .

相关问题