原题解答
本次的题目如下所示：
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即，其中为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串），下图为其中一组。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1≤b≤92)。
输出
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
输入样例
92
输出样例
看到这道题，可能很多同学首先想到的是使用枚举算法来解决这个问题。使用枚举算法肯定能解决这个问题，但是棋盘上有八行八列，如果使用枚举算法解决这个问题，那我们就需要嵌套8层循环，时间复杂度高达，程序的效率会非常低下。
因此，这个题目我们需要使用别的思想来解决。这里要提到回溯算法。回溯算法的思路是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。
我们看一下八皇后中冲突的情况：
从前往后寻找第i个皇后的列数，游标为j:
从前往后比较前i-1个皇后的位置是否与第i个皇后的位置冲突，游标为k:（k和i在图中表示行数）：
如果：
(1)列数冲突,即：第k个皇后的列数=第i个皇后的列数
(2)正对角线冲突，即:第k个皇后的行数-第i个皇后的行数=第k个皇后的列数-第i个皇后的列数
如图所示：
(3)副对角线冲突，即第i个皇后的行数-第k个皇后的行数=第k个皇后的列数-第i个皇后的列数
如图所示：
使用回溯算法解决的思路如下：
第一个皇后先放第一行第一列第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适位置继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤。
看到回溯算法的思路，我们可以发现，回溯算法利用了函数的递归调用。本道题最后代码如下所示：
a = [0] * 16
c = [0] * 16
u = [0] * 16
v = [0] * 16
ans = []
n = 8
def dfs(t):
global n
if t == n:
b = [str(a[i]) for i in range(n)]
ans.append("".join(b))
return
for i in range(n):
if c[i] == 1 or u[i + t] == 1 or v[i - t + n] == 1:
continue
c[i] = u[i + t] = v[i - t + n] = 1
a[t] = i + 1
dfs(t + 1)
c[i] = u[i + t] = v[i - t + n] = 0
dfs(0)
m = int(input())
while m > 0:
n = int(input())
print(ans[n - 1])
m -= 1
本题拓展
本题考查的是回溯算法，题目难度★★★★★
除了八皇后的问题，还有经典的黑白皇后问题也是使用类似的思路解决，我们看下面这道题：
给定一个n×n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入描述:
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出描述:
输出一个整数，表示总共有多少种放法。
输入样例：
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
输出样例：
由于每行都要放置黑皇后和白皇后，其实这就是n皇后问题（n*n的棋盘下放置n个皇后，它们之间不同行不同列不同对角线），在n行放置好白皇后的基础上放置黑皇后。
我们定义函数dfs(i,s)，i代表放置的行，s代表皇后的颜色（由于数字0和1在题目中指定用于表示是否可以放置皇后，我们假设2为白皇后、3为黑皇后）
我们开始先放置白皇后，起始为：dfs(0,2)
当dfs(i,n)中的i=n时，表示前n行已放置，判断当前皇后颜色状态：
若s=2，表示n个白皇后全部放置完毕，开始放置黑皇后,程序执行dfs(0,3);
若s=3，表示n个黑皇后全部放置完毕，又因为白皇后在黑皇后放置之前已放置完毕，所以可知n个黑皇后和n个白皇后都放置完毕，因此就可以得到一种放置方法。
根据分析后，我们的代码如下所示：
n = int(input())
mp = []
ans = 0
for i in range(n):
mp.append(list(map(int, input().split())))
def check(x, y, s):
global mp
global n
for i in range(0, x): # 测试该列是否放过同种颜色的皇后
if mp[i][y] == s:
return False
i = x - 1
j = y - 1
while (i >= 0 and j >= 0): # 测试左对角线是否放过同种颜色的皇后
if mp[i][j] == s:
return False
i -= 1
j -= 1
i = x - 1
j = y + 1
while (i >= 0 and j < n): # 测试右对角线是否放过同种颜色的皇后
if mp[i][j] == s:
return False
i -= 1
j += 1
return True
def dfs(x, s):
global ans
global n
global mp
if x == n:
if s == 2:
dfs(0, 3)
else:
ans += 1 # 黑皇后与白皇后都放置完毕，方法数+1
return
for j in range(0, n):
if mp[x][j] != 1:
continue
if not check(x, j, s):
continue
else:
mp[x][j] = s # 表示该层可以放置皇后
dfs(x + 1, s) # 下一层
mp[x][j] = 1 # 回溯
dfs(0, 2)
print(ans) ———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载 点击查看详情
站 长 微 信： nanadh666
