Scala Programming

パズルの解法 (3)

今回は基本的な探索手法である幅優先探索 (breadth-first search) と反復深化 (iterative deeping) を使って 15 パズルで有名なスライドパズルを解いてみましょう。

●8 パズルの説明

参考文献 1 によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。

      図 : 15 パズル

15 パズルは上図に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。

15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 8 までの数字を並べる「8 パズル」を考えることにします。

              図 : 8 パズル

15 パズルは 4 行 4 列の盤ですが、8 パズルは 3 行 3 列と盤を小さくしたパズルです。8 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、9! = 362880 通りあります。15 パズルや 8 パズルの場合、参考文献 2 によると 『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にしか移行できない』 とのことです。

上図 (2) は 7 と 8 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。このような性質を「偶奇性 (パリティ)」といいます。詳しい説明は拙作のページ Puzzle DE Programming 偶奇性 (パリティ) のお話 をお読みください。8 パズルの場合、完成形に到達する局面の総数は 9! / 2 = 181440 個となります。

●幅優先探索による解法

それでは、プログラムを作りましょう。下図に示すスタートから完成形 (ゴール) に到達するまでの最短手数を幅優先探索で求めます。

            図 : 8 パズル

8 パズルの盤面は配列 (ArrayBuffer) を使って表します。盤面の位置と配列の添字の対応は下図を見てください。

           図 : 8 パズルの盤面

隣接リストの定義は次のようになります。

リスト : 隣接リスト

  val adjacent = Array(
    List(1, 3),       // 0
    List(0, 2, 4),    // 1
    List(1, 5),       // 2
    List(0, 4, 6),    // 3
    List(1, 3, 5, 7), // 4
    List(2, 4, 8),    // 5
    List(3, 7),       // 6
    List(4, 6, 8),    // 7
    List(5, 7))       // 8

次は局面を表すクラスを定義します。

リスト : 局面の定義

  type Board = ArrayBuffer[Int]

  case class State(board: Board, space: Int, prev: State)

クラス名は State としました。board は盤面を表す配列で、型は ArrayBuffer[Int] になります。type で別名 Board を付けています。Array を使わないのは、演算子 == で等値の判定ができないからです。ArrayBuffer は演算子 == で等値を判定することができます。space は空き場所の位置、prev は 1 手前の局面 (State のオブジェクト) を格納します。ゴールに到達したら、prev をたどって手順を表示します。

それでは幅優先探索のプログラムを作りましょう。次のリストを見てください。

リスト : 幅優先探索

  def solver(start: Board, goal: Board): Unit = {
    val q = new Queue[State]
    val s = MSet[Board]()
    q.enqueue(State(start, start.indexOf(0), null))
    s += start
    while (!q.isEmpty) {
      val st = q.dequeue()
      for (x <- adjacent(st.space)) {
        val newBd = st.board.clone
        newBd(st.space) = newBd(x)
        newBd(x) = 0
        if (!s(newBd)) {
          val newSt = State(newBd, x, st)
          if (newBd == goal) {
            printAnswer(newSt)
            return
          }
          q.enqueue(newSt)
          s += newBd
        }
      }
    }
  }

  // 手順の表示
  def printAnswer(st: State): Unit = {
    if (st != null) {
      printAnswer(st.prev)
      println(st.board)
    }
  }

プログラムの骨格は 経路の探索 で説明した幅優先探索と同じです。今回は scala.collection.mutable の Queue を import します。使い方は拙作ページ 多相クラス で作成した mutable なキューとほとんど同じです。solver の引数 start はスタートの盤面を、goal はゴールの盤面を表します。スタートの局面を State() で生成し、メソッド enqueue でキューに登録します。

変数 s は同一局面をチェックするためのセットを格納します。幅優先探索の場合、手数 を 1 つずつ増やしながら探索を行います。このため、n 手目の移動で作られた局面が n 手以前の局面で出現している場合、n 手より短い手数で到達する移動手順が必ず存在します。最短手順を求めるのであれば、この n 手の手順を探索する必要はありません。セットをチェックして新しい局面だけキューに登録します。

次の while ループで、ゴール (GOAL) に到達するまで探索を繰り返します。キューが空になり while ループが終了する場合、start は GOAL に到達できない、つまり解くことができなかったことになります。キューから局面を取り出して変数 st にセットします。それから、駒を動かして新しい局面を生成します。盤面は元の局面 st.board をメソッド clone で複製して変数 newBd にセットします。動かせる駒の位置は空き場所の隣なので、adjacent(a.space) で求めることができます。あとは、newBd[st.space] に newBd(x) の駒をセットし、newBd(x) に空き場所を表すデータ 0 を書き込みます。

