八皇后问题是高斯于 1950 年提出的,这是一个典型的回溯算法的问题。八皇后问题的大意如下:
国际象棋的棋盘是 8 行 8 列共 64 个单元格,在棋盘上摆件八个皇后,使其不能互相攻击,也就是说任意两个皇后都不能处于同一行、同一列或同一斜线上。
问总共有多少种摆放方法,每一种摆放方式是怎样的。目前,数学上可以证明八皇后问题总共有 92 种解。
- # 递归版本
- def nQueens(n, x=0, *solution):
- if x == n:
- yield solution
- else:
- for y in range(n):
- if all(y != j and abs(x - i) != abs(y - j) for i, j in solution):
- yield from nQueens(n, x + 1, *solution, (x, y))
- # 迭代版本
- def nQueensIter(n):
- solution = []
- j = 0
- while solution or j < n:
- i = len(solution)
- while j < n and not all(y != j and abs(x - i) != abs(y - j)
- for x, y in enumerate(solution)):
- j += 1
- if j < n:
- solution.append(j)
- if i == n - 1:
- yield tuple(enumerate(solution))
- j = solution.pop() + 1
- else:
- j = 0
- else:
- j = solution.pop() + 1
- if __name__ == '__main__':
- def showSolution(solutions, n):
- for i, s in enumerate(solutions, 1):
- print("%s:\n" % i + "=" * 20)
- for x in range(n):
- for y in range(n):
- print('Q ' if s[x][1] == y else '_ ', end='')
- print()
- print()
- N = 8
- showSolution(nQueens(N), N)
- showSolution(nQueensIter(N), N)
刘硕老师 Python 精品课程:
《Python 高级编程技巧实战》:
《Python 算法实战视频课程》:
《Python 科学计算—NumPy 实战课程》:
熊猫 TV 直播间:
来源: http://www.bubuko.com/infodetail-1952514.html