n皇后.c

在n×n的棋盘上放置n个皇后

#include <stdio.h>
#include <stdlib.h>
int nqueens(int *a, int k, int n)
{
    int  i , j, conflict;
    if (k==n) return 1;

    for (i=0;i<n; i++)
    {
        conflict =0;
        for (j=0;j<k;j++)
        {
            if (i==a[j]||k-j==i-a[j]||k-j==a[j]-i)
                conflict = 1;
        }
        if (conflict==0)
        {
            a[k]=i;
            if (nqueens(a, k + 1, n)==1) return 1;
        }
    }
    return 0;
}
void output(int* a, int n)
{
    int i, j;
    printf("\nPlace Queens in the following positions:\n");
    for (i = 0; i < n; i++)
    {
        printf("row%3d-col%3d:|",i,a[i]);
        for (j = 0; j < a[i];j++) printf(" |");
        printf("Q|");
        for (j = a[i]+1; j < n; j++) printf(" |");
        putchar('\n');
    }
}
int main()
{
    int n,*a;
    printf("Please enter an integer as the size of the promblem: N=");
    scanf("%d", &n);
    if (n>0) a= (int *)malloc(n*sizeof(int));
    else
    {
        printf("Error ! Invalid input!\n");
        return 0;
    }
    if (nqueens(a,0,n)==1) output(a,n);
    else
        printf("Sorry!There is no solution for %d Queens problem!\n",n);
    free(a);
    return 0;
}