CCF NOI1149 N皇后问题

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

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

题目描述

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

输入

第一行输入N。

输出

输出方案总数。

样例输入

4
样例输出

数据范围限制

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
", total_solution);

    return 0;
}