再帰呼出に挑戦 「Python 18 lines: 8-Queens Problem」より

先日、Python の 18行プログラム「8-Queens Problem」を紹介しました。

この記事の最後に次のような問題を2つ提示しました。

(1)関数「under_attack」を再帰呼出で書けるでしょうか。

(2)関数「solve」を再帰呼出を使わずに書けるでしょうか。

そして今回は回答編です。

---

関数「under_attack」を再帰呼出で書いてみた

BOARD_SIZE = 8

def under_attack(left, col, right, queens, n):
    if n == 0:
        return False
    
    if n <= len(queens):
        r, c = queens[n-1]
        if c in (left, col, right):
            return True
        
    return under_attack(left-1, col, right+1, queens, n-1)

def solve(n):
    if n == 0:
        return [[]]

    smaller_solutions = solve(n - 1)

    return [solution+[(n,i+1)]
        for i in range(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, i+1, i+1, solution, n)]

ちょっと微妙な感じ。
引数が増えてしまった。
left、right への破壊的な代入はなくなったけど。

「if n <= len(queens):」
この条件文をなくせないものか。

「エレガント」というには一歩足りないような。

---

関数「solve」を再帰呼出を使わずに書いてみた

BOARD_SIZE = 8

def under_attack(col, queens):
    left = right = col

    for r, c in reversed(queens):
        left, right = left - 1, right + 1

        if c in (left, col, right):
            return True
    return False

def solve():
    new_solutions = [[]]
    
    for n in range(BOARD_SIZE):
        smaller_solutions = new_solutions
        new_solutions = []
        
        for i in range(BOARD_SIZE):
            for solution in smaller_solutions:
                if not under_attack(i+1, solution):
                    new_solutions += [solution + [(n+1,i+1)]]
    return new_solutions

なんとなく。
ちょっとややこしいですね。

「for n in range(BOARD_SIZE)」でループするのですが、前のループの結果である「new_solutions」を使わなければなりません。

1.smaller_solutions に待避してから
2.new_solutions をクリアして
3.新しい new_solutions を作り出す

という手順なります。

こんな風に書いてみると、データがプログラミングの要であるとつくづく思います。過去に出会った「理解が難しいコード」に間違いなくあったのは「よくわからないデータ」でした。

わかりやすいコードを目指して。