N皇后问题

头一次认真的去写一个程序，代码中有什么不足之处，请指出，谢谢！

问题描述：

    设在初始状态下在国际象棋上没有任何棋子。然后顺序在第1行，第2行，…，第n行上布放棋子。在每一行中有n个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件：即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个算法（递归或者非递归均可），求解并输出此问题的所有合法布局。

 

/*
 * =====================================================================================
 *
 * Filename: nqueen.c
 *
 * Description: N皇后问题（人工智能实验一）
 *
 * Version: 1.0
 * Created: 2008-10-23 12:41:34
 * Revision: none
 * Compiler: gcc
 *
 * Author: MneeHNXM (Mnee), [e-mail]
 * Company: HeNan University
 *
 * =====================================================================================
 */

#include    <stdio.h>
#include    <math.h>
#include    <malloc.h>
#include    <errno.h>

int count=0; //N皇后问题的解决方案数

int * pos; //棋盘


void show (int);
int place (int);
/*
 * === FUNCTION ======================================================================
 * Name: nqueen
 * Description: N皇后函数/递归函数，参考数据结构（C语言版）P151
 * =====================================================================================
 */
    void
nqueen (int i,int n) //进入本函数时，在n*n棋盘前i-1行已放置了互不攻击的i-1个棋子。

{
    //现从第i行起继续为后续棋子选择合适位置。

    //当i>n时，求得一个合法布局，输出之。

    int j=1;

    if ( i>n )
    {
        show(n);
    }
    else
        for (j = 1; j <= n; j++)
         {
            pos[i-1] = j;     //在第i行第j列放置一个棋子


            
            if ( place(i) )         //如果当前布局合法

            {
                nqueen(i+1,n);
            }

            pos[i-1] = -1; //移走第i行第j列的棋子

        }

    return;
}        /* ----- end of function nqueen ----- */


/*
 * === FUNCTION ======================================================================
 * Name: place
 * Description: 判断当前布局是合法
 * =====================================================================================
 */
    int
place (int i )
{
    int j=0;
    for(j=0;j<i-1;j++)
    {
        if( ( pos[i-1]==pos[j] ) ||
                ( abs(pos[i-1]-pos[j]) == abs(j+1-i) ) //此行等价于p[i-1]-i==p[j]-(j+1) || p[i-1]+i==p[j]+(j+1)

             )
            return 0;
    }
    return 1;
}        /* ----- end of function place ----- */
/*
 * === FUNCTION ======================================================================
 * Name: show
 * Description: 打印棋盘
 * =====================================================================================
 */
    void
show (int n)
{
    printf("\n");

    int i =0;
    int j =0;

    for (i=0;i < n; i++)
     {
        
        for (j=1;j <= n; j++)
         {
            if ( pos[i] == j )
             {
                printf("Q ");
            }
            else
            {
                printf("* ");
            }
        }
        printf("\n");
    }

    count++; //方案数加一；

    return ;
}        /* ----- end of function show ----- */



    int
main ( int argc, char *argv[] )
{
    int n=0;
    printf("Please input the number of the queens:");
    scanf("%d",&n);

    pos    = (int*)malloc (n*sizeof(int));
    if ( pos==NULL ) {
        fprintf ( stderr, "\ndynamic memory allocation failed\n" );
        exit (EXIT_FAILURE);
    }

    int i;
    for(i=0;i<n;i++)
    {
        pos[i] = -1;
    }
    
    nqueen(1,n);
    printf("Total:%d\n",count);

    free (pos);
    return EXIT_SUCCESS;
}                /* ---------- end of function main ---------- */


在GCC3.4.5下编译通过。