程序设计比赛一些经典的题目

 1. N皇后问题

1.1 受伤的皇后

有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：

1. 任何两个皇后不在同一行。
2. 任何两个皇后不在同一列。
3. 如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。

请问一共有多少种摆放方案。

输入描述

输入的第一行包含一个整数 n。其中，1≤n≤10。

输出描述

输出一个整数，表示答案。

输入

4

输出 

2 

python解答

import os
import sysn = int(input())  # 皇后数量
col = [100]*n  # 记录每一行的皇后在第几列，[100]表示10*10的列表
count = 0def dfs(row): #定义一个表示行的函数global n,col,count #声明全局变量if row == n: # 如果行数=皇后个数count+=1 # 只有一种摆法else:for i in range(n): # 用于遍历当前皇后可以存放的列flage = Truefor k in range(n): # 遍历之前的皇后所在的行if i == col[k]: # col[k]存的是第k行的皇后所存放的列，如果当前列已经有其他皇后存在，则不能放flage = False elif abs(row-k)==abs(i-col[k]) and abs(row-k)<3: #如果与其他行的皇后处在一个斜线上，也不满足条件flage = Falseif flage:col[row] = i#标记dfs(row+1)#可以放就放了，然后做递归判断下一行col[row] = 100#这里要回溯？因为做完这一行，就返回到上一行去换一列dfs(0)
print(count)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！