八皇后問題 Python實(shí)現(xiàn)

田田田

• 八皇后問題：國(guó)際象棋棋盤是8 * 8的方格，每個(gè)方格里放一個(gè)棋子?；屎筮@種棋子可以攻擊同一行或者同一列或者斜線（左上左下右上右下四個(gè)方向）上的棋子。在一個(gè)棋盤上如果要放八個(gè)皇后，使得她們互相之間不能攻擊（即任意兩兩之間都不同行不同列不同斜線），求出一種（所有）布局方式。

• 注意事項(xiàng)：

  1.寫一個(gè)函數(shù)，遍歷所有位置，因?yàn)樾胁恢貜?fù)，所以遍歷和找到皇后所在列的位置即可

  2.寫一個(gè)檢查函數(shù)，檢查列重復(fù)以及對(duì)角線重復(fù)

  3.寫一個(gè)函數(shù)打印結(jié)果

  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:當(dāng)前行，col:每一行皇后的位置 n為總行數(shù)
        if row == n:
            self.printSolution(col, n)      #到最后一行，打印結(jié)果
            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):            #檢查對(duì)角線
            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()

• 運(yùn)行截圖（一共有92種結(jié)果）：

image.png

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