新しい盤面を作ったら、同一局面がないか s(newBd) でチェックします。同一局面がない場合は、State() で新しい局面を生成して変数 newSt にセットします。このとき、空き場所の位置は x で、1 手前の局面は st になります。そして、newBd が GOAL に到達したら関数 printAnswer で手順を表示して処理を終了します。そうでなければ、局面 newSt をキューに登録して、セットに newBd を追加します。

関数 printAnswer は簡単です。局面を表す Board を println でそのまま出力します。st.prev を順番にたどって出力すると、手順は逆順に表示されてしまいます。そこで、再帰呼び出しを使って最初の状態に戻り、そこから局面を順番に出力させます。

●実行結果

これでプログラムは完成です。それでは実行してみましょう。

$ scalac eight.scala
$ scala eight
ArrayBuffer(8, 6, 7, 2, 5, 4, 3, 0, 1)
ArrayBuffer(8, 6, 7, 2, 0, 4, 3, 5, 1)
ArrayBuffer(8, 0, 7, 2, 6, 4, 3, 5, 1)
ArrayBuffer(0, 8, 7, 2, 6, 4, 3, 5, 1)
ArrayBuffer(2, 8, 7, 0, 6, 4, 3, 5, 1)
ArrayBuffer(2, 8, 7, 3, 6, 4, 0, 5, 1)
ArrayBuffer(2, 8, 7, 3, 6, 4, 5, 0, 1)
ArrayBuffer(2, 8, 7, 3, 6, 4, 5, 1, 0)
ArrayBuffer(2, 8, 7, 3, 6, 0, 5, 1, 4)
ArrayBuffer(2, 8, 0, 3, 6, 7, 5, 1, 4)
ArrayBuffer(2, 0, 8, 3, 6, 7, 5, 1, 4)
ArrayBuffer(2, 6, 8, 3, 0, 7, 5, 1, 4)
ArrayBuffer(2, 6, 8, 0, 3, 7, 5, 1, 4)
ArrayBuffer(2, 6, 8, 5, 3, 7, 0, 1, 4)
ArrayBuffer(2, 6, 8, 5, 3, 7, 1, 0, 4)
ArrayBuffer(2, 6, 8, 5, 3, 7, 1, 4, 0)
ArrayBuffer(2, 6, 8, 5, 3, 0, 1, 4, 7)
ArrayBuffer(2, 6, 0, 5, 3, 8, 1, 4, 7)
ArrayBuffer(2, 0, 6, 5, 3, 8, 1, 4, 7)
ArrayBuffer(2, 3, 6, 5, 0, 8, 1, 4, 7)
ArrayBuffer(2, 3, 6, 0, 5, 8, 1, 4, 7)
ArrayBuffer(2, 3, 6, 1, 5, 8, 0, 4, 7)
ArrayBuffer(2, 3, 6, 1, 5, 8, 4, 0, 7)
ArrayBuffer(2, 3, 6, 1, 5, 8, 4, 7, 0)
ArrayBuffer(2, 3, 6, 1, 5, 0, 4, 7, 8)
ArrayBuffer(2, 3, 0, 1, 5, 6, 4, 7, 8)
ArrayBuffer(2, 0, 3, 1, 5, 6, 4, 7, 8)
ArrayBuffer(0, 2, 3, 1, 5, 6, 4, 7, 8)
ArrayBuffer(1, 2, 3, 0, 5, 6, 4, 7, 8)
ArrayBuffer(1, 2, 3, 4, 5, 6, 0, 7, 8)
ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 0, 8)
ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 0)
636 msec

31 手で解くことができました。生成した局面は全部で 181440 通りで、実行時間は 0.64 秒 (Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz) かかりました。8 パズルの場合、最長手数は 31 手で、下図に示す 2 通りの局面があります。スタートの局面はその一つです。

      図 : 31 手で解ける局面

最長手数の局面は、幅優先探索を使って求めることができます。これはあとで試してみましょう。

●双方向探索

ところで、今回の 8 パズルようにゴールの状態が明確な場合、スタートから探索するだけではなくゴールからも探索を行うことで、幅優先探索を高速化することができます。これを「双方向探索 (bi-directional search)」といいます。

その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。

これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。

生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の探索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。

