题目如下： checker Challenge 跳棋的挑战 检查一个如下的6 x 6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5 来描述,第i个数字表示在第i行的相应位置有一个棋子,如下: 行号 1 2 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解.请编写一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。 解按字典顺序排列。请输出前3个解。最后一行是解的总个数。 INPUT FORMAT 一个数字N (6 <= N <= 13) 表示棋盘是N x N 大小的。 SAMPLE INPUT(checker.in) 6 OUTPUT FORMAT 前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。 SAMPLE OUTPUT(checker.out) 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4 解题思路： 这一题实际上就是一个N皇后问题，用DFS就可以过，每对角线可以表示为： b[行+列]和b1[列-行+N-1] ，列为：b2[列] 所以代码如下：
#include<cstdio> #include<cstdlib> int n,ans=0; int bj1[50],b[100],a[50],bj[100]; void get(int &x) { char c = getchar(); x = 0; while(c < '0' || c > '9') c = getchar(); while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar(); } void put(int x) { int num = 0; char c[15]; while(x) c[++num] = (x%10)+48, x /= 10; while(num) putchar(c[num--]); putchar('\n'); } void dfs(int k) { if(k==n+1) { if(ans<3) {//输出前三个 for(register int i=1; i<k; i++) put(a[i]); printf("\n"); } ans++;//总是+1 return ;//返回 } for(register int i=1; i<=n; i++) { if(bj1[i]==0&&b[i+k]==0&&bj[i-k+n-1]==0) {//保证使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子 bj1[i]=1; b[i+k]=1; bj[i-k+n-1]=1; a[k]=i; dfs(k+1); bj1[i]=0; b[i+k]=0; bj[i-k+n-1]=0; } } } int main() { freopen("checker.in","r",stdin); freopen("checker.out","w",stdout); get(n); dfs(1);//从第一行开始搜索 put(ans); return 0; }