2025.9.16
题目内容
一个如下的 \(6 \times 6\) 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子
上面的布局可以用序列 \(2\ 4\ 6\ 1\ 3\ 5\) 来描述，第 \(i\) 个数字表示在第 \(i\) 行的相应位置有一个棋子，如下：
行号 \(1\ 2\ 3\ 4\ 5\ 6\)
列号 \(2\ 4\ 6\ 1\ 3\ 5\)
这只是棋子放置的一个解，请编一个程序找出所有棋子放置的解，并把它们以上面的序列方法输出，解按字典顺序排列，请输出前 \(3\) 个解，最后一行是解的总个数
输入描述
一行一个正整数 \(n\)，表示棋盘是 \(n \times n\) 大小的
输出描述
前三行为前三个解，每个解的两个数字之间用一个空格隔开，第四行只有一个数字，表示解的总数
输入输出样例
输入
6
输出
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明/提示
对于 \(100\%\) 的数据，\(6 \le n \le 13\)
C++实现
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int a[50][50],yi[20],xjay[50],xjiany[50];
int n,c=0,s=0;
void out() {if(c>=3)c++;else {for(int i=1; i<=n; i++) {for(int k=1;k<=n;k++){if(a[i][k]==1)cout<<k<<" ";}}cout<<endl;c++;}
}//输出前三组解
void zhanlin(int x,int y){a[x][y]=1;yi[y]=1;xjiany[x-y+n]=1;xjay[x+y]=1;
}//在（x，y）放皇后
void fangqi(int x,int y){a[x][y]=0;yi[y]=0;xjiany[x-y+n]=0;xjay[x+y]=0;
}//拿走（x，y）的皇后
int isok(int x,int y){if(a[x][y]==0&&yi[y]==0&&xjiany[x-y+n]==0&&xjay[x+y]==0)return 0;return 1;
}//该点是否可以放皇后
void dfs(int x) {if(x==n+1) {out();} else {for(int k=1; k<=n; k++) {if(isok(x,k)==0){zhanlin(x,k);dfs(x+1);fangqi(x,k);} }}
}//深搜
int main() {int i,k;cin>>n;dfs(1);cout<<c;return 0;
}