それではプログラムを作りましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な修正が必要になります。ここは、探索方向を示すフラグを用意することで、一つのキューだけで処理することにしましょう。局面を表すクラスに方向を格納するフィールド変数 dir を追加します。

リスト : 局面の定義 (双方向からの探索)

  // 方向を表す定数
  val Fore = 1
  val Back = 0

  case class State(board: Board, space: Int, prev: State, dir: Int)

スタートからの探索を Fore で、ゴールからの探索を Back で表ます。双方向探索のプログラムは次のようになります。

リスト : 双方向探索

  def solver(start: Board, goal: Board): Unit = {
    val q = new Queue[State]
    val st1 = State(start, start.indexOf(0), null, Fore)
    val st2 = State(goal,  goal.indexOf(0),  null, Back)
    val m = MMap(start -> st1, goal -> st2)
    q.enqueue(st1, st2)
    while (!q.isEmpty) {
      val st = q.dequeue()
      for (x <- adjacent(st.space)) {
        val newBd = st.board.clone
        newBd(st.space) = newBd(x)
        newBd(x) = 0
        val newSt = State(newBd, x, st, st.dir)
        m.get(newBd) match {
          case None => { q.enqueue(newSt); m += (newBd -> newSt) }
          case Some(oldSt) => 
            if (oldSt.dir != newSt.dir) {
              printAnswer(oldSt, st)
              return
            }
        }
      }
    }
  }

スタートとゴールの局面を生成してキューにセットします。スタートの局面は Fore をセットし、ゴールの局面は Back をセットします。最初に、スタートの状態から 1 手目の局面が生成され、次にゴールの状態から 1 手目の局面が生成されます。あとは、交互に探索が行われます。それから、同一局面を見つけたとき、その局面の方向 dir を比較する必要があるので、セットではなくマップを使います。キーは Board で値が State になります。

駒の移動と局面の生成処理は幅優先探索と同じです。m.get(newBd) で同一局面を探索します。見つけた場合、局面は変数 oldSt にセットされます。そして、newSt.dir と oldSt.dir を比較して探索方向が異なっていれば、双方向の探索で同一局面に到達したことがわかります。見つけた最短手順を関数 printAnswer で出力します。同じ探索方向であれば、キューへの追加は行いません。

printAnswer は簡単なプログラムなので説明は割愛いたします。詳細は プログラムリスト２ をお読みください。

さっそく実行してみると、実行時間は 0.14 秒になりました。双方向探索の効果は十分に出ていると思います。

●最長手数の求め方

今度は最長手数の局面を求めてみましょう。最長手数の求め方ですが、181440 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかし、この方法では時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。

まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。

このプログラムの目的は、いちばん長い手数となる配置を求めることなので、その手順を表示することは行いません。このため、一つ前の局面を格納するフィールド変数 prev は削除します。そのかわり、その局面までの手数を格納するフィールド変数 move を用意します。一つ前の局面の手数を move から求め、それに 1 を足せば現在の局面の手数となります。

●プログラムの作成

それではプログラムを作ります。次のリストを見てください。

リスト : 8 パズルの最長手数を求める

  // 局面の定義
  case class State(board: Board, space: Int, move: Int)

  def solver(start: Board): Unit = {
    var buff1 = ArrayBuffer(State(start, start.indexOf(0), 0))
    val s = MSet[Board]()
    s += start
    while (true) {
      val buff2 = ArrayBuffer[State]()
      for (st <- buff1) {
        for (x <- adjacent(st.space)) {
          val newBd = st.board.clone
          newBd(st.space) = newBd(x)
          newBd(x) = 0
          if (!s(newBd)) {
            buff2 += State(newBd, x, st.move + 1)
            s += newBd
          }
        }
      }
      if (buff2.isEmpty){
        for (st <- buff1) println(st)
        return
      }
      buff1 = buff2
    }
  }

関数 solver には GOAL をチェックする処理がないことに注意してください。今回はキューを使わないで、buff1 に格納されている局面から新しい局面を生成して、同一局面がなければそれを buff2 に格納することにします。buff2 が空であれば、新しい局面が生成されなかったので、buff1 に格納されている局面が最小手数の局面となります。あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト３ をお読みください。

さっそく実行してみましょう。

$ scalac eightmax.scala
$ scala eightmax
State(ArrayBuffer(6, 4, 7, 8, 5, 0, 3, 2, 1),5,31)
State(ArrayBuffer(8, 6, 7, 2, 5, 4, 3, 0, 1),7,31)
629 msec

最長手数は 31 手で、その配置は全部で 2 通りになります。実行時間は 0.63 秒になりました。

