チェスの「皇后」問題の遡及アルゴリズム

//    “  ”       
//    “  ”       
/*
      ：   
      ：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);
}