(简答题) 用回溯法求解四皇后的一个解

四皇后问题是指将4个皇后放在4×4的棋盘上，使任意两个皇后都不能在同一行、同一列或同一斜线上。我们可以使用回溯法来解决这个问题。

回溯法的基本思想是：从问题的某一种状态开始搜索，当发现当前状态不符合要求时，就返回上一个状态继续搜索，直到找到符合要求的状态或者所有状态都搜索完毕。

解题步骤如下：

1.定义一个数组board，表示棋盘，board[i]表示第i行皇后所在的列数。
2.从第1行开始，尝试在每一列放置皇后，判断是否符合要求。
3.如果符合要求，继续递归搜索下一行。如果搜索到第5行，说明找到了一个解，输出结果并返回。
4.如果不符合要求，回溯到上一行，继续在下一列尝试放置皇后。

完整的C语言代码如下：

#include <stdio.h>

#define N 4 //棋盘大小

int board[N+1] = {0}; //定义棋盘

void print_board() //输出结果
{
    int i,j;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=N;j++)
        {
            if(board[i] == j)
                printf("Q ");
            else
                printf(". ");
        }
        printf("\n");
    }
    printf("\n");
}

int check(int row, int col) //检查当前位置是否符合要求
{
    int i;
    for(i=1;i<row;i++)
    {
        if(board[i] == col //同一列
           || i+board[i] == row+col //同一右斜线
           || i-board[i] == row-col) //同一左斜线
            return 0;
    }
    return 1;
}

void queen(int row) //回溯搜索
{
    int i;
    if(row > N) //找到一种解
    {
        print_board();
        return;
    }
    for(i=1;i<=N;i++)
    {
        if(check(row, i)) //当前位置符合要求
        {
            board[row] = i; //放置皇后
            queen(row+1); //继续搜索下一行
            board[row] = 0; //回溯到上一行
        }
    }
}

int main()
{
    queen(1); //从第1行开始搜索
    return 0;
}

输出结果：

Q . . .
. . Q .
. Q . .
. . . Q