SimplePrograms で Python を学ぶ その１７

SimplePrograms - Python Wiki
https://wiki.python.org/moin/SimplePrograms

の 17番目のプログラムは、　18行の再帰呼び出し(エイト・クイーン問題)です。

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(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, solution)]
for answer in solve(BOARD_SIZE):
    print (answer)


ファイルにして実行してみます。出力は92行（解の総数）あるのでほとんど省略します。

$ ./prog-18.py
[(1, 4), (2, 2), (3, 7), (4, 3), (5, 6), (6, 8), (7, 5), (8, 1)]
.......... 省略　....................
[(1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3), (8, 8)]
[(1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4), (8, 8)]
$

17番目のプログラムなのに１８行で、これ以降のサンプルプログラムは行が飛び飛びになっており、これまでよりより具体的なプログラムになっているようです。今後どうするかは、考えてみます。

これは、だいぶ前に Microsoft の Bing に質問した解説があるので紹介します。現在どうなっているかは試して見てください。
まずは、最初の８行の部分です。
ここから ----------------------
こんにちは、これはBingです。??

8-queens の問題とは、8×8のチェス盤に8つのクイーンを互いに攻撃しないように配置する問題です12。一般に、n-queens の問題として、n×nのチェス盤にn個のクイーンを配置する問題も考えられます1。

Python で書かれたサンプルプログラムは、再帰的な関数とリスト内包表記を使って、n-queens の問題のすべての解を求めるものです3。コードの各部分について説明します。

(1)まず、BOARD_SIZE = 8 という行は、チェス盤のサイズを定義しています。この値を変えると、n-queens の問題に対応できます。

(2)次に、under_attack(col, queens) という関数は、ある列番号 col と既に配置されたクイーンのリスト queens を引数にとり、その列にクイーンを置くことができるかどうかを判定する関数です。この関数では、以下の処理を行っています。

(3)・ left と right という変数に col を代入します。これらは、左斜め上方向と右斜め上方向にあるクイーンの列番号を表します。
(4)・ for r, c in reversed(queens): というループで、queens のリストを逆順に取り出しています。r は行番号、c は列番号です。
(5)・ left, right = left - 1, right + 1 という行で、left と right をそれぞれ1ずつ減らし、増やしています。これは、斜め上方向に移動することを表しています。
(6)・ if c in (left, col, right): という条件文で、c が left, col, right のいずれかと等しいかどうかを判定しています。これは、同じ列か同じ斜め方向にクイーンがあるかどうかを判定しています。
(7)・ もし条件が真ならば、True を返します。これは、その列にクイーンを置くことができないことを表しています。
(8)・ もしループが終了したら、False を返します。これは、その列にクイーンを置くことができることを表しています。

この関数は、クイーンの配置が可能かどうかを高速に判定するためのものです。
---------------------- ここまで (対応する行を () で追記してあります。

次に solve()　の部分（９行目から16行目まで）です。

ここから ----------------------
( 9)次に、solve(n) という関数は、n 個のクイーンを配置する問題のすべての解を求める関数です。この関数では、以下の処理を行っています。

(10)・ if n == 0: という条件文で、n が0かどうかを判定しています。これは、すべてのクイーンが配置されたかどうかを判定しています。
(11)・ もし n == 0 ならば、[[]] を返します。これは、空の解のリストを表しています。

(12)・ もし n != 0 ならば、smaller_solutions = solve(n - 1) という行で、smaller_solutions という変数に、n-1 個のクイーンを配置する問題のすべての解のリストを代入しています。これは、再帰的に関数を呼び出すことで、問題を小さく分割して解いていることを表しています。

(13)・ return [solution+[(n,i+1)] for i in range(BOARD_SIZE) for solution in small_solutions if not under_attack(i+1, solution)] という行(つまり、13,14,15,16行)で、リスト内包表記を使って、
n 個目のクイーンを配置する可能性のあるすべての解を生成しています。この行では、以下の処理を行っています。

(14) ・ for i in range(BOARD_SIZE): というループで、i を0から7まで変化させています。これは、列番号を表しています。
(15) ・ for solution in smaller_solutions: というループで、smaller_solutions のリストから要素を取り出しています。これは、n-1 個のクイーンを配置する問題の解を表しています。
(16) ・ if not under_attack(i+1, solution): という条件文で、i+1 番目の列にクイーンを置くことができるかどうかを判定しています。これは、under_attack 関数を呼び出して、クイーンが互いに攻撃しないかどうかを判定しています。

・ もし条件が真ならば、solution+[(n,i+1)] をリストに追加します。これは、n 個目のクイーンを i+1 番目の列に置いた場合の解を表しています。

・ このようにして、n 個のクイーンを配置する問題のすべての解のリストを返します。
---------------------- ここまで (対応する行を () で追記してあります。

最後に答えを出力する部分です。
ここから ----------------------
(17)(18)最後に、for answer in solve(BOARD_SIZE): print (answer) という行で、solve(BOARD_SIZE) 関数を呼び出して、8-queens の問題のすべての解を求めています。そして、for ループでそれらの解を表示しています。

このプログラムは、再帰的な関数とリスト内包表記というPython の特徴的な機能を使って、簡潔に書かれています。しかし、初心者にとっては難しいかもしれません。もっと詳しく説明が必要な場合は、教えてください。
---------------------- ここまで (対応する行を () で追記してあります。

もっともらしく解説文を作ってくれました。便利ですね。

このプログラムから、Python は再帰呼び出しができる言語ということが分かりました。

(4)行目の　reversed() は組み込み関数で、引数を逆順に取り出すイテレータを返すもののようです。

>>> b
[(1, 2), (3, 4), (5, 6), (7, 8)]
>>> reversed(b)
<list_reverseiterator object at 0xf798f730>
>>>
>>> for i,j in reversed(b):
...        print(i,j)
...
7 8
5 6
3 4
1 2
>>>

(6)行目の　if 文の中の in は、
in の後ろのタプルの中に含まれるかどうかの判定に使うのですね。ここは、Copilot に聞いてみました。

ここから ----------------------
`in` は、リストや辞書の中に特定の値が含まれているかどうかを判定するために使います。
(途中省略）
要するに、`in` は特定の値がコンテナ（リストや辞書など）に含まれているかどうかを確認するのに便利なキーワードです。
---------------------- ここまで

タプルが使えるかどうかを確認すると、

ここから ----------------------
はい、`if` 文の中で `in`を使う際に、リストの代わりにタプルを使用することもできます。
タプルはリストと似ていますが、要素を変更できない不変のコレクションです。
---------------------- ここまで

Python のプログラムで分からない所の確認に生成AIは有効ですね。例も出てくるので実際に試せますから。
ためしてみると、次のようになりました。

>> print(a)
(1, 2, 3)
>>> print(b)
(4, 5, 6)
>>> print(c)
2
>>> if c in a:
...        print('True')
...    else:
...        print('False')
...
True
>>> if c in b:
...        print('True')
...    else:
...        print('False')
...
False
>>>
タプルでなくてリストでも大丈夫です。

>>> a = [1, 2, 3]
>>> if c in a:
...        print('True')
...    else:
...        print('False')
...
True
>>>

これは、よく使われそうです。

ここで、気になったのが
(3)行目のいわゆる連鎖代入
(5)行目のいっぺんに2つの変数に代入できる？表記と、
(13)～(15) の return にある、「リスト内包表記」です。

長くなったので、次回はこれに付いて調べて見たいと思います。