八皇后问题 Python实现

田田田

• 八皇后问题：国际象棋棋盘是8 * 8的方格，每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线（左上左下右上右下四个方向）上的棋子。在一个棋盘上如果要放八个皇后，使得她们互相之间不能攻击（即任意两两之间都不同行不同列不同斜线），求出一种（所有）布局方式。

• 注意事项：

  1.写一个函数，遍历所有位置，因为行不重复，所以遍历和找到皇后所在列的位置即可

  2.写一个检查函数，检查列重复以及对角线重复

  3.写一个函数打印结果

  4.不能硬编码

• 完整代码：

#!/usr/bin/python
# -*- coding: UTF-8 -*-
class solution(object):

    def queens_num(self, n):  #矩阵为n行n列
        self.position([-1] * n, 0, n)

    def position(self, col, row, n):  #row:当前行，col:每一行皇后的位置 n为总行数
        if row == n:
            self.printSolution(col, n)      #到最后一行，打印结果
            return

        for row_position in range(n):
            col[row] = row_position         #row_position皇后所在列的位置
            if self.isValid(col, row):
                self.position(col, row + 1, n)

    def isValid(self, col, row):
        if len(set(col[:row + 1])) != len(col[:row + 1]):   #检查列
            return False
        
        for i in range(row):            #检查对角线
            if abs(col[i] - col[row]) == int(row - i):  
                return False
        return True

    def printSolution(self, col, n):
        print col, '\n'
        for row in range(n):
            line = ""
            for column in range(n):
                if col[row] == column:
                    line += " Q "
                else:
                    line += " * "
            print(line)
        print('\n')


def main():
    q = solution()
    q.queens_num(8)


if __name__ == '__main__':
    main()

• 运行截图（一共有92种结果）：

image.png

附上原始的代码地址：https://zhuanlan.zhihu.com/p/71796190