ytu 1789:n皇后问题（水题，枚举）

n皇后问题

Time Limit: 1 Sec Memory Limit: 64 MB Special Judge
Submit: 12 Solved: 3
[Submit][Status][Web Board]

Description

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

Input

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

Output

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

Sample Input

Sample Output

1 3 5 2 4

HINT

N皇后问题
解决这道问题有两种不同形式的做法：递归和迭代。

递归和迭代有什么区别呢？
现在引用百度知道的一个回答：

简单来说，递归就是自己调用自己,如：

int abc(...)

{

if(...) //递归终止条件

{ return abc(...); }

return ;

}

而迭代是重复一组指令，不断地根据变量的旧值推出新值，如：

for(; ; ;) //迭代终止条件

{

a = b + c;

b = a;

c = a;

}

我想有一部分人也是分不清的吧，包括我自己也是，现在重温一下这两者的区别。
===================================
好了，刚才只是题外话，现在我们回归正题。
不管是递归还是迭代，实际上思路都是一样的。

解题思路：
　　题目要求任意一横排、一竖列、一斜线上不能有两个皇后，那么我们以行i做一个循环

，每循环一次就确定第i个皇后在第几列。很显然第i个皇后的位置不能和之前（i-1）个皇后的位置重复

，也就是a[i]!=a[1]/a[2]/.../a[i-1]，那么写一个递归函数f(i)，确定第i个皇后的位置。

下面是我用递归做的代码：

 #include <iostream>

 using namespace std;

 int n;

 int a[];

 bool f(int h)

 {

     if(h>n)

         return true;

     if(h==){　　　　//第一个皇后的位置不需要对比

         for(int i=;i<=n;i++){

             a[h]=i;                  if(f(h+))

                 return true;

         }

     }

     else {　　//从第二个皇后开始位置需要与前面的皇后对比了

         for(int i=;i<=n;i++){　　//按行循环

             int j;

             for(j=;j<h;j++)　　//判断是否一竖列有两个皇后

                 if(a[j]==i)

                     break;

             if(j<h)

                 continue;

             for(j=;j<h;j++){　　//判断是否一斜线上有两个皇后。因为是按行循环，所以不需要判断是否一横行上有两个皇后。

                 int t=h-j;

                 if(a[j]+t==i || a[j]-t==i)

                     break;

             }

             if(j<h)

                 continue;

             a[h]=i;

             if(f(h+))　　//判断下一个皇后的位置。

                 return true;

         }

     }

     return false;　　//条件都不符合，则说明这种摆法不合适，回溯，换一种摆法。

 }

 int main()

 {

     cin>>n;

     f();

     for(int i=;i<=n;i++)

         cout<<a[i]<<' ';

     return ;

 }

Freecode : www.cnblogs.com/yym2013

秒客网