TZOJ 4435 n皇后问题(回溯)

描述

在 n×n 的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后（任两个皇后都不能处于同一条横行、纵行或斜线上）

输入

输入有多组（直到-1结束）

每组一行一个整数 n（0<n<11)代表皇后的个数。

输出

每组测试数据间输出一个换行。

对于每组数据，如果存在一个棋谱（使得n个皇后不会相互攻击），先输出这是第几种棋谱，然后输出该棋谱。当全部棋谱都输完时，最后输出该组总共摆放的棋谱数。

样例输入

1
2
4
-1

样例输出

case1:
1
There are 1 kinds of

There are 0 kinds of

case1:
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
case2:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
There are 2 kinds of

提示

存放皇后时，按列优先的顺序从上往下从左至右的顺序遍历。

题意

在 n×n 的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后（任两个皇后都不能处于同一条横行、纵行或斜线上），输出所有可能的棋盘，最后输出总数

题解

回溯，往前试探一步，判断是否可行，再试探

代码

 #include<stdio.h>

 #include<string.h>

 int n,k;

 int pos[];//pos[i]=j表示第i行的皇后在第j列

 int abs(int x){return x>?x:-x;}

 bool st(int now)

 {

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

         if(pos[i]==pos[now]||abs(pos[i]-pos[now])==abs(i-now))//和前几个在同一列，在同一斜

             return false;

     return true;

 }

 void print()

 {

     printf("case%d:\n",++k);//k代表个数

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

     {

         if(pos[i]==)

             printf("");

         else

             printf("");

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

         {

             if(pos[i]==j)

                 printf("");

             else

                 printf("");

         }

         puts("");

     }

 }

 void trail(int now)//递归回溯，now表示第几个试探

 {

     if(n==now)//填满n个结束

     {

         print();

         return;

     }

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

     {

         pos[now]=j;//先填上，试探

         if(st(now))//可行就先选这个数

             trail(now+);//试探下一个

     }

 }

 int main(){

     int o=;

     while(scanf("%d",&n)!=EOF,n!=-)

     {

         if(o++)puts("");

         memset(pos,,sizeof(pos));

         k=;

         trail();

         printf("There are %d kinds of\n",k);

     }

     return ;

 }

巴特西

TZOJ 4435 n皇后问题(回溯)

最新文章

热门文章