8 Queen Problem, Python 3

8queen.py

#!/usr/bin/env python3
# 8 Queens Problem
# by James Swineson

from functools import reduce

# 一个棋盘的表示，其中 .board[i] 表示第 i 行的旗子在第几列
class nQueenBoard:
    def __init__(self, size, board=[]):
        self.size = size
        self.board = board

    # 用于自定义 print() 时的结果
    def __str__(self):
        return str(self.board)

# 求解器
class nQueenSolver:
    # 检查棋盘是否符合规则
    @staticmethod
    def __isValidBoard(board):
        # 检查行列是否有冲突（所有列数之和应当等于 1+2+...+n）
        # 现有的搜索方式不会遇到这个情况所以注释掉
        # if reduce(lambda x, y: x + y, board.board) != int(board.size * (board.size - 1) / 2):
        #     return False
        # 检测一个方向对角线（不出现行列序号之差相等）
        if len(set([x - board.board[x] for x in range(len(board.board))])) != board.size:
            return False
        # 检查另一个方向对角线（不出现行列之和相等）
        if len(set([x + board.board[x] for x in range(len(board.board))])) != board.size:
            return False
        return True

    # 获取搜索树当前节点的所有子节点的 list
    @staticmethod
    def __getNextBoardSet(board):
        return map(
                    lambda x: nQueenBoard(board.size, board.board + [x]),
                    filter(lambda x: x not in board.board, range(0, board.size))
                  )

    # 执行搜索
    def __calc(self, currentBoardSet=[], currentDepth=0):
        # 递归结束条件
        if currentDepth == self.size:
            return list(filter(nQueenSolver.__isValidBoard, currentBoardSet))
        # 初始化递归变量（避免对同一对象操作）
        if currentBoardSet == []:
            currentBoardSet = [nQueenBoard(self.size)]
        # 递归：获取搜索树下一层所有节点并拼成一个 list
        return reduce(
                        lambda x, y: x + y,
                        map(lambda board: self.__calc(nQueenSolver.__getNextBoardSet(board), currentDepth + 1), currentBoardSet),
                        []
                     )

    # 对象构造函数
    def __init__(self, size):
        if size < 1: raise ValueError("Board size should be greater than 0")
        self.size = size
        self.result = self.__calc()

    # 用于 for .. in
    def __iter__(self):
        return iter(self.result)

    # 用于 len()
    def __len__(self):
        return len(self.result)

if __name__ == "__main__":
    import time
    for x in range(1, 9):
        print("Queen number: ", x)
        start_time = time.time()
        a = nQueenSolver(x)
        for board in a:
            print(board)
        print("Total count: ", len(a))
        print("Execution time: %ss" % (time.time() - start_time))
        print("-" * 20)