●反復深化による解法

次は反復深化で 8 パズルを解いてみましょう。拙作のページ 経路の探索 で説明したように、反復深化は最短手数を求めることができるアルゴリズムです。幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。

ただし、同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。実行時間が長くなるといっても、枝刈りを工夫することでパズルを高速に解くことができます。メモリ不足になる場合には、積極的に使ってみたいアルゴリズムといえるでしょう。

幅優先探索では全ての局面を保存しましたが、反復深化ではその必要はありません。盤面は ArrayBuffer で表し、変数 board に格納します。駒の移動は board を書き換えて、バックトラックする時は元に戻すことにします。動かした駒はリスト move に格納します。動かした駒がわかれば局面を再現できるので、それで移動手順を表すことにしましょう。

●手数の偶奇性

8 パズルや 15 パズルの場合、スタートの空き場所の位置とゴールの空き場所の位置から、解の手数が偶数になるのか奇数になるのか簡単に判定することができます。この場合、探索の上限値を 1 手ずつではなく 2 手ずつ増やすことができます。これで実行時間を大幅に短縮することができます。

判定は簡単です。次の図を見てください。

            図 : 手数の偶奇性

盤面を市松模様に塗り分けます。上図のパリティでは 0 と 1 で表しています。スタートからゴールに到達するまで、空き場所はいろいろな位置に移動しますが、同じパリティの位置に移動する場合は偶数回かかり、異なるパリティの位置に移動する場合は奇数回かかります。

たとえば、スタートで駒 5 を 1 回動かすと、空き場所は上の位置に移動します。この場合、移動回数は奇数でパリティの値は 0 から 1 に変わります。スタートから駒 5 と 6 を動かすと、移動回数は偶数でパリティの値は 0 のままです。このように、同じパリティの位置に移動する場合は偶数回、異なるパリティの位置に移動する場合は奇数回となります。上図のスタートとゴールの場合、空き場所のパリティが異なるので、奇数回かかることがわかります。

●プログラムの作成

それでは、探索を行う関数 dfs を作ります。次のリストを見てください。

リスト : 単純な反復深化による解法

  val parity = Array(1, 0, 1, 0, 1, 0, 1, 0, 1)

  val board = ArrayBuffer(8, 6, 7, 2, 5, 4, 3, 0, 1)
  val goal  = ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 0)
  var count = 0

  def dfs(n: Int, limit: Int, space: Int, move: List[Int]): Unit = {
    if (n == limit) {
      if (board == goal) {
        count += 1
        println(move.reverse.tail)
      }
    } else {
      for (x <- adjacent(space)) {
        val p = board(x)
        if (move.head != p) {
          board(space) = p
          board(x) = 0
          dfs(n + 1, limit, x, p::move)
          board(x) = p
          board(space) = 0
        }
      }
    }
  }

関数 dfs の引数 n が手数、limit が上限値、space が空き場所の位置、move が移動手順を表すリストです。手数が上限値に達したら、パズルが解けたかチェックします。goal は完成形を表す配列です。完成形に到達したら、解の総数をカウントする変数 count をインクリメントし、println で手順を表示します。上限値に達していない場合は、駒を移動して新しい局面を作ります。

8 パズルのように、元の局面に戻すことが可能 (可逆的) なパズルの場合、単純な深さ優先探索では同じ移動手順を何度も繰り返すことがあります。そうなると、とんでもない解を出力するだけではなく、再帰呼び出しが深くなるとスタックがオーバーフローしてプログラムの実行が停止してしまいます。

このような場合、局面の履歴を保存しておいて同じ局面がないかチェックすることで、解を求めることができるようになります。ただし、同一局面をチェックする分だけ時間が余分にかかりますし、最初に見つかる解が最短手数とは限りません。

反復深化では深さが制限されているため、同一局面のチェックを行わなくてもスタックオーバーフローが発生することはありません。そのかわり、無駄な探索はどうしても避けることができません。8 パズルの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ってしまいます。完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。

プログラムでは、リスト move に移動した駒を格納しているので、1 手前と同じ駒は動かさないようにチェックしています。なお、move の末尾はダミーデータで 0 になります。手順を表示するときは move を reverse で反転して、tail でダミーデータを削除しています。

次は、関数 dfs を呼び出すプログラムを作ります。

