// 国际象棋“皇后”问题处理头文件

// 国际象棋“皇后”问题的回溯算法

/**/ /*

    作者：成晓旭

    时间：2001年10月9日(17:35:38-18:00:00)

    内容：完成“皇后”问题的程序序言部分

    时间：2001年10月9日(14:00:00-15:00:00)

    内容：完成“皇后”问题的程序序言部分

    ===================================================

    问题描述:

        在一个n*n的棋盘上放置n个不能互相捕捉的国际象棋“皇后”,

    并输出所有合理的布局情况.(在国际象棋中,皇后可以沿着纵、横

    及两条斜线共4个方向捕捉对手,可见,合适的解是在每行、每列及

    在一条斜线上只能有一个皇后 <皇后相互捕捉> )

    编程思想:

    算法描述:

    {

        输入棋盘大小值n;

        m=0;    //从空配置开始

        notcatch=1;        //空配置中皇后不能相互捕捉

        do

        {

            if(notcatch)

            {

                if(m==n)

                {

                    输出解;

                    调整(形成下一个候选解);

                }

                else

                    扩展当前候选解至下一列;    //向前试探

            }

            else

                调整(形成下一个候选解);        //向后回溯

            notcatch = 检查当前候选解的合理性

        }while(m!=0)

    }

*/

#include  " stdlib.h "

#define   MAXN 100

// 全局变量及全局工作数组定义

int  m,n,NotCatch;

int     ColFlag[MAXN + 1 ];     /**/ /*表示第i列的第ColFlag[i]行有皇后,(1:有;0:没有)*/

int  RowFlag[MAXN + 1 ];     /**/ /*RowFlag[i]:表示第i行没有皇后(1:没有;0:有)*/

int  upBiasFlag[ 2 * MAXN + 1 ];     /**/ /*upBiasFlag[i]:表示第i条上斜线(右高左斜)没有皇后(1:没有;0:有)*/

int  dnBiasFlag[ 2 * MAXN + 1 ];     /**/ /*dnBiasFlag[i]:表示第i条下斜线(左高右斜)没有皇后(1:没有;0:有)*/

// 显示输入填写的数字

void  ArrangeQueen()

... {

    int i;

    char answer;

    printf("输入棋盘边格数：");

    scanf("%d",&n);

    for(i=0;i<=n;i++)    /**//*设置程序初始状态*/

        ColFlag[i] = 1;

    for(i=0;i<=2*n;i++)

        upBiasFlag[i] = dnBiasFlag[i] = 1;

    m = 1;

    ColFlag[1] = 1;

    NotCatch = 1;

    ColFlag[0] = 0;

    do

    ...{

        if(NotCatch)

        ...{

            if(m==n)

            ...{

                printf("列 行");

                for(i=1;i<=n;i++)    /**//*找到可行解,输出*/

                    printf("%3d %3d ",i,ColFlag[i]);

                printf("还要继续搜索吗(Q/q for Exit)？ ");

                scanf("%c",&answer);

                if(answer=='Q' || answer=='q')

                    exit(0);

                while(ColFlag[m] == n)

                ...{

                    m--;    /**//*清除第m-1列,第RowFlag[ColFlag[m-1]]行有皇后的标志*/

                    RowFlag[ColFlag[m]] = upBiasFlag[m+ColFlag[m]] = dnBiasFlag[n+m-ColFlag[m]] = 1;

                }

                ColFlag[m]++;    /**//*调整第m列的皇后配置(扩展调整)*/

            }

            else

            ...{

                /**//*设置第m列,第RowFlag[ColFlag[m-1]]行有皇后的标志*/

                RowFlag[ColFlag[m]] = upBiasFlag[m+ColFlag[m]] = dnBiasFlag[n+m-ColFlag[m]] = 0;

                ColFlag[++m] = 1;    /**//*向前试探*/

            }

        }

        else

        ...{    

            while(ColFlag[m]==n)    /**//*向后回溯*/

            ...{

                m--;    /**//*清除第m-1列,第RowFlag[ColFlag[m-1]]行有皇后的标志*/

                RowFlag[ColFlag[m]] = upBiasFlag[m+ColFlag[m]] = dnBiasFlag[n+m-ColFlag[m]] = 1;

            }

            ColFlag[m]++;    /**//*调整第m列的皇后配置(回溯调整)*/

        }

        NotCatch = RowFlag[ColFlag[m]] && upBiasFlag[m+ColFlag[m]] && dnBiasFlag[n+m-ColFlag[m]];

    }while(m!=0);

}

void  dArrange_Queen_All( int  k, int  n)

... {

    int i,j;

    char answer;

    for(i=1;i<=n;i++)

    ...{

        if(RowFlag[i] && upBiasFlag[k+i] && dnBiasFlag[n+k-i])

        ...{

            ColFlag[k] = i;

            RowFlag[i] = upBiasFlag[k+i] = dnBiasFlag[n+k-i] = 0;

            if(k==0)

            ...{

                printf("列 行");

                for(j=1;j<=n;j++)    /**//*找到可行解,输出*/

                    printf("%3d %3d ",i,ColFlag[i]);

                printf("还要继续搜索吗(Q/q for Exit)？ ");

                scanf("%c",&answer);

                if(answer=='Q' || answer=='q')

                    exit(0);

            }

            else

                dArrange_Queen_All(k+1,n);

            RowFlag[i] = upBiasFlag[k+i] = dnBiasFlag[n+k-i] = 1;

        }

    }

}

void  dArrangeQueenAll()

... {

    int i;

    printf("输入棋盘边格数：");

    scanf("%d",&n);

    for(i=0;i<=n;i++)    /**//*设置程序初始状态*/

        ColFlag[i] = 1;

    for(i=0;i<=2*n;i++)

        upBiasFlag[i] = dnBiasFlag[i] = 1;

    dArrange_Queen_All(1,n);

}