02754: 八皇后
dfs and similar, http://cs101.openjudge.cn/practice/02754
描述：会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即
八皇后是一个古老的经典问题：如何在一张国际象棋的棋盘上，摆放8个皇后，使其任意两个皇后互相不受攻击。该问题由一位德国国际象棋排局家 Max Bezzel 于 1848年提出。严格来说，那个年代，还没有“德国”这个国家，彼时称作“普鲁士”。1850年，Franz Nauck 给出了第一个解，并将其扩展成了“ n皇后 ”问题，即在一张 n x n 的棋盘上，如何摆放 n 个皇后，使其两两互不攻击。历史上，八皇后问题曾惊动过“数学王子”高斯(Gauss)，而且正是 Franz Nauck 写信找高斯请教的。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 ≤ b ≤ 92)
输出
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
样例输入
2
1
92样例输出
15863724
84136275使用一维数组来表示棋盘是一种常见的优化方法，特别是对于 n 皇后问题。一维数组的每个元素表示每一行的皇后所在的列。这样可以减少空间复杂度，并且使代码更加简洁和高效。题面里直接就是优化表述。
# 02754 八皇后, http://cs101.openjudge.cn/practice/02754/
list1 = []
def queen(s):
if len(s) == 8:
list1.append(s)
return
for i in range(1, 9):
if all(str(i) != s[j] and abs(len(s) - j) != abs(i - int(s[j])) for j in range(len(s))):
queen(s + str(i))
queen('')
samples = int(input())
for k in range(samples):
print(list1[int(input()) - 1])
"""
abs(len(s) - j) != abs(i - int(s[j])) for j in range(len(s)) 是一个生成器表达式，
用于检查当前尝试放置的皇后是否与已经放置的皇后在同一条对角线上。具体解释如下：
- len(s) 表示当前已经放置的皇后的数量，即当前正在尝试放置的皇后的行号。
- j 是已经放置的皇后的列号。
- i 是当前尝试放置的皇后的列号。
- s[j] 是已经放置的皇后所在的列号。
对于每一个已经放置的皇后，检查以下条件：
- abs(len(s) - j) 计算当前尝试放置的皇后与已经放置的皇后之间的行差。
- abs(i - int(s[j])) 计算当前尝试放置的皇后与已经放置的皇后之间的列差。
如果行差和列差相等，说明两皇后在同一条对角线上，返回 `False`，否则返回 `True`。
"""Note:
1）string类型是不可变的，作为参数传递给函数时，实际上是复制了一份，可以避免由于共享引用导致的数据污染问题。这样就会避免八皇后使用列表的浅拷贝问题。
2）因为列表是可变对象，当一个列表被传递给函数时，是传递该列表的引用。如果在函数内部直接修改了这个列表，那么这些修改也会影响到原始列表。
但是列表很方便，允许原地修改，可以提高性能并简化代码。使用时候注意浅拷贝问题就好。
全排列、八皇后，可以对照着学习。全排列I, https://sunnywhy.com/sfbj/4/3/132，02754 八皇后, http://cs101.openjudge.cn/practice/02754/
python# 全排列I, https://sunnywhy.com/sfbj/4/3/132 list1 = [] def sequ(s, nums): if len(s) == nums: list1.append(s) return for i in range(1, nums + 1): if str(i) not in s: sequ(s + str(i), nums) num = int(input()) sequ('', num) for k in list1: print(' '.join(k))
思路：与全排列完全类似，一位一位向后排，只是多了额外的位置条件；注意在函数调用过程中要谨慎使用break，逻辑错误很容易导致递归出现问题，还很难检查。
02748: 全排列, recursion, http://cs101.openjudge.cn/practice/02748 04070: 全排列,recursion, http://cs101.openjudge.cn/practice/04070/
def queens(numlst,seq,ans):
if len(seq)==8:
ans.append(seq.copy())
return
for i in range(8):
if numlst[i]:
q=1
for j in range(len(seq)):
if abs(seq[j]-numlst[i])==abs(-j+len(seq)):
q=0
break
if q==1:
para=numlst[i]
numlst[i]=False
seq.append(para)
queens(numlst,seq,ans)
numlst[i]=para
seq.pop()
return
n=int(input())
nums=[i for i in range(1,9)]
for _ in range(n):
p=int(input())
solutions=[]
queens(nums,[],solutions)
print(*solutions[p-1],sep="")思路：用dfs算法，判断两个皇后不在同一斜线的方法是保证两个皇后所在坐标的行差不等于列差。
# 赵昱安 2200011450
answer = []
def Queen(s):
for col in range(1, 9):
for j in range(len(s)):
if (str(col) == s[j] or # 两个皇后不能在同一列
abs(col - int(s[j])) == abs(len(s) - j)): # 两个皇后不能在同一斜线
break
else:
if len(s) == 7:
answer.append(s + str(col))
else:
Queen(s + str(col))
Queen('')
n = int(input())
for _ in range(n):
a = int(input())
print(answer[a - 1])先给出两个dfs回溯实现的八皇后，接着给出两个stack迭代实现的八皇后。
八皇后思路：回溯算法通过尝试不同的选择，逐步构建解决方案，并在达到某个条件时进行回溯，以找到所有的解决方案。从第一行第一列开始放置皇后，然后在每一行的不同列都放置，如果与前面不冲突就继续，有冲突则回到上一行继续下一个可能性。
def solve_n_queens(n):
solutions = [] # 存储所有解决方案的列表
queens = [-1] * n # 存储每一行皇后所在的列数
def backtrack(row):
if row == n: # 找到一个合法解决方案
solutions.append(queens.copy())
else:
for col in range(n):
if is_valid(row, col): # 检查当前位置是否合法
queens[row] = col # 在当前行放置皇后
backtrack(row + 1) # 递归处理下一行
queens[row] = -1 # 回溯，撤销当前行的选择
def is_valid(row, col):
for r in range(row):
if queens[r] == col or abs(row - r) == abs(col - queens[r]):
return False
return True
backtrack(0) # 从第一行开始回溯
return solutions
# 获取第 b 个皇后串
def get_queen_string(b):
solutions = solve_n_queens(8)
if b > len(solutions):
return None
queen_string = ''.join(str(col + 1) for col in solutions[b - 1])
return queen_string
test_cases = int(input()) # 输入的测试数据组数
for _ in range(test_cases):
b = int(input()) # 输入的 b 值
queen_string = get_queen_string(b)
print(queen_string)def is_safe(board, row, col):
# 检查当前位置是否安全
# 检查同一列是否有皇后
for i in range(row):
if board[i] == col:
return False
# 检查左上方是否有皇后
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i] == j:
return False
i -= 1
j -= 1
# 检查右上方是否有皇后
i = row - 1
j = col + 1
while i >= 0 and j < 8:
if board[i] == j:
return False
i -= 1
j += 1
return True
def queen_dfs(board, row):
if row == 8:
# 找到第b个解，将解存储到result列表中
ans.append(''.join([str(x+1) for x in board]))
return
for col in range(8):
if is_safe(board, row, col):
# 当前位置安全，放置皇后
board[row] = col
# 继续递归放置下一行的皇后
queen_dfs(board, row + 1)
# 回溯，撤销当前位置的皇后
board[row] = 0
ans = []
queen_dfs([None]*8, 0)
#print(ans)
for _ in range(int(input())):
print(ans[int(input()) - 1])如果要使用栈来实现八皇后问题，可以采用迭代的方式，模拟递归的过程。在每一步迭代中，使用栈来保存状态，并根据规则进行推进和回溯。
def queen_stack(n):
stack = [] # 用于保存状态的栈
solutions = [] # 存储所有解决方案的列表
stack.append((0, tuple())) # 初始状态为第一行，所有列都未放置皇后,栈中的元素是 (row, queens) 的元组
while stack:
row, cols = stack.pop() # 从栈中取出当前处理的行数和已放置的皇后位置
if row == n: # 找到一个合法解决方案
solutions.append(cols)
else:
for col in range(n):
if is_valid(row, col, cols): # 检查当前位置是否合法
stack.append((row + 1, cols + (col,)))
return solutions[::-1]
def is_valid(row, col, queens):
for r, c in enumerate(queens):
if c == col or abs(row - r) == abs(col - c):
return False
return True
# 获取第 b 个皇后串
def get_queen_string(b, solutions):
if b > len(solutions):
return None
queen_string = ''.join(str(col + 1) for col in solutions[b - 1])
return queen_string
solutions = queen_stack(8)
# 读取输入数据
test_cases = int(input()) # 输入的测试数据组数
for _ in range(test_cases):
b = int(input()) # 输入的 b 值
queen_string = get_queen_string(b, solutions)
print(queen_string)def solve_n_queens(n):
stack = [] # 用于保存状态的栈
solutions = [] # 存储所有解决方案的列表
stack.append((0, [-1] * n)) # 初始状态为第一行，所有列都未放置皇后
while stack:
row, queens = stack.pop()
if row == n: # 找到一个合法解决方案
solutions.append(queens.copy())
else:
for col in range(n):
if is_valid(row, col, queens): # 检查当前位置是否合法
new_queens = queens.copy()
new_queens[row] = col # 在当前行放置皇后
stack.append((row + 1, new_queens)) # 推进到下一行
return solutions
def is_valid(row, col, queens):
for r in range(row):
if queens[r] == col or abs(row - r) == abs(col - queens[r]):
return False
return True
# 获取第 b 个皇后串
def get_queen_string(b):
solutions = solve_n_queens(8)
if b > len(solutions):
return None
b = len(solutions) + 1 - b
queen_string = ''.join(str(col + 1) for col in solutions[b - 1])
return queen_string
test_cases = int(input()) # 输入的测试数据组数
for _ in range(test_cases):
b = int(input()) # 输入的 b 值
queen_string = get_queen_string(b)
print(queen_string)详细步骤（参考 https://www.jianshu.com/p/deb028537af2）： 1）判断新的皇后是否与已经存在的皇后打架，加入是第一个则不用判断直接加入。
第1个皇后
2）第二行新生成的皇后，然后与第一行判断是否打架，是的话，向右移动一个格子，否则添加上去。
第2个皇后
3）第三行从左至右从第一个格子开始，判断是否与上面所有的皇后打架，是的话，向右移动一个格子，否则添加上去。
第3个皇后
第3个皇后
。。。
。。。
8）到第八行，新生成一个皇后，判断是否与上面所有的皇后打架，没有则添加。有则向右移动一个格子。当移动至一个不打架的格子，则一个解法已经生成。向后则寻找第二个方案，将第8行的皇后删除（for循环的下一列），新生成的皇后在刚才最后一个皇后的右边，为什么在右边呢？因为左边刚才已经判断过都失败了，所以新生成的在右边，然后在判断是否与上边的皇后打架。
终于找完了8个皇后
9）当向右移动最后一个格子而且与上边的皇后打架，则删除掉此皇后（for循环的下一列），然后把上一行的皇后向右移动一个格子（for循环的下一列），第8行从左向右从0开始生成一个新的皇后。然后 步骤8）.
第92种解法
10）直到第一行的皇后走到第一行的最后一个，第二行也找到最后一个格子的皇后，而且失败，则是所有解法都寻找完成。
在开始寻找第93种解法的时候，是这样子
判断两个棋子是否同一斜线，https://www.cnblogs.com/spmt/p/10607457.html
任意两个棋子不能在同一斜线上，可以把整个棋盘当作是一个
这里在记录解的时候，不能直接引用数组，否则最终解集中的解都是重复的，要进行拷贝，另外开辟出一个数组空间用解集记录。
ans = []
def queen_dfs(A, cur=0): #考虑放第cur行的皇后
if cur == len(A): #如果已经放了n个皇后，一组新的解产生了
ans.append(''.join([str(x+1) for x in A])) #注意避免浅拷贝
return
for col in range(len(A)): #将当前皇后逐一放置在不同的列，每列对应一组解
for row in range(cur): #逐一判定，与前面的皇后是否冲突
#因为预先确定所有皇后一定不在同一行，所以只需要检查是否同列，或者在同一斜线上
if A[row] == col or abs(col - A[row]) == cur - row:
break
else: #若都不冲突
A[cur] = col #放置新皇后，在cur行，col列
queen_dfs(A, cur+1) #对下一个皇后位置进行递归
queen_dfs([None]*8)
for _ in range(int(input())):
print(ans[int(input()) - 1])# 2021fall-cs101, TA_HU Yang
result = []
def dfs (former=[],i = 0,col_selected =[], a_diag =set(),b_diag =set()):
if i == 8:
result.append(former)
return
for j in range(8):
if j not in col_selected and i-j not in a_diag and i+j not in b_diag:
dfs(former+[j+1], i+1, col_selected+[j], a_diag|{i-j},b_diag|{i+j})
dfs()
n = int(input())
for i in range(n):
index = int(input())
print(''.join(map(str,result[index-1])))"""
当使用回溯法解决 N 皇后问题时，在每一行中依次尝试放置皇后，
然后回溯处理不符合条件的情况。
"""
result = []
def is_valid(former, row, col):
for i in range(row):
if former[i] == col or abs(i - row) == abs(former[i] - col):
return False
return True
def backtrack(former=[], row=0):
if row == 8:
result.append(former[:])
return
for col in range(8):
if is_valid(former, row, col):
former.append(col)
backtrack(former, row + 1)
former.pop()
backtrack()
n = int(input())
for i in range(n):
index = int(input())
print("".join(str(x+1) for x in result[index - 1]))2020fall-cs101，李博海。思路：queen_dfs_non_recursive
def queen_dfs_non_recursive():
stack = [([None] * 8, 0)]
while stack:
A, cur = stack.pop()
if cur == len(A):
ans.append(''.join([str(x+1) for x in A]))
continue
for col in range(len(A)-1, -1, -1): # push child nodes to stack by reverse order
for row in range(cur):
if A[row]==col or abs(col-A[row])==cur-row:
break
else:
A[cur] = col
stack.append((A[:], cur+1))
ans = []
queen_dfs_non_recursive() # with proper dfs order
for _ in range(int(input())):
print(ans[int(input()) - 1])c not in [a, a-2, a+2.... ] 不能在对角线上
#OJ eight queens
A = []
for a in range(1,9):
for b in range(1,9):
if b not in [a, a-1, a+1]:
for c in range(1,9):
if c not in [a,a-2,a+2, b,b-1,b+1]:
for d in range(1,9):
if d not in [a,a-3,a+3,b,b-2,b+2,c,c-1,c+1]:
for e in range(1,9):
if e not in[a,a-4,a+4,b,b-3,b+3,c,c-2,c+2,d,d-1,d+1]:
for f in range(1,9):
if f not in [a,a-5,a+5,b,b-4,b+4,c,c-3,c+3,d,d-2,d+2,e,e-1,e+1]:
for g in range(1,9):
if g not in [a,a-6,a+6,b,b-5,b+5,c,c-4,c+4,d,d-3,d+3,e,e-2,e+2,f,f-1,f+1]:
for h in range(1,9):
if h not in [a,a-7,a+7,b,b-6,b+6,c,c-5,c+5,d,d-4,d+4,e,e-3,e+3,f,f-2,f+2,g,g-1,g+1]:
A.append(''.join( map(str, [a,b,c,d,e,f,g,h] )))
for _ in range(int(input())):
print(A[int(input()) - 1])2020fall-cs101，蓝克轩。
思路：本的想法是对角线一个是差不变，一个是和不变，可是做起来太复杂了，看了解答才发现可以直接利用斜率的绝对值=1，即绝对值(列差)=行差。另外，还发现就是由于棋盘是对称的，可以只生成一半的解，再用99999999减去前半部的解求得后半部的解。
ans=[[] for j in range(46)]
num=0
def queen(a,step):
global num
if num>45:
return 0
if step==8:
ans[num]=a[:]
num+=1
return 0
for col in range(8):
a[step]=col
safe=True
for before in range(step):
if a[before]==col or abs(col-a[before])==step-before:
safe=False
break
if safe:
queen(a,step+1)
queen([None for i in range(8)],0)
for _ in range(int(input())):
a=int(input())-1
print("".join((str(x+1) for x in ans[a]) if a<46 else (str(8-x) for x in ans[91-a])))2021fall-cs101, 陈锦洋。
值得注意的是第三行的定义全局变量，我以前大概知道有这么一回事，但用了dfs 后才算碰到一个需要它的场合。Global 告诉函数下面提及的这些变量是全局变量，这样不管函数第几层调用自己，都可以对全局变量直接修改。Return 可加可不加，加上可以让函数少跑几步。q[:]不能替换为q，不然只是一个指向q 的变量，会和q 一起同步变化。第六行和第八行是一对，表示一个后的放置与移除。可想而知，当所有位置都遍历后，棋盘上是空空如也的。但正如泰戈尔说：“天空中没有鸟的痕迹，但我已飞过。”棋盘上没有我走过的痕迹，但我已经通过循环+递归把所有可能性都走了一遍。这一点和“马走日”是一样的。Dfs 是深度优先搜索，所以就必然会要自己调用自己（递归）；而bfs 是宽度优先搜索，只要准备一个列表queue 就可以了。
q = []
ans = [0]
i = -1
def queens():
global i, ans, q
if i == 7:
ans += q[:],
return
for k in range(1,9):
q += k,
i += 1
if all(q[i]!=q[j] and i-j!=abs(q[i]-q[j]) for j in range(i)):
queens()
q.pop()
i-=1
queens()
for _ in [0]*int(input()):
print(*ans[int(input())], sep='')2021fall-cs101，李文梁。
纵向排除很简单，直接现有字符串不包含该数字即可斜向排除可以遍历前面几个数，位置之差不能等于数字之差的绝对值我用的相等 求和 再用或 取反，相当于纵向和斜向整体NOR（如果紧凑，把6、8、11行合并到上一行写，可以八行解决八皇后）
2022fall-cs101, 项天歌，物理学院。看了答案代码，发现可以用这种类似dp 的算法，存储前几位尚未矛盾的皇后位置，对之后的皇后位置遍历达到排除或存储的目的，用函数的自我调用深度优先搜索找出所有的解。
a=[]
def q(l,n):
for i in "12345678":
if not(i in n or sum(abs(int(i) - int(n[j])) == l - j for j in range(l))):
if l > 6:
a.append(n + i)
else:
q(l + 1, n + i)
q(0, "")
for _ in range(int(input())):
print(a[int(input()) - 1])2022fall-cs101，鞠志翔，工学院。
听说这题用什么dfs+回溯，但都没有用就做完了，好像不讲武德。感觉是一道组合数学的题，所以进口了一个好使的函数permutations ，排列过程的本身即可避免皇后共水平线或竖直线；然后再对着8！组数检验是否共斜线即可。
2022fall-cs101，张博康，化学与分子工程学院。
可以直接对8 的全排列使用对角线约束条件（任两数字差不等于其位置差）筛一遍即可。
s=[1,2,3,4,5,6,7,8]
result=[]
final_result=[]
from itertools import permutations
for i in permutations(s,8):
result.append(i)
for k in result:
n=0
for i in range(8):
for j in range(8):
if i!=j and abs(i-j)==abs(k[i]-k[j]):
n+=1
if n==0:
final_result.append(k)
for i in range(int(input())):
k=int(input())
s=final_result[k-1]
print(''.join(map(str,s)))八皇后的递归写法，如果不容易理解，可以先把穷举的方法掌握了。
在八皇后问题中，每个皇后放在不同的行且不同的列，因此可以使用排列 (permutation) 来建立解空间。每种排列代表每行中的一个皇后所在的列。通过检查排列是否满足对角线的约束（即两个皇后不能在同一对角线上），可以筛选出合法的解。
# 02754:八皇后 http://cs101.openjudge.cn/practice/02754/ 穷举法
from itertools import permutations
def solve_n_queens(n):
solutions = []
cols = range(n)
# 生成每一行皇后位置的排列
for perm in permutations(cols):
# 检查是否有两个皇后在同一对角线上
if n == len(set(perm[i] + i for i in cols)) == len(set(perm[i] - i for i in cols)):
# 如果满足条件，加入解
solutions.append(perm)
return solutions
solutions = solve_n_queens(8)
for _ in range(int(input())):
n = int(input())
queen_string = ''.join(str(col + 1) for col in solutions[n - 1])
print(queen_string)具体来说，排列
(c1, c2, ..., cn)表示第 1 行的皇后在第c1列，第 2 行的皇后在第c2列，以此类推。对角线检查
为了确保没有两个皇后在同一对角线上，我们需要检查以下两种类型的对角线：
- 主对角线（从左上到右下）：对于位置
(i, j)，主对角线上的其他位置(i', j')满足i - j = i' - j'。- 副对角线（从右上到左下）：对于位置
(i, j)，副对角线上的其他位置(i', j')满足i + j = i' + j'。具体实现
在代码中，我们使用集合来检查对角线冲突：
- 主对角线检查：使用
set(perm[i] + i for i in cols)来检查主对角线上的冲突。- 副对角线检查：使用
set(perm[i] - i for i in cols)来检查副对角线上的冲突。如果这两个集合的大小都等于
n，说明没有两个皇后在同一对角线上。通过对角线检查，我们可以确保生成的排列中没有两个皇后在同一对角线上。这种方法利用了集合的唯一性特性，高效地检查了对角线冲突。
详细解释一下主对角线和副对角线的原理。
主对角线（从左上到右下）
对于位置
(i, j)，主对角线上的其他位置(i', j')满足i - j = i' - j'。这是因为主对角线上的所有位置在直角坐标系中具有相同的i - j值。举例说明
考虑一个 4x4 的棋盘，我们标记出所有的主对角线：
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3)对于每个位置
(i, j)，计算i - j的值：
(0,0)->0 - 0 = 0(0,1)->0 - 1 = -1(0,2)->0 - 2 = -2(0,3)->0 - 3 = -3(1,0)->1 - 0 = 1(1,1)->1 - 1 = 0(1,2)->1 - 2 = -1(1,3)->1 - 3 = -2(2,0)->2 - 0 = 2(2,1)->2 - 1 = 1(2,2)->2 - 2 = 0(2,3)->2 - 3 = -1(3,0)->3 - 0 = 3(3,1)->3 - 1 = 2(3,2)->3 - 2 = 1(3,3)->3 - 3 = 0可以看到，主对角线上的位置具有相同的
i - j值。例如，主对角线(0,0), (1,1), (2,2), (3,3)上的所有位置的i - j值都是 0。副对角线（从右上到左下）
对于位置
(i, j)，副对角线上的其他位置(i', j')满足i + j = i' + j'。这是因为副对角线上的所有位置在直角坐标系中具有相同的i + j值。举例说明
继续考虑同一个 4x4 的棋盘，我们标记出所有的副对角线：
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3)对于每个位置
(i, j)，计算i + j的值：
(0,0)->0 + 0 = 0(0,1)->0 + 1 = 1(0,2)->0 + 2 = 2(0,3)->0 + 3 = 3(1,0)->1 + 0 = 1(1,1)->1 + 1 = 2(1,2)->1 + 2 = 3(1,3)->1 + 3 = 4(2,0)->2 + 0 = 2(2,1)->2 + 1 = 3(2,2)->2 + 2 = 4(2,3)->2 + 3 = 5(3,0)->3 + 0 = 3(3,1)->3 + 1 = 4(3,2)->3 + 2 = 5(3,3)->3 + 3 = 6可以看到，副对角线上的位置具有相同的
i + j值。例如，副对角线(0,3), (1,2), (2,1), (3,0)上的所有位置的i + j值都是 3。