「女王たちを一緒にするな」を解いてみました

「問題解決のPythonプログラミング」という本の第4章「女王たちを一緒にするな」の問題を解いてみました。

前回↓

Nクイーン問題の一歩手前の８クイーン問題ですね。8×8の盤面で8つのクイーンがお互いの効き（移動範囲）に入らないように配置することができるか？という問題です。
ここで表示されるリストは各インデックスが盤面の列数を、それぞれの数字が盤面の行数を表します。

問題１

サンプルにあるコードを完成させると、８クイーン問題の解答が出力されるようになります。その解が結構あるので、新たに任意の解の数字だけ出力させるプログラムを書く、というものですね。

def eight_queens_n(answer: int, n=8):
    """練習問題1の解答用。求める解の数を引数にとり、その数だけ出力する"""
    board = [-1] * n
    ans_count = 0
    for i in range(n):
        board[0] = i
        for j in range(n):
            board[1] = j
            if not no_conflicts(board, 1):
                continue
            for k in range(n):
                board[2] = k
                if not no_conflicts(board, 2):
                    continue
                for l in range(n):
                    board[3] = l
                    if not no_conflicts(board, 3):
                        continue                
                    for m in range(n):
                        board[4] = m
                        if not no_conflicts(board, 4):
                            continue
                        for o in range(n):
                            board[5] = o
                            if not no_conflicts(board, 5):
                                continue
                            for p in range(n):
                                board[6] = p
                                if not no_conflicts(board, 6):
                                    continue
                                for q in range(n):
                                    board[7] = q
                                    if no_conflicts(board, 7):
                                        print(board)
                                        ans_count += 1
                                        if ans_count == answer:
                                            return
    return

パズル問題２

８クイーン問題を解く際、予めユーザーが特定の場所にクイーンを置いていたらどんな解答になるか出力する問題です。リストの-1がまだクイーンが置かれていないことを示します。

def eight_queens_location(location: list, n=8):
    "パズル問題２の解答"
    board = [-1] * n
    for i in range(n):
        board[0] = i
        for j in range(n):
            board[1] = j
            if not no_conflicts(board, 1):
                continue
            for k in range(n):
                board[2] = k
                if not no_conflicts(board, 2):
                    continue
                for l in range(n):
                    board[3] = l
                    if not no_conflicts(board, 3):
                        continue                
                    for m in range(n):
                        board[4] = m
                        if not no_conflicts(board, 4):
                            continue
                        for o in range(n):
                            board[5] = o
                            if not no_conflicts(board, 5):
                                continue
                            for p in range(n):
                                board[6] = p
                                if not no_conflicts(board, 6):
                                    continue
                                for q in range(n):
                                    board[7] = q
                                    if no_conflicts(board, 7):
                                        for r, s in zip(location, board):
                                            if r != -1:
                                                if r != s:
                                                    break
                                        else: # 指定場所が一致したら
                                            print(board)
    return

解答結果

解答結果を出力すると…

# 上記のコードの続き
if __name__ == '__main__':
    # 練習問題１
    print("練習問題１")
    eight_queens_n(4)
    print()

    # パズル問題２
    print("パズル問題２")
    eight_queens_location([-1, 4, -1, -1, -1, -1, -1, 0])

その出力が

練習問題１

[0, 4, 7, 5, 2, 6, 1, 3]

[0, 5, 7, 2, 6, 3, 1, 4]

[0, 6, 3, 5, 7, 1, 4, 2]

[0, 6, 4, 7, 1, 3, 5, 2]
パズル問題２

[2, 4, 1, 7, 5, 3, 6, 0]

次回↓