题目描述
一个如下的 6*6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n，表示棋盘是 n×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入输出样例
输入 #1
6
输出 #1复制
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
说明/提示
【数据范围】
对于 100% 的数据，6≤n≤13。
题目翻译来自NOCOW。
USACO Training Section 1.5
思路主要还是用到了搜索与回溯 其他就没啥了 主要要理解定义的几个数组的含义
代码如下
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int a[100];//存储行
int b[100];//存储列
int c[100];//存储左对角线
int d[100];// 存储右对角线
void print(int *a){if(cnt<3){for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;}
}
void dfs(int depth){if(depth>n){print(a);cnt++;return ;}else{for(int i=1;i<=n;i++){if(!b[i]&&!c[depth+i]&&!d[depth-i+n]){b[i]=1;a[depth]=i;c[depth+i]=1;d[depth-i+n]=1; //这两个c d数组看不懂的话就画图进行理解，随便在棋盘找几对对角线 分别做对角线和右对角线 会发现在一个n*n的棋盘中 从左下往右上的对角线刚好能满足一个点的i+j等于另一个点的i+j（i，j为坐标） 从右下往左上的对角线则满足一个点的i-j+n(n为棋盘规模)与另一个点的i-j+n相等。。dfs(depth+1);c[depth+i]=0;//回溯d[depth-i+n]=0;b[i]=0;}}}
}
int main(){cin>>n;dfs(1);cout<<cnt<<endl;return 0;
}