Python3でnクイーン問題を解く

nクイーン問題とは

n×nのチェスの盤上に、n個のクイーンがお互いを攻撃しないように、ボード上に配置する問題。
n-クイーン(Wikipedia)

バックトラック法の例として有名な問題 (バックトラック法とは)

実装

nqueens.py

def n_queen(n):
    count = 0
    for board in put_queens(board=[n] * n):
        for queen in board:
            print(''.join('.Q'[x == queen] for x in range(n)))
        print()
        count += 1
    print(count, 'ways')


def put_queens(board, y=0):
    n = len(board)
    if y == n:
        yield board
    else:
        for x in range(n):
            if not conflict(board, x, y):
                board[y] = x
                yield from put_queens(board, y + 1)


def conflict(board, x, y):
    return any(tx == x or tx + (y - ty) == x or tx - (y - ty) == x
               for ty, tx in enumerate(board[:y]))


if __name__ == '__main__':
    n_queen(int(input('n = ')))

入力:
n