CCF NOI1149 N皇后问题

问题链接：CCF NOI1149 N皇后问题。

---

时间限制: 1000 ms  空间限制: 262144 KB

题目描述 

  在N*N(N<=10)的棋盘上放N个皇后，使得她们不能相互攻击。两个皇后能相互攻击当且仅当它们在同一行，或者同一列，或者同一条对角线上。   找出一共有多少种放置方法。

输入

  第一行输入N。

输出

  输出方案总数。

样例输入

4 样例输出

2

数据范围限制

  N<=10

提示

 

---

问题分析

  该问题与《HDU2553 N皇后问题》几乎是同一问题，输入数据不同。

程序说明

  参见参考链接。

要点详解

回溯法是常用的算法。

---

参考链接：HDU2553 N皇后问题。

---

100分通过的C语言程序：

#include <stdio.h> #define TRUE 1 #define FALSE 0 #define MAXQUEEN 10 #define ABS(x) ((x>0)?(x):-(x)) /*求x的绝对值*/ /*存放8个皇后的列位置，数组下标为皇后的列位置*/ int queen[MAXQUEEN]; int total_solution; /*计算共有几组解*/ /* 测试在（row,col）上的皇后是否遭受攻击若遭受攻击则返回值为1，否则返回0 */ int attack(int row, int col) { int i, atk=FALSE; int offset_row, offset_col; i=0; while(!atk && i<row) { offset_row=ABS(i-row); offset_col=ABS(queen[i]-col); /* 判断两皇后是否在同一列，是否在同一对角线 */ /* 若两皇后在同列或同对角线，则产生攻击，atk==TRUE */ atk = (queen[i] == col) || (offset_row == offset_col); i++; } return atk; } /* 递归放置皇后子程序 */ void place(int q, int n) { int i=0; while(i < n) { if(!attack(q, i)) /* 皇后未受攻击 */ { queen[q]=i; /* 储存皇后所在的列位置 */ /* 判断是否找到一组解 */ if(q == n-1) total_solution++; /* 得到一个解 */ else place(q+1, n); /* 否则继续摆下一个皇后 */ } i++; } } int main(void) { int n; scanf("%d", &n); // 皇后遍历 total_solution = 0; place(0, n); /*从第0个皇后开始摆放至棋盘*/ printf("%d\n", total_solution); return 0; }