Thothの日誌

日々の活動や読んだ本について書き綴っていこうと思います

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


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

前回↓

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

問題1

サンプルにあるコードを完成させると、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

パズル問題2

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

def eight_queens_location(location: list, n=8):
    "パズル問題2の解答"
    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__':
    # 練習問題1
    print("練習問題1")
    eight_queens_n(4)
    print()

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

その出力が

練習問題1
[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
[2, 4, 1, 7, 5, 3, 6, 0]