Eight queens problem

题目

his is a classical problem in computer science. The objective is to place eight queens on a chessboard so that no two queens are attacking each other; i.e., no two queens are in the same row, the same column, or on the same diagonal.

Hint: Represent the positions of the queens as a list of numbers 1..N. Example: [4,2,7,3,6,8,5,1] means that the queen in the first column is in row 4, the queen in the second column is in row 2, etc. Use the generate-and-test paradigm.

八皇后问题

八皇后问题是一个以西洋棋为背景的问题：如何能够在8×8的西洋棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。若且唯若n = 1或n ≥ 4时问题有解。

解题

最简单的方法就是枚举，用回溯法列出所有的摆法（八个皇后在8x8棋盘上共有4,426,165,368（64C8）种摆放方法）。再逐一检测是否符合要求。

枚举法简单但低效，可以以其为基础加以优化。在回溯的时候，可以提前排除不可能的摆法。当为第i为皇后寻找位置时，之前的皇后位置都已确定。则此时已经可以为第i个皇后排除掉不可行的位置。

比如，第1个皇后已经选在了第一行第列。则第二行中，第一列和第二列就是不可行的位置，第二个皇后只能从其它的位置中选择。

代码实现

def eight_queens(): return queens(8, 8, []) def queens(m, n, allocatedQueens): if n == 0: return [[]] availablePostions = allocate(m, allocatedQueens) return [[queen] + remain for queen in availablePostions for remain in queens(m, n-1, allocatedQueens + [queen])] def allocate(m, allocatedQueens): for pos in range(1, m+1): if isAvailable(pos, allocatedQueens): yield pos def isAvailable(pos, allocatedQueens): if pos in allocatedQueens: return False for index in range(1, len(allocatedQueens)+1): if allocatedQueens[-index]+index == pos: return False if allocatedQueens[-index]-index == pos: return False return True

这𥚃使用递归实现回溯。假设，已有若干个皇后选好位置，现在再加入一个皇后。

  1. 首先，罗列本行所有的位置。
  2. 然后，排除掉跟已有皇后位置相冲的位置（同列、同斜⻆线）。
  3. 最后，计算后皇后的摆放位置。这𥚃套用步骤1和2。

每一个皇后都有多种位置可选，后续皇后的位置也有多种选项。所以，这𥚃用双重List Comprehension列出所有的组合。

参考

results matching ""

    No results matching ""