コンテンツにスキップ

0350: 例外による探索の打ち切り

問題

バックトラック法による探索では、再帰の深い位置で解が見つかった瞬間に、探索全体を打ち切りたいことがあります。 Python には goto 文がないため、深くネストした制御構造からまとめて抜けるには例外を使います。

Nクイーン問題は、\(n \times n\) の盤面に \(n\) 個のクイーンを、互いに取り合わない（同じ列・斜線上に2個以上並ばない）ように各行へ1個ずつ配置する問題です。

次の2つを実装してください。

  • Exception を継承したユーザ定義例外 Found。見つかった解を属性として運びます。
  • 関数 first_solution(n: int) -> list[int] | None。Nクイーン問題を行ごとの深さ優先探索で解き、最初に見つかった解を返します。解は長さ \(n\) のリストで、i 番目の要素は i 行目のクイーンを置く列番号です。解が存在しない場合は None を返します。

first_solution() は、解が見つかった地点で解を載せた Found を送出し、再帰呼び出しの最上位でそれを捕捉して解を取り出す構造にしてください。

制約

  • n は 1 以上の整数です。
  • 各行では列番号を昇順（0, 1, ..., n-1）に試してください。これにより返り値は辞書式順序で最小の解に定まります。
  • 解の発見は return 値の引き継ぎではなく、例外 Found の送出で呼び出しの最上位まで伝えてください。
  • Found は Exception を継承してください。
  • 解が存在しない場合（例: n = 2, 3）は None を返してください。

例

>>> issubclass(Found, Exception)
True
>>> first_solution(1)
[0]
>>> first_solution(4)
[1, 3, 0, 2]
>>> first_solution(6)
[1, 3, 5, 0, 2, 4]
>>> first_solution(8)
[0, 4, 7, 5, 2, 6, 1, 3]
>>> first_solution(2) is None
True
>>> first_solution(3) is None
True

発展

最初の \(k\) 個の解を辞書式順序で返す関数 solutions(n: int, k: int) -> list[list[int]] を実装してください。 \(k\) 個目の解が見つかった時点で、例外によって探索を打ち切ります。

参考