リスト : 反復深化の実行

  def idSearch(): Unit = {
    val s1 = board.indexOf(0)
    val s2 = goal.indexOf(0)
    val limit = if (parity(s1) != parity(s2)) 1 else 2
    for (i <- limit to 31 by 2) {
      println("-----" + i + "-----")
      dfs(0, i, board.indexOf(0), List(0))
      if (count > 0) return
    }
  }

最初にパリティをチェックして、start と goal が異なるパリティであれば、上限値の初期値 limit を 1 に、同じパリティであれば 2 にセットします。for ループの変数 i が上限値を表します。i を 2 手ずつ増やして関数 dfs を呼び出します。変数 count が 0 より大きくなれば解が見つかったのでループを脱出します。プログラムはこれで完成です。

実際に実行してみると、当然ですが最短手数は 31 手で 40 通りの手順が表示されました。実行時間は約 11.1 秒かかりました。反復深化の場合、枝刈りを工夫しないと高速に解くことはできません。そこで、反復深化の常套手段である「下限値枝刈り法」を使うことにしましょう。

●下限値枝刈り法

下限値枝刈り法は難しいアルゴリズムではありません。たとえば、5 手進めた局面を考えてみます。探索の上限値が 10 手とすると、あと 5 手だけ動かすことができますね。この時、パズルを解くのに 6 手以上かかることがわかれば、ここで探索を打ち切ることができます。このように、必要となる最低限の手数が明確にわかる場合、この値を「下限値 (Lower Bound)」と呼びます。この下限値を求めることができれば、「今の移動手数＋下限値」が探索手数を超えた時点で、枝刈りすることが可能になります。これが下限値枝刈り法の基本的な考え方です。

さて、下限値を求める方法ですが、これにはいろいろな方法が考えられます。今回は、各駒が正しい位置へ移動するまでの手数 (移動距離) ^[*1] を下限値として利用することにしましょう。次の図を見てください。

            図 : 下限値の求め方

たとえば、右下にある 1 の駒を左上の正しい位置に移動するには、最低でも 4 手必要です。もちろん、ほかの駒との関連で、それ以上の手数が必要になる場合もあるでしょうが、4 手より少なくなることは絶対にありません。同じように、各駒について最低限必要な手数を求めることができます。そして、その合計値はパズルを解くのに最低限必要な手数となります。これを下限値として利用することができます。ちなみに、上図 (2) の初期状態の下限値は 21 手になります。

下限値枝刈り法を使う場合、下限値の計算を間違えると正しい解を求めることができなくなります。たとえば、10 手で解ける問題の下限値を 11 手と計算すれば、最短手数を求めることができなくなります。それどころか、10 手の解しかない場合は、答えを求めることすらできなくなります。下限値の計算には十分に注意してください。

●下限値枝刈り法のプログラム

それでは、プログラムを作りましょう。下限値の求め方ですが、駒を動かすたびに各駒の移動距離を計算していたのでは時間がかかります。8 パズルの場合、1 回に一つの駒しか移動しないので、初期状態の下限値を求めておいて、動かした駒の差分だけ計算すればいいでしょう。また、駒の移動距離はいちいち計算するのではなく、あらかじめ計算した結果を配列に格納しておきます。この配列を distance とすると、盤面から移動距離を求めるプログラムは次のようになります。

リスト : 移動距離を求める

  // マンハッタン距離
  val distance = Array(
    Array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    Array(0, 1, 2, 1, 2, 3, 2, 3, 4),
    Array(1, 0, 1, 2, 1, 2, 3, 2, 3),
    Array(2, 1, 0, 3, 2, 1, 4, 3, 2),
    Array(1, 2, 3, 0, 1, 2, 1, 2, 3),
    Array(2, 1, 2, 1, 0, 1, 2, 1, 2),
    Array(3, 2, 1, 2, 1, 0, 3, 2, 1),
    Array(2, 3, 4, 1, 2, 3, 0, 1, 2),
    Array(3, 2, 3, 2, 1, 2, 1, 0, 1))

  // 移動距離を求める
  def getDistance(): Int = {
    var v = 0
    for (x <- 0 until board.size) {
      val p = board(x)
      if (p != 0) {
        v += distance(p)(x)
      }
    }
    v
  }

distance は 2 次元配列で「駒の種類×駒の位置」を表しています。空き場所は関係ないので、distance(0) はダミーとなります。関数 getDistance は盤面 board にある駒と位置から移動距離を求めます。変数 v を 0 に初期化して、空き場所 (0) 以外の駒の移動距離を distance から求めて v に足し算するだけです。

次は、下限値枝刈り法による反復深化を行う関数 dfs を作ります。次のリストを見てください。

