问题 I: n皇后问题

题目描述

在n×n 格的棋盘上放置彼此不受攻击的n 个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2 个皇后不放在同一行或同一列或同一斜线上。 设计一个解n 后问题的队列式分支限界法，计算在n× n个方格上放置彼此不受攻击的n个皇后的一个放置方案。

输入

输入数据只占一行，有1 个正整数n，4≤n≤20。

输出

将计算出的彼此不受攻击的n个皇后的一个放置方案输出。第1行是n个皇后的放置方案。

样例输入

5

样例输出

1 3 5 2 4

提示

代码：

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <malloc.h> void nQueens(int *x, int n); int place(int *x, int k); void printSolution(int *x, int n); int main() { int n; int *x; scanf("%d",&n); x=(int*)malloc(sizeof(int)*(n+1)); nQueens(x,n); return 0; } int place(int *x, int k) { int i; for(i=1;i<k;i++) { if ((x[i]==x[k])||(fabs(x[i]-x[k])==fabs(i-k))) return 0; } return 1; } void nQueens(int *x, int n) { int k; k=1; x[k]=0; while(k>0) { x[k]++; while(x[k]<=n&&!place(x,k)) x[k]++; if(x[k]<=n) { if(k==n) printSolution(x,n); else { k++; x[k]=0; } } else k--; } } void printSolution(int *x, int n) { int i=1,j; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(j==x[i]) printf("%d ",j); } } printf("\n"); }