八皇后问题--回溯法非递归算法--两个回退一个前进

void queen(int n)
{
    //初始化N+1个元素是为了编程直观，第一元素不使用
    int *col =new int[n+1];        //col[m]=n 表示第m列，第n行放置皇后
    int *a   =new int[n+1];        //a[k] = 1 表示第k行上没有皇后
    int *b   =new int[2*n+1];    //b[k] = 1 表示第k条主对角线上没有皇后
    int *c   =new int[2*n+1];    //c[k] = 1 表示第k条次对角线上没有皇后
    int j;
    for(j=0;j<=n;j++)
        a[j] = 1;
    for(j=0;j<=2*n;j++)
        b[j] = c[j] =1;
    int m = 1;            //从第一列开始(0不用)
    col[1] = 1;            //初始第一列，第一行放上皇后
    int good = 1;            
    col[0] = 0;
    char awn;
    do{
        if(good)
        {
            if(m==n)        //已经找到一个解
            {
                printf("列\t\t行\n");
                for(j=1;j<=n;j++)
                    printf("%d\t\t%d\n",j,col[j]);
                printf("Enter a character(Q/q for exit)!\n");
                scanf("%c",&awn);
                if(awn == 'Q'||awn == 'q')
                    exit(0);
                while(col[m]==n)    //如果本列试探完毕，则回溯
                {
                    m--;        //回溯
                    //标记m列col[m]行处没有皇后(所在行，对角线，次对角线上都没有皇后)
                    a[col[m]] = b[m+col[m]]=c[n+m-col[m]]=1;
                }
                col[m]++;        //继续试探本列其他行
            }else{                //当前列的放置皇后满足要求，但还没找到解，继续
                a[col[m] ] = b[m+col[m]] = c[n+m-col[m]]=0; //标志当前位置已经放置皇后
                col[++m] = 1;        //转到下列第一行
            }
        }else{
            while(col[m]==n)    //第m列选择已经到了最后一行，所以回溯到上一列
            {
                m--;        //回溯到上一列
                a[col[m]] = b[m+col[m]]=c[n+m-col[m]]=1;//标记没有皇后
            }
            col[m]++;        //试探其他行
        }
        good = a[col[m]] && b[m+col[m]]&&c[n+m-col[m]];    //检查是否满足要求
    }while(m!=0);
}