八皇后(DFS)

八皇后

时间限制: 1 Sec  内存限制: 256 MB

题目描述

一个如下的6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列2 4 6 1 3 5 来描述，第 ii 个数字表示在第 i 行的相应位置有一个棋子，如下：

行号1 2 3 4 5 6

列号2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

输入格式

一行一个正整数 nn，表示棋盘是 n×n 大小的。

输入格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例

输入

6
输出

2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

4

题意：

       一道经典的DFS，题意不解释了题目说的很明白了。（逃

       这道题在《一本通》里有解析和代码，这里换一种思路。

       仔细观察这张图的行号和列号找规律。

       你发现了什么？

       找规律是个好办法

       我们采用标记的办法记录这个点可不可以存放棋子。

       判断行、列是否重复很简单就不赘述了。

       对角线的判断，我们可以对每一条假想的斜线编一个号，如按左下——右上方向编组，（1,1）属于一组，（1,2），（2,1）属于一组，（3,1），（2,2），（1,3）属于另一组......

       很容易发现我们新编的组中，每一对数中的行号和列号相加的值总为一个定值，所以我们用一个数组f2来记录我们定义的新组。

       同样的按左上——右下编组，（1,6）属于一组，（1,5），（2,6）属于一组，（1,4），（2,5），（3,6）属于另一组......

       在这个新编的组中，每一对数的行号和列号的差总为一定值（超简单对不对），所以我们用数组f3来标记这个新数组。

代码如下：

 1 #include<iostream>
 2 #include<stdio.h>
 3 using namespace std;
 4 int n,ans,pos[15],f1[25],f2[25],f3[25],f4[25];
 5 void print()
 6 {
 7     ans++;
 8     if(ans>3)  return;//只输出前三个答案 
 9     printf("%d",pos[1]);
10     for(int i=2;i<=n;i++)  printf(" %d",pos[i]);//打印 
11     printf("\n");
12 return;
13 }
14 void dfs(int x)
15 {
16     //x代表目前正在将第x颗棋子放置在第x行， 
17     if(x==n+1)  { print(); return; }
18     for(int i=1;i<=n;i++)//尝试第x行第i列 
19         if(!f1[i] && !f2[i+x] && !f3[i-x+n])
20         {
21             f1[i]=f2[i+x]=f3[i-x+n]=1,pos[x]=i;
22             //pos记录答案，f3数组中为防止下标为负数需要+n 
23             dfs(x+1);
24             //回溯 
25             f1[i]=f2[i+x]=f3[i-x+n]=0;
26         }
27 }
28 int main()
29 {
30     scanf("%d",&n);
31     dfs(1);//从第1枚棋子开始放置 
32     printf("%d\n",ans);
33 return 0;
34 }

八皇后(DFS)

原文：https://www.cnblogs.com/leaf-2234/p/13862651.html