运用递归来解N皇后问题

/*递归　实验  运用递归来解N皇后问题。          　*/

/*===============================================*/
/*程序构思：                                     */
/*必须先判断传入的坐标位置是否可放置皇后。       */
/*（判断譔坐标上、下、左、右、左上、右上、左下、右下八个方向是否有其它的皇后，*/
/*有返回false，无返回true。                      */
/*假设传入的坐标为(LocX, LocY)，棋盘大小为N*N。  */
/*坐标上方：(LocX, LocY-1)到(LocX, 0)是否有其它的皇后。*/
/*坐标下方：(LocX, LocY+1)到(LocX, N-1)是否有其它的皇后。*/
/*坐标左方：(LocX-1, LocY)到(0, LocY)是否有其它的皇后。*/
/*坐标右方：(LocX+1, LocY)到(N-1, LocY)是否有其它的皇后。*/
/*坐标左上方：(LocX-1, LocY-1)到(LocX, 0)或(0, LocY)是否有其它的皇后。*/
/*坐标右上方：(LocX+1, LocY-1)到(LocX, 0)或(N-1, LocY)是否有其它的皇后。*/
/*坐标左下方：(LocX-1, LocY+1)到(LocX, N-1)或(0, LocY)是否有其它的皇后。*/
/*坐标右下方：(LocX+1, LocY+1)到(LocX, N-1)或(N-1, LocY)是否有其它的皇后。*/
/*递归结束条件：当N个皇后皆放置成功。            */
/*递归执行部分：判断传入坐标是否可放置皇后，可以放置则依序递归放置下一个皇后。*/

/*===============================================*/
/*程序源代码                                     */
/*==============Program Description==============*/
/*程序名称: recursive02.c                        */
/*程序目的: 运用递归来解N皇后问题                */
/*程序提供: 马春江                               */
/*===============================================*/
char Chessboard[8][8];        /*声明8*8的空白棋盘*/

/*===============================================*/
/*递归解N皇后问题                                */
/*===============================================*/
int N_Queens(int LocX, int LocY, int Queens)
{
    int i, j;                 /*循环计数变量     */
    int Result=0;

    if (Queens==8)            /*递归结束条件     */
        return 1;
    else
        if (QueensPlace(LocX, LocY))
        {
            Chessboard[LocX][LocY]='Q';
            for (i=0; i<8; i++)
                for (j=0; j<8; j++)
                {
                    Result+=N_Queens(i, j, Queens+1);
                    if (Result>0)
                        break;
                }
            if (Result>0)
                return 1;
            else
            {
                ChessboardpLocX][LocY]='X';
                Return 0;
            }
        }
        else
            return 0;
}

/*===============================================*/
/*判断传入坐标是否可放置皇后                     */
/*===============================================*/
int Queen Place (int LocX, int LocY)
{
    int i, j;

    if (Chessboard[LocX][LocY]!='X')       /*判断是否有皇后          */
        return 0;

    for (j=LocY-1; j>=0; j--)              /*判断上方是否有皇后      */
        if (Chessboard[LocX][j]!='X')
            return 0;

    for (j=LocY+1; j<8; j++)               /*判断下方是否有皇后      */
        if (Chessboard[LocX][j]!='X')
            return 0;

    for (i=LocX-1; i>=0; i--)              /*判断左方是否有皇后      */
        if (Chessboard[i][LocY]!='X')
            return 0;

    for (i=LocX+1; i<8; i++)               /*判断右方是否有皇后      */
        if (Chessboard[i][LocY]!='X')
            return 0;

    i=LocX-1;
    j=LocY-1;
    while (i>=0 && j>=0)                   /*判断左上方是否有皇后    */
        if (Chessboard[i--][j--]!='X')
            return 0;

    i=LocX+1;
    j=LocY-1;
    while (i<8 && j>=0)                    /*判断右上方是否有皇后    */
        if (Chessboard[i++][j--]!='X')
            return 0;

    i=LocX-1;
    j=LocY+1;
    while (i>=0 && j<8)                    /*判断左下方是否有皇后    */
        if (Chessboard[i--][j++]!='X')
            return 0;

    i=LocX+1;
    j=LocY+1;
    while (i<8 && j<8)                     /*判断右下方是否有皇后    */
        if (Chessboard[i++][j++]!='X')
            return 0;
    return 1;
}

/*===============================================*/
/*主程序                                         */
/*===============================================*/
void main()
{
    int i, j;                              /*循环计数变量           */
    
    for (i=0; i<8; i++)
        for (j=0; j<8; j++)
            Chessboard[i][j]='X';
    N_Queens (0, 0, 0);

    printf ("The graph of 8 Queens on the Chessboard. \n");
    printf ("     0   1   2   3   4   5   6   7  \n");
    printf ("   +---+---+---+---+---+---+---+---+\n");

    for (i=0; i<8; i++)
    {
        printf (" %d |", i);
        for (j=0; j<8; j++)
            printf ("-%c-|, Chessboard[i][j]);
        printf ("\n   +---+---+---+---+---+---+---+---+\n");
    }
}

/*希望的结果                                            */
/*The graph of 8 Queens on the Chessboard.              */
/*    0   1   2   3   4   5   6   7                     */
/*  +---+---+---+---+---+---+---+---+                   */
/*0 |-Q-|-X-|-X-|-X-|-X-|-X-|-X-|-X-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*1 |-X-|-X-|-X-|-X-|-Q-|-X-|-X-|-X-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*2 |-X-|-X-|-X-|-X-|-X-|-X-|-X-|-Q-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*3 |-X-|-X-|-X-|-X-|-X-|-Q-|-X-|-X-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*4 |-X-|-X-|-Q-|-X-|-X-|-X-|-X-|-X-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*5 |-X-|-X-|-X-|-X-|-X-|-X-|-Q-|-X-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*6 |-X-|-Q-|-X-|-X-|-X-|-X-|-X-|-X-|                   */
/*  +---+---+---+---+---+---+---+---+                   */
/*7 |-X-|-X-|-X-|-Q-|-X-|-X-|-X-|-X-|                   */