题目链接：
题目描述
有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：
- 任何两个皇后不在同一行。
- 任何两个皇后不在同一列。
- 如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。
请问一共有多少种摆放方案。
输入描述
输入的第一行包含一个整数 n。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
4
输出
2
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
JAVA解法 ：
import java.util.Arrays; import java.util.Scanner; public class n皇后2 { static int n ; static int[] a; static int count=0 ; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt()+1; a = new int[n]; dfs(1); System.out.println(count); } private static void dfs(int row) {//第row皇后放何处 if (row==n){ count++; //System.out.println(Arrays.toString(a)); } for (int i = 1; i <= n-1; i++) {//生成列 if (check(row,i)){ a[row]=i; dfs(row+1); a[row]=0; } } } private static boolean check(int row, int col) { for (int j = 1; j <= row; j++) {//在已经放过皇后的行进行判断 if (a[j]==col) return false; //j行a[j]列已有皇后 if (j+a[j] == row+col) return false;//这个位置的反对角线已有皇后 if (j-a[j] == row-col) return false;//这个位置的正对角线已有皇后 } return true; } }
C++解法：
#include <iostream> using namespace std; int a[10]={0};//用来存储第i行存储在第几列 int count,n; bool valid(int row,int y)//判断row行的y列是否可用 { for(int i=1;i<row;i++)//判断前row-1行中有无与y冲突的列 { if(a[i]==y) return false;//前row-1行中有行存在第y列不可用 if((a[i]+i==row+y)&&(row-i)<3) return false;//前row-1行中有列存在和第y列在反对角线上不可用 if((row-i==y-a[i])&&(row-i)<3) return false;//前row-1行中有列存在和第y列在正对角线上不可用 } return true; } void dfs(int row) { if(row==n+1)//前row行均以排完，方案数加一 { count++; return; } for(int i=1;i<=n;i++)//依次判断1到n列有无可用 { if(valid(row,i))//row行i列可用 { a[row]=i;//row行存在第i列 dfs(row+1);//处理下一行 a[row]=0;//重置便与尝试新方案 } } } int main() { cin>>n; dfs(1); cout<<count; return 0;//给楼里一位兄弟的代码加了些个人认为的注释，便于各位理解 }
python解法：
import os import sys import math # 请在此输入您的代码 # 使用dfs进行深度搜索，其中会有多种重复 # 用dfs深搜的结果 / 行数的阶乘可得正确答案 def isleagal(x,y): if 0 <= x < n and 0 <= y < n : return True return False def isrowcol(i,j): # 行列没有返回True for k in range(n): if v[i][k] ==1 or v[k][j] == 1: return False return True def isxie(i,j): # 45度对角线没有返回True dx = [1,1,-1,-1] dy = [1,-1,-1,1] for k in range(4): for m in range(1,3): nx = i+dx[k]*m ny = j+dy[k]*m if isleagal(nx,ny) and v[nx][ny] ==1: return False return True def dfs(x): if x == n: # 当放的皇后的数量x == n时结束 ans[0] +=1 return for i in range(n): for j in range(n): if v[i][j] == 0 and isrowcol(i,j) and isxie(i,j): v[i][j]=1 dfs(x+1) v[i][j]=0 ans =[0] n = int(input()) num = 1 for i in range(1,n+1): num *= i v = [] for i in range(n): v.append([0] * n) dfs(0) print(ans[0]//num )