リスト : 下限値枝刈り法

  def dfs(n: Int, limit: Int, low: Int, space: Int, move: List[Int]): Unit = {
    if (n + low > limit) return
    if (n == limit) {
      if (board == goal) {
        count += 1
        println(move.reverse.tail)
      }
    } else {
      for (x <- adjacent(space)) {
        val p = board(x)
        if (move.head != p) {
          board(space) = p
          board(x) = 0
          dfs(n + 1,
              limit, 
              low - distance(p)(x) + distance(p)(space),
              x,
              p::move)
          board(x) = p
          board(space) = 0
        }
      }
    }
  }

dfs の引数 low は現在の盤面 board の下限値を表しています。n + lower が上限値 limit を超えたら枝刈りを行います。return で探索を打ち切るだけです。limit 以下の場合は今までの処理とほぼ同じですが、駒を動かしたときに差分を計算して、新しい下限値を求める処理を追加します。追加する処理はこれだけです。とても簡単ですね。

最後に idSearch を修正します。次のリストを見てください。

リスト : 反復深化の実行

  def idSearch(): Unit = {
    val s1 = board.indexOf(0)
    val s2 = goal.indexOf(0)
    val low = getDistance()
    val limit = if (parity(s1) != parity(s2)) {
                  if (low % 2 == 0) low + 1 else low
                } else {
                  if (low % 2 == 0) low else low + 1
                }
    for (i <- limit to 31 by 2) {
      println("-----" + i + "-----")
      dfs(0, i, low, board.indexOf(0), List(0))
      if (count > 0) return
    }
  }

関数 getDistance で初期状態の下限値 low を求めます。次にパリティをチェックして、上限値の初期値 limit を求めます。下限値がわかるのですから、上限値 i は 1 手からではなく limit からスタートします。あとは dfs に下限値 low を渡して呼び出すだけです。

プログラムの主な修正はこれだけです。実際に実行してみると、実行時間は 0.10 秒になりました。約 111 倍という高速化に驚いてしまいました。下限値枝刈り法の効果は極めて高いですね。

●参考文献

1. 井上うさぎ, 『世界のパズル百科イラストパズルワンダーランド』, 東京堂出版, 1997
2. 三木太郎, 『特集コンピュータパズルへの招待 スライディングブロック編』, C MAGAZINE 1996 年 2 月号, ソフトバンク
3. 高橋謙一郎, 『特集 悩めるプログラマに効くアルゴリズム』, C MAGAZINE 2000 年 11 月号, ソフトバンク

●プログラムリスト１

//
// eight.scala : 8 パズル (幅優先探索)
//
//               Copyright (C) 2014-2021 MakotoHiroi
//
import scala.collection.mutable.{Set => MSet, ArrayBuffer, Queue}

object eight {
  // 隣接リスト
  val adjacent = Array(
    List(1, 3),       // 0
    List(0, 2, 4),    // 1
    List(1, 5),       // 2
    List(0, 4, 6),    // 3
    List(1, 3, 5, 7), // 4
    List(2, 4, 8),    // 5
    List(3, 7),       // 6
    List(4, 6, 8),    // 7
    List(5, 7))       // 8

  type Board = ArrayBuffer[Int]

  case class State(board: Board, space: Int, prev: State)

  def printAnswer(st: State): Unit = {
    if (st != null) {
      printAnswer(st.prev)
      println(st.board)
    }
  }

