[python版]: # n-皇后问题
样例
输入样例:
4
输出样例:
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
第一种搜索顺序:知道每一行只有一个皇后
第一种搜索顺序 每一行只有一个皇后,当前i行,放置(i,j)
确定回溯状态,第i行
确定递归出口
展开当前第i行的j列活节点
def dfs(i):
if i == n:
#print('g',g)
for row in g:
print(''.join(row))
print()
return
for j in range(n):
#print(i, j, i + j, n - i + j-1)
if not col[j] and not dg[i + j] and not undg[n - i + j-1]:
g[i][j] = 'Q'
col[j], dg[i + j], undg[n - i + j-1] = True, True, True
dfs(i + 1)
col[j], dg[i + j], undg[n - i + j-1] = False, False, False
g[i][j] = '.'
n = int(input())
g = [['.'] * n for i in range(n)]
col = [False] * n
dg = [False] * (2 * n - 1)
undg = [False] * (2 * n - 1)
dfs(0)
你这里的ij表达的很清晰, 比y大的好懂