一、受伤的皇后——21年模拟赛
题目链接：
题目描述
有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：
- 任何两个皇后不在同一行。
- 任何两个皇后不在同一列。
- 如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。
请问一共有多少种摆放方案。
输入描述
输入的第一行包含一个整数 n。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
4
输出
2
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
JAVA解法 ：
importjava.util.Arrays; importjava.util.Scanner; publicclassn皇后2 { staticintn ; staticint[] a; staticintcount=0 ; publicstaticvoidmain(String[] args) { Scannersc=newScanner(System.in); n=sc.nextInt()+1; a=newint[n]; dfs(1); System.out.println(count); } privatestaticvoiddfs(introw) {//第row皇后放何处if (row==n){ count++; //System.out.println(Arrays.toString(a)); } for (inti=1; i<=n-1; i++) {//生成列if (check(row,i)){ a[row]=i; dfs(row+1); a[row]=0; } } } privatestaticbooleancheck(introw, intcol) { for (intj=1; j<=row; j++) {//在已经放过皇后的行进行判断if (a[j]==col) returnfalse; //j行a[j]列已有皇后if (j+a[j] ==row+col) returnfalse;//这个位置的反对角线已有皇后if (j-a[j] ==row-col) returnfalse;//这个位置的正对角线已有皇后 } returntrue; } }
C++解法：
usingnamespacestd; inta[10]={0};//用来存储第i行存储在第几列 intcount,n; boolvalid(introw,inty)//判断row行的y列是否可用 { for(inti=1;i<row;i++)//判断前row-1行中有无与y冲突的列 { if(a[i]==y) returnfalse;//前row-1行中有行存在第y列不可用 if((a[i]+i==row+y)&&(row-i)<3) returnfalse;//前row-1行中有列存在和第y列在反对角线上不可用 if((row-i==y-a[i])&&(row-i)<3) returnfalse;//前row-1行中有列存在和第y列在正对角线上不可用 } returntrue; } voiddfs(introw) { if(row==n+1)//前row行均以排完，方案数加一 { count++; return; } for(inti=1;i<=n;i++)//依次判断1到n列有无可用 { if(valid(row,i))//row行i列可用 { a[row]=i;//row行存在第i列dfs(row+1);//处理下一行a[row]=0;//重置便与尝试新方案 } } } intmain() { cin>>n; dfs(1); cout<<count; return0;//给楼里一位兄弟的代码加了些个人认为的注释，便于各位理解}
python解法：
importosimportsysimportmathdefisleagal(x,y): if0<=x<nand0<=y<n : returnTruereturnFalsedefisrowcol(i,j): #行列没有返回Trueforkinrange(n): ifv[i][k] ==1orv[k][j] ==1: returnFalsereturnTruedefisxie(i,j): #45度对角线没有返回Truedx= [1,1,-1,-1] dy= [1,-1,-1,1] forkinrange(4): forminrange(1,3): nx=i+dx[k]*mny=j+dy[k]*mifisleagal(nx,ny) andv[nx][ny] ==1: returnFalsereturnTruedefdfs(x): ifx==n: #当放的皇后的数量x==n时结束ans[0] +=1returnforiinrange(n): forjinrange(n): ifv[i][j] ==0andisrowcol(i,j) andisxie(i,j): v[i][j]=1dfs(x+1) v[i][j]=0ans=[0] n=int(input()) num=1foriinrange(1,n+1): num*=iv= [] foriinrange(n): v.append([0] *n) dfs(0) print(ans[0]//num )