  // 幅優先探索
  def solver(start: Board, goal: Board): Unit = {
    val q = new Queue[State]
    val s = MSet[Board]()
    q.enqueue(State(start, start.indexOf(0), null))
    s += start
    while (!q.isEmpty) {
      val st = q.dequeue()
      for (x <- adjacent(st.space)) {
        val newBd = st.board.clone
        newBd(st.space) = newBd(x)
        newBd(x) = 0
        if (!s(newBd)) {
          val newSt = State(newBd, x, st)
          if (newBd == goal) {
            printAnswer(newSt)
            return
          }
          q.enqueue(newSt)
          s += newBd
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {
    val s = System.currentTimeMillis
    solver(ArrayBuffer(8,6,7,2,5,4,3,0,1), ArrayBuffer(1,2,3,4,5,6,7,8,0))
    println(s"{System.currentTimeMillis - s} msec")
  }
}

●プログラムリスト２

//
// eightbi.scala : 8 パズル (双方向探索)
//
//                 Copyright (C) 2014-2021 MakotoHiroi
//

import scala.collection.mutable.{Map => MMap, ArrayBuffer, Queue}

object eightbi {
  // 隣接リスト
  val adjacent = Array(
    List(1, 3),       // 0
    List(0, 2, 4),    // 1
    List(1, 5),       // 2
    List(0, 4, 6),    // 3
    List(1, 3, 5, 7), // 4
    List(2, 4, 8),    // 5
    List(3, 7),       // 6
    List(4, 6, 8),    // 7
    List(5, 7))       // 8

  type Board = ArrayBuffer[Int]

  case class State(board: Board, space: Int, prev: State, dir: Int)

  val Fore = 1
  val Back = 0

  def printAnsFore(st: State): Unit = {
    if (st != null) {
      printAnsFore(st.prev)
      println(st.board)
    }
  }

  def printAnsBack(st: State): Unit = {
    if (st != null) {
      println(st.board)
      printAnsBack(st.prev)
    }
  }

  def printAnswer(st1: State, st2: State): Unit = {
    if (st1.dir == Fore) {
      printAnsFore(st1)
      printAnsBack(st2)
    } else {
      printAnsFore(st2)
      printAnsBack(st1)
    }
  }

  // 双方向探索
  def solver(start: Board, goal: Board): Unit = {
    val q = new Queue[State]
    val st1 = State(start, start.indexOf(0), null, Fore)
    val st2 = State(goal,  goal.indexOf(0),  null, Back)
    val m = MMap(start -> st1, goal -> st2)
    q.enqueue(st1, st2)
    while (!q.isEmpty) {
      val st = q.dequeue()
      for (x <- adjacent(st.space)) {
        val newBd = st.board.clone
        newBd(st.space) = newBd(x)
        newBd(x) = 0
        val newSt = State(newBd, x, st, st.dir)
        m.get(newBd) match {
          case None => { q.enqueue(newSt); m += (newBd -> newSt) }
          case Some(oldSt) => 
            if (oldSt.dir != newSt.dir) {
              printAnswer(oldSt, st)
              return
            }
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {
    val s = System.currentTimeMillis
    solver(ArrayBuffer(8,6,7,2,5,4,3,0,1), ArrayBuffer(1,2,3,4,5,6,7,8,0))
    println(s"${System.currentTimeMillis - s} msec")
  }
}

●プログラムリスト３

//
// eightmax.scala : 8 パズル (最長手数の局面を求める)
//
//                  Copyright (C) 2014-2021 MakotoHiroi
//
import scala.collection.mutable.{Set => MSet, ArrayBuffer}

object eightmax {
  // 隣接リスト
  val adjacent = Array(
    List(1, 3),       // 0
    List(0, 2, 4),    // 1
    List(1, 5),       // 2
    List(0, 4, 6),    // 3
    List(1, 3, 5, 7), // 4
    List(2, 4, 8),    // 5
    List(3, 7),       // 6
    List(4, 6, 8),    // 7
    List(5, 7))       // 8

  type Board = ArrayBuffer[Int]

  case class State(board: Board, space: Int, move: Int)

  // 最長手数の局面を求める
  def solver(start: Board): Unit = {
    var buff1 = ArrayBuffer(State(start, start.indexOf(0), 0))
    val s = MSet[Board]()
    s += start
    while (true) {
      val buff2 = ArrayBuffer[State]()
      for (st <- buff1) {
        for (x <- adjacent(st.space)) {
          val newBd = st.board.clone
          newBd(st.space) = newBd(x)
          newBd(x) = 0
          if (!s(newBd)) {
            buff2 += State(newBd, x, st.move + 1)
            s += newBd
          }
        }
      }
      if (buff2.isEmpty){
        for (st <- buff1) println(st)
        return
      }
      buff1 = buff2
    }
  }

  def main(args: Array[String]): Unit = {
    val s = System.currentTimeMillis
    solver(ArrayBuffer(1,2,3,4,5,6,7,8,0))
    println(s"${System.currentTimeMillis - s} msec")
  }
}

●プログラムリスト４

//
// eightid.scala : 8 パズル (反復深化)
//
//                 Copyright (C) 2014-2021 MakotoHiroi
//
import scala.collection.mutable.{ArrayBuffer}

object eightid {
  // 隣接リスト
  val adjacent = Array(
    List(1, 3),       // 0
    List(0, 2, 4),    // 1
    List(1, 5),       // 2
    List(0, 4, 6),    // 3
    List(1, 3, 5, 7), // 4
    List(2, 4, 8),    // 5
    List(3, 7),       // 6
    List(4, 6, 8),    // 7
    List(5, 7))       // 8

  val parity = Array(1, 0, 1, 0, 1, 0, 1, 0, 1)

  val board = ArrayBuffer(8, 6, 7, 2, 5, 4, 3, 0, 1)
  val goal  = ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 0)
  var count = 0

  // 反復深化
  def dfs(n: Int, limit: Int, space: Int, move: List[Int]): Unit = {
    if (n == limit) {
      if (board == goal) {
        count += 1
        println(move.reverse.tail)
      }
    } else {
      for (x <- adjacent(space)) {
        val p = board(x)
        if (move.head != p) {
          board(space) = p
          board(x) = 0
          dfs(n + 1, limit, x, p::move)
          board(x) = p
          board(space) = 0
        }
      }
    }
  }

  // 反復深化の実行
  def idSearch(): Unit = {
    val s1 = board.indexOf(0)
    val s2 = goal.indexOf(0)
    val limit = if (parity(s1) != parity(s2)) 1 else 2
    for (i <- limit to 31 by 2) {
      println("-----" + i + "-----")
      dfs(0, i, board.indexOf(0), List(0))
      if (count > 0) return
    }
  }

  def main(args: Array[String]): Unit = {
    val s = System.currentTimeMillis
    idSearch()
    println(count)
    println(s"${System.currentTimeMillis - s} msec")
  }
}

●プログラムリスト５

//
// eightlow.scala : 8 パズル (反復深化＋下限値枝刈り法)
//
//                  Copyright (C) 2014-2021 MakotoHiroi
//
import scala.collection.mutable.{ArrayBuffer}

object eightlow {
  // 隣接リスト
  val adjacent = Array(
    List(1, 3),       // 0
    List(0, 2, 4),    // 1
    List(1, 5),       // 2
    List(0, 4, 6),    // 3
    List(1, 3, 5, 7), // 4
    List(2, 4, 8),    // 5
    List(3, 7),       // 6
    List(4, 6, 8),    // 7
    List(5, 7))       // 8

  // マンハッタン距離
  val distance = Array(
    Array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    Array(0, 1, 2, 1, 2, 3, 2, 3, 4),
    Array(1, 0, 1, 2, 1, 2, 3, 2, 3),
    Array(2, 1, 0, 3, 2, 1, 4, 3, 2),
    Array(1, 2, 3, 0, 1, 2, 1, 2, 3),
    Array(2, 1, 2, 1, 0, 1, 2, 1, 2),
    Array(3, 2, 1, 2, 1, 0, 3, 2, 1),
    Array(2, 3, 4, 1, 2, 3, 0, 1, 2),
    Array(3, 2, 3, 2, 1, 2, 1, 0, 1))

  val parity = Array(1, 0, 1, 0, 1, 0, 1, 0, 1)

  val board = ArrayBuffer(8, 6, 7, 2, 5, 4, 3, 0, 1)
  val goal  = ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 0)
  var count = 0

  // 移動距離を求める
  def getDistance(): Int = {
    var v = 0
    for (x <- 0 until board.size) {
      val p = board(x)
      if (p != 0) {
        v += distance(p)(x)
      }
    }
    v
  }

  // 反復深化＋下限値枝刈り法
  def dfs(n: Int, limit: Int, low: Int, space: Int, move: List[Int]): Unit = {
    if (n + low > limit) return
    if (n == limit) {
      if (board == goal) {
        count += 1
        println(move.reverse.tail)
      }
    } else {
      for (x <- adjacent(space)) {
        val p = board(x)
        if (move.head != p) {
          board(space) = p
          board(x) = 0
          dfs(n + 1,
              limit, 
              low - distance(p)(x) + distance(p)(space),
              x,
              p::move)
          board(x) = p
          board(space) = 0
        }
      }
    }
  }

  // 反復深化の実行
  def idSearch(): Unit = {
    val s1 = board.indexOf(0)
    val s2 = goal.indexOf(0)
    val low = getDistance()
    val limit = if (parity(s1) != parity(s2)) {
                  if (low % 2 == 0) low + 1 else low
                } else {
                  if (low % 2 == 0) low else low + 1
                }
    for (i <- limit to 31 by 2) {
      println("-----" + i + "-----")
      dfs(0, i, low, board.indexOf(0), List(0))
      if (count > 0) return
    }
  }

  def main(args: Array[String]): Unit = {
    val s = System.currentTimeMillis
    idSearch()
    println(count)
    println(s"${System.currentTimeMillis - s} msec")
  }
}