/*
* File: queen.c
* Description: 求 N 皇后問題回溯算法
* Created: 2001/11/12
* Author: Justin Hou [mailto:justin_hou@hotmail.com]
*/
#include <stdio.h>

#define  DelayTime  20000                /* 顯示棋局時間      */
#define  TopX      10                    /* 棋盤左上角 x 坐標  */
#define  TopY      5                    /* 棋盤左上角 y 坐標  */

int N;                                    /* 皇后數量          */

int a[8], b[15], c[15];
/*
* a[col-1] 記錄第 col 列有無皇后, 1 表示有。
* b[row+col-2] 記錄從左上數第 row+col-1 條斜率為 1 的線上有無皇后。
* c[row-col+7] 記錄從右上數第 row-col+8 條斜率為 -1 的線上有無皇后。
*/
int Num = 0;
int row;  
void BackTrack (int row)
{
    int col;                                        /* 局部變量 */
    for (col=1; col<=N; col++)
    {
        if (a[col-1] + b[row+col-2] + c[row-col+N-1] == 0)
        {
            a[col-1] = 1;                          /* 更改數據 */
            b[row+col-2] = 1;
            c[row-col+N-1] = 1;

            gotoxy(col*2 + TopX, row + TopY);      /* 畫皇后  */
            putch('Q');

            if (row < N)
            {
                BackTrack (row + 1);
            }
            else
            {
                Num++;                              /* 遞歸終點 */
                gotoxy(40, 9);
                printf("Num: %d ", Num);
                delay(DelayTime);
            }

            a[col-1] = 0;                          /* 清空數據 */
            b[row+col-2] = 0;
            c[row-col+N-1] = 0;

            gotoxy(col*2 + TopX, row + TopY);      /* 清除圖象 */
putch('.');

        }/* end if */
    }/* end for */
}/* end function BackTrack */

void main()
{
    int i, j;
    clrscr();

    gotoxy(1, 10);                            /* 要求用戶輸入皇后數量 */
    printf("Input the number of queen: ");
    while(N <= 0 || N > 14)
    {
        scanf("%d", &N);
        if(N > 14) printf("Two huge number, input again:");
        if(N <= 0) printf("Can's smaller than 1, again:");
}

clrscr();

    for(i=1; i<=N; i++)                        /*  畫棋盤(Chessboard) */
    {
        for(j=1; j<=N; j++)
        {
            gotoxy(i*2 + TopX, j + TopY);
            putch('.');
        }
    }

    BackTrack(1);                                    /* 開始回溯算法 */

    gotoxy(12, 17);                                  /* 顯示最后結果 */
    printf ("There are %d kinds of solution.\n", Num);

    getch();
}