SimplePrograms で Python を学ぶ その２０

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

の ２０番目のプログラムは、　２８行の２度目の８クイーン問題で、独自の例外（exception）の定義です。

BOARD_SIZE = 8

class BailOut(Exception):
    pass

def validate(queens):
    left = right = col = queens[-1]
    for r in reversed(queens[:-1]):
       left, right = left-1, right+1
       if r in (left, col, right):
          raise BailOut

def add_queen(queens):
    for i in range(BOARD_SIZE):
       test_queens = queens + [i]
       try:
          validate(test_queens)
          if len(test_queens) == BOARD_SIZE:
             return test_queens
          else:
             return add_queen(test_queens)
       except BailOut:
          pass
    raise BailOut

queens = add_queen([])
print (queens)
print ("\n".join(". "*q + "Q " + ". "*(BOARD_SIZE-q-1) for q in queens))

再び、8クイーン問題を扱うプログラムですが、答えは１つだけ表示されます。早速これを prog-28.py というファイルにして実行してみます。

$ python3 prog-28.py
[0, 4, 7, 5, 2, 6, 1, 3]
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
$

最初に、Google Gemini による解説を抜粋します。

ここから========>
### コードの解説

#### 定数と例外
* **BOARD_SIZE:** チェスボードのサイズを定義しています。このプログラムでは、8×8のチェスボードを想定しています。
* **BailOut:** 探索中に矛盾が生じた場合に発生させるカスタム例外です。

#### 関数
* **validate(queens):**
* 引数として、既に配置されたクイーンの列番号のリストを受け取ります。
* 新たに追加しようとしているクイーンと、既に配置されているクイーンが互いに攻撃できるかどうかを検証します。
* 攻撃できる場合は、BailOut例外を発生させます。
* **add_queen(queens):**
* 再帰的な関数で、チェスボードの次の行にクイーンを配置する場所を探索します。
* すべての行にクイーンが配置できたら、その配置のリストを返します。
* 配置できない場合は、BailOut例外を発生させます。

#### メインロジック
* **queens = add_queen([]):**
* 空のリストから始めて、add_queen関数で全てのクイーンを配置します。
* **print(queens):**
* 求められたクイーンの配置（列番号のリスト）を出力します。
* **print("\n".join(". "*q + "Q " + ". "*(BOARD_SIZE-q-1) for q in queens)):**
* 求められたクイーンの配置を、チェスボードの形で視覚的に表示します。"Q"がクイーンを表し、"."が空のマスを表します。

### プログラムの仕組み
1. **add_queen**関数は、チェスボードの最初の行から始めて、各行にクイーンを配置できるかどうかを順に試します。
2. **validate**関数は、新しいクイーンを追加するたびに、そのクイーンが他のクイーンと攻撃できるかどうかを検証します。
3. 攻撃できる場合は、**BailOut**例外が発生し、**add_queen**関数は別の配置を試します。
4. 全ての行にクイーンが配置できたら、その配置が一つ見つかったことになるので、探索を終了します。
5. もし、全ての可能性を試しても有効な配置が見つからなければ、**BailOut**例外が発生し、プログラムはエラーで終了します。

### より詳しく
* **再帰:** このプログラムでは、**add_queen**関数が自分自身を呼び出す再帰的な構造になっています。再帰は、問題をより小さな部分問題に分割し、それらを解決することで全体の問題を解決する手法です。
* **バックトラッキング:** 探索中に矛盾が生じたら、一つ前の状態に戻って別の選択肢を試す手法をバックトラッキングといいます。このプログラムでも、**BailOut**例外が発生した際に、一つ前の状態に戻って探索を続けることで、バックトラッキングが行われています。
ここまで========>

Gemini もこのように、プログラムの概要は教えてくれますね。気になるところを見ていきます。

まず、クラス BailOutの定義が、「カスタム例外」(独自の例外:your own exceptions)ですね。
https://docs.python.org/ja/3/tutorial/controlflow.html#pass-statements

pass 文は何もしません。 pass は、文を書くことが構文上要求されているが、プログラム上何の動作もする必要がない時に使われます:

これは最小のクラスを作るときによく使われる方法です:

ということで、ここで言う「最小のクラス」を定義しているようです。何もしないのが重要ですね。
これは、validate() 関数（基本的には前に出てきた18lines プログラムのunder_attack()関数と同じもの）の中で使われている、raise文
https://docs.python.org/ja/3/reference/simple_stmts.html#the-raise-statement

と関連しており、

raise は最初の式を、例外オブジェクトとして評価します。これは、 BaseException のサブクラスまたはインスタンスでなければなりません。クラスなら、例外インスタンスが必要なとき、クラスを無引数でインスタンス化することで得られます。

例外の 型 は例外インスタンスのクラスで、 値 はインスタンスそのものです。

となって、if 文の条件が真ならば、例外 BailOut が発生するのですね。

その例外を受けるものがないと、普通のエラーみたいになる？ので、validdate()を中で呼び出す、
add_queen()関数の定義の中で ８lines プログラムのように、try ~ except を使って、
この例外を処理するようです。

つまり、validate()で例外BailOutが発生すると except節が実行されて、何もせずにfor文の次の i が代入されて繰り返すようです。validate()で例外が発生しなければ、test_queens の長さが、
８になるまではadd_queen()が再帰的に呼ばれて、
８になったら test_queens を返す
ので、実行例のように最初に見つかった配置を返すのでしょう。

add_queen()の最後の raise 文は念のためのような気がします。これがないと返却値がないことになるので、その判定が必要になるからだと思います。というわけで、適当に簡略化すると、

class カスタム例外：
    ....

def func_test(....):
    for
       ...
       try:
          　　...
       except カスタム例外：
          　　...
    raise カスタム例外

となるのが、入門者が覚えた方が良い形でしょうか。

最後は、add_queen()で生成された解 queens を出力して、それを使ってジェネレータ式でチェス盤を出力するのですね。 改行文字を頭に付けるのが面白いですね。

join()の使い方をみるために少し試してみました。分かりやすくするために改行文字を"++"にしました。
まず、ジェネレータ式ではない場合です。

>>> q = 3
>>> print("++".join(". "*q + "Q " + ". "*(8-q-1)))
.++ ++.++ ++.++ ++Q++ ++.++ ++.++ ++.++ ++.++

join()の中の文字列「１文字ずつ」に"++"を付加するのですね。つまり単純化すると、

>>> print("++".join("ABCDE"))
A++B++C++D++E
>>>

です。

これをプログラムのようにジェネレータ式にすると、

>>> queens = [2,3,4,6]
>>> print("++".join(". "*q + "Q " + ". "*(8-q-1) for q in queens))
. . Q . . . . . ++. . . Q . . . . ++. . . . Q . . . ++. . . . . . Q .
>>>

join()の使い方と共に、この事例は覚えておいて損はなさそうです。