今回は幅優先探索の例題として、15 パズルで有名な「スライドパズル (スライディングブロックパズル)」を解いてみましょう。
参考文献 1 『世界のパズル百科イラストパズルワンダーランド』によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。
┌─┬─┬─┬─┐ │１│２│３│４│ ├─┼─┼─┼─┤ │５│６│７│８│ ├─┼─┼─┼─┤ │９│10│11│12│ ├─┼─┼─┼─┤ │13│14│15│ │ └─┴─┴─┴─┘ 図 : 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 パズルの盤面はベクタを使って表します。盤面の位置とベクタの添字の対応は下図を見てください。
┌─┬─┬─┐ ┌─┬─┬─┐
│１│２│３│ │０│１│２│
├─┼─┼─┤ ├─┼─┼─┤
│４│５│６│ │３│４│５│
├─┼─┼─┤ ├─┼─┼─┤
│７│８│ │ │６│７│８│
└─┴─┴─┘ └─┴─┴─┘
盤面: [1 2 3 盤面と配列の対応
4 5 6
7 8 0]
図 : 8 パズルの盤面
隣接リストの定義は次のようになります。
リスト : 隣接リスト (def adjacent [[1 3] ; 0 [0 2 4] ; 1 [1 5] ; 2 [0 4 6] ; 3 [1 3 5 7] ; 4 [2 4 8] ; 5 [3 7] ; 6 [4 6 8] ; 7 [5 7]]) ; 8
局面はリスト (board space prev) で表します。board は盤面を表すベクタ、space は空き場所の位置、prev は 1 手前の局面を格納します。ゴールに到達したら、prev をたどって手順を表示します。
次は駒を動かす関数 move-piece を作ります。
リスト : 駒の移動 (defn move-piece [board x space] (assoc board space (get board x) x 0))
引数 board が盤面、x が動かす駒の位置、space が空き場所の位置です。assoc で x の位置にある駒をspace に移動し、x の位置に空き場所を表す 0 をセットします。Clojure のベクタは immutable で、assoc により新しいベクタが生成されることに注意してください。
次は駒を動かして新しい局面を生成する関数 make-new-state を作ります。
リスト : 局面の生成
(defn make-new-state [[bd sp _ :as st] q]
(reduce (fn [q0 x]
(let [newbd (move-piece bd x sp)
newst (list newbd x st)]
(conj q0 newst)))
q
(get adjacent sp)))
make-new-state は新しい局面をキュー q に追加します。空き場所の隣の位置を隣接リストから求め、それを reduce に渡します。無名関数の引数 q0 がキュー、x が動かす駒の位置です。move-piece で駒を移動して新しい盤面 newbd を生成します。そして、newbd を格納した新しい局面 newst を生成し、それをキュー q0 に追加します。
それでは幅優先探索のプログラムを作りましょう。次のリストを見てください。
リスト : 幅優先探索
(defn solver-bfs [start goal]
(let [s0 (list start (.indexOf start 0) '())]
(loop [q (conj empty-queue s0)
ht (hash-map)]
(when-not (empty? q)
(let [[bd _ _ :as st] (peek q)
st1 (get ht bd)]
(cond
(= bd goal) (print-answer st)
st1 (recur (pop q) ht)
:else (recur (make-new-state st (pop q))
(assoc ht bd st))))))))
関数 solver-bfs の引数 start がスタートの盤面で、goal がゴールの盤面です。幅優先探索はキューを使うと簡単にプログラムできます。今回は Clojure に用意されている Queue を使用します。キューの使い方は拙作のページ「経路の探索」で簡単に説明しましたので、そちらをお読みくださいませ。
loop / recur の局所変数 q がキューを、ht がマップを表します。幅優先探索の場合、手数を 1 つずつ増やしながら探索を行います。このため、n 手目の移動で作られた局面が n 手以前の局面で出現している場合、n 手より短い手数で到達する移動手順が必ず存在します。最短手順を求めるのであれば、この n 手の手順を探索する必要はありません。マップ ht をチェックして新しい局面だけキューに登録します。
キューが空になり loop / recur が終了する場合、start は goal に到達できない、つまり解くことができなかったことになります。キューにデータがある場合、キューから局面を取り出して変数 st にセットします。そして、同一の盤面がないかマップ ht を検索し、結果を変数 st1 にセットします。
bd が goal と等しい場合、関数 print-answer で手順を表示してからループを脱出します。st1 が真の場合、同一の局面があるので、recur で次の局面を調べます。このとき、(pop q) でキューから現局面を取り除くことをお忘れなく。新しい盤面ならば、make-new-state で新しい局面を生成してキューに挿入し、st をマップ ht に登録します。
あとのプログラムは簡単なので、説明は省略いたします。詳細はプログラムリスト１をお読みください。
これでプログラムは完成です。それでは実行してみましょう。
user=> (time (solver-bfs [8 6 7 2 5 4 3 0 1] [1 2 3 4 5 6 7 8 0])) [8 6 7 2 5 4 3 0 1] [8 6 7 2 0 4 3 5 1] [8 0 7 2 6 4 3 5 1] [0 8 7 2 6 4 3 5 1] [2 8 7 0 6 4 3 5 1] [2 8 7 3 6 4 0 5 1] [2 8 7 3 6 4 5 0 1] [2 8 7 3 6 4 5 1 0] [2 8 7 3 6 0 5 1 4] [2 8 0 3 6 7 5 1 4] [2 0 8 3 6 7 5 1 4] [2 6 8 3 0 7 5 1 4] [2 6 8 0 3 7 5 1 4] [2 6 8 5 3 7 0 1 4] [2 6 8 5 3 7 1 0 4] [2 6 8 5 3 7 1 4 0] [2 6 8 5 3 0 1 4 7] [2 6 0 5 3 8 1 4 7] [2 0 6 5 3 8 1 4 7] [2 3 6 5 0 8 1 4 7] [2 3 6 0 5 8 1 4 7] [2 3 6 1 5 8 0 4 7] [2 3 6 1 5 8 4 0 7] [2 3 6 1 5 8 4 7 0] [2 3 6 1 5 0 4 7 8] [2 3 0 1 5 6 4 7 8] [2 0 3 1 5 6 4 7 8] [0 2 3 1 5 6 4 7 8] [1 2 3 0 5 6 4 7 8] [1 2 3 4 5 6 0 7 8] [1 2 3 4 5 6 7 0 8] [1 2 3 4 5 6 7 8 0] "Elapsed time: 1731.572107 msecs" nil 実行環境 : Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
31 手で解くことができました。生成した局面はゴールを含めて 181440 通りで、実行時間は 1.73 秒かかりました。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 を追加します。
(board space prev dir) ; dir = f or g
start から探索を開始した局面には f を、goal から探索を開始した局面には g をセットすることにします。双方向探索のプログラムは次のようになります。
リスト : 双方向探索
;; 盤面の生成
(defn make-new-state-bi [[bd sp _ dir :as st] q]
(reduce (fn [q0 x]
(let [newbd (move-piece bd x sp)
newst (list newbd x st dir)]
(conj q0 newst)))
q
(get adjacent sp)))
;; 双方向探索
(defn solver-bi [start goal]
(let [s0 (list start (.indexOf start 0) '() 'f)
s1 (list goal (.indexOf goal 0) '() 'g)]
(loop [q (conj (conj empty-queue s0) s1)
ht (hash-map)]
(when-not (empty? q)
(let [[bd sp _ dir :as st] (peek q)
[_ _ _ dir1 :as st1] (get ht bd)]
(cond
(not st1) (recur (make-new-state-bi st (pop q)) (assoc ht bd st))
(not= dir dir1) (print-answer-bi st st1)
:else (recur (pop q) ht)))))))
関数 make-new-state-bi は make-new-state とほぼ同じですが、探索方向を示す dir を局面に追加するところが異なります。関数 solver-bi は、start と gaol の局面を生成してキューに登録します。最初に、start の状態から 1 手目の局面が生成され、次に goal の状態から 1 手目の局面が生成されます。あとは、交互に探索が行われます。
駒の移動と局面の生成処理は幅優先探索と同じです。st と同じ局面がないかマップを探索して結果を変数 st1 にセットします。同じ局面を見つけたとき、st と st1 の探索方向が異なっていれば、双方向からの探索で同一局面に到達したことがわかります。見つけた最短手順を関数 print-answer-bi で出力します。同じ探索方向であれば、キューへの追加は行いません。
あとのプログラムは簡単なので、説明は省略いたします。詳細はプログラムリスト１をお読みください。
それでは実行してみましょう。
(time (solver-bi [8 6 7 2 5 4 3 0 1] [1 2 3 4 5 6 7 8 0])) [8 6 7 2 5 4 3 0 1] [8 6 7 2 0 4 3 5 1] [8 0 7 2 6 4 3 5 1] ・・・ 省略 ・・・ [1 2 3 4 5 6 0 7 8] [1 2 3 4 5 6 7 0 8] [1 2 3 4 5 6 7 8 0] "Elapsed time: 131.877801 msecs" nil
生成された局面数は 16088 個で、実行時間は 0.13 秒でした。局面数は約 1 / 11 になり、実行時間も約 13 倍と高速になりました。
今度は最長手数の局面を求めてみましょう。最長手数の求め方ですが、181440 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかし、この方法では時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。
まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。
このプログラムの目的は、いちばん長い手数となる配置を求めることなので、その手順を表示することは行いません。このため、1 手前の局面を格納する第 3 要素 prev は不要になります。prev のかわりに手数を表すデータを格納することにします。
それではプログラムを作ります。次のリストを見てください。
リスト : 8 パズルの最長手数を求める
(defn make-new-state-max [[bd sp mv :as st]]
(reduce (fn [a x]
(let [newbd (move-piece bd x sp)
newst (list newbd x (inc mv))]
(cons newst a)))
'()
(get adjacent sp)))
(defn solver-max [start]
(loop [xs (list (list start (.indexOf start 0) 0))
hs (conj (hash-set) start)]
(let [[xs' hs'] (reduce (fn [[xs1 hs1] st]
(if (contains? hs1 (first st))
(list xs1 hs1)
(list (cons st xs1) (conj hs1 (first st)))))
(list '() hs)
(mapcat make-new-state-max xs))]
(if-not (seq xs')
(println xs)
(recur xs' hs')))))
関数 make-new-state-max は make-new-state とほぼ同じですが、局面を表すリストを変更します。手順を表示する必要が無いので、(board space prev) の prev (1 手前の局面) のかわりに、手数 move を格納することにします。新しい局面 newst を生成するとき、手数 mv を +1 した値を格納します。
関数 solver-max にはゴールをチェックする処理がないことに注意してください。生成できる局面がなくなるまで処理を繰り返します。このプログラムではキューを使わないで、xs と xs' という 2 つのリストに局面を格納することにします。xs にある局面から新しい局面を生成して、それを xs' にセットします。xs' にデータがない場合、新しい局面は生成されなかったので繰り返しを終了します。このとき、xs に格納されている局面が最長手数となります。
新しい局面は xs に格納された局面に make-new-state-max を適用すれば求めることができます。make-new-state-max を局面を格納したリストを返すので、mapcat で平坦化しています。あとは reduce に渡す無名関数の中で同一局面のチェックを行い、新しい局面であれば xs' とマップ hs' に局面を登録します。
これでプログラムは完成です。さっそく実行してみましょう。
user=> (time (solver-max [1 2 3 4 5 6 7 8 0])) (([8 6 7 2 5 4 3 0 1] 7 31) ([6 4 7 8 5 0 3 2 1] 5 31)) "Elapsed time: 1129.117395 msecs" nil
最長手数は 31 手で、その配置は全部で 2 通りになります。実行時間は 1.13 秒でした。
┌┬┬┬┬┬┐ ┌─┬─┬─┐
├┘│││└┤ │┌┼─┼┐│
├─┼┴┼─┤ ├┼┼─┼┼┤
├─┤ ├─┤ │││ │││
├─┼┬┼─┤ ├┼┼─┼┼┤
├┐│││┌┤ │└┼─┼┘│
└┴┴┴┴┴┘ └─┴─┴─┘
ＳＴＡＲＴ ＧＯＡＬ
図 : スライドパズル
「8 パズル」の変形バージョンです。このスライドパズルは数字ではなく 6 種類の駒 (┘┐┌└│─) を使います。─と│は 2 個ずつあるので駒は全部で 8 個になります。START から GOAL までの最短手順を求めてください。
問題 A, B から GOAL までの最短手順を求めてください。
┌───┬─┬─┐ ┌─┬─┬───┐ ┌───┬─┬─┐
│ 電球 │Ｏ│Ｎ│ │Ｎ│Ｏ│ 電球 │ │ 電球 │Ｎ│Ｏ│
├─┬─┼─┼─┤ ├─┼─┼─┬─┤ ├─┬─┼─┼─┤
│Ｏ│Ｆ│Ｆ│ │ │Ｆ│Ｏ│Ｆ│ │ │Ｏ│Ｆ│Ｆ│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
問題Ａ 問題Ｂ ＧＯＡＬ
図 : NO-OFF
スライドパズル NO-OFF は、問題 A の "ON-OFF" を GOAL のように "NO-OFF" にチェンジするパズルです。NO-OFF は芦ヶ原伸之氏が考案されたパズルで、C MAGAZINE 1991 年 1 月号の「Ｃマガ電脳クラブ」でも出題されています。問題 B は GOAL からの最長手数の局面のひとつです。このパズルは局面の総数が少ないにもかかわらず、手数がけっこうかかる面白いパズルです。
;;;
;;; eight.clj : ８パズルの解法
;;;
;;; Copyright (C) 2025 Makoto Hiroi
;;;
;; 盤面
;; 0 1 2
;; 3 4 5
;; 6 7 8
;; 隣接リスト
(def adjacent
[[1 3] ; 0
[0 2 4] ; 1
[1 5] ; 2
[0 4 6] ; 3
[1 3 5 7] ; 4
[2 4 8] ; 5
[3 7] ; 6
[4 6 8] ; 7
[5 7]]) ; 8
;; キュー
(def empty-queue (clojure.lang.PersistentQueue/EMPTY))
;; 局面
;; (board space prev)
;; 駒の移動
(defn move-piece [board x space]
(assoc board space (get board x) x 0))
;; 解の表示
(defn print-answer [[bd _ pv :as st]]
(when (seq st)
(print-answer pv)
(println bd)))
;; 盤面の生成
(defn make-new-state [[bd sp _ :as st] q]
(reduce (fn [q0 x]
(let [newbd (move-piece bd x sp)
newst (list newbd x st)]
(conj q0 newst)))
q
(get adjacent sp)))
;; 幅優先探索
(defn solver-bfs [start goal]
;; 初期化
(let [s0 (list start (.indexOf start 0) '())]
(loop [q (conj empty-queue s0)
ht (hash-map)]
(when-not (empty? q)
(let [[bd _ _ :as st] (peek q)
st1 (get ht bd)]
(cond
(= bd goal) (print-answer st)
st1 (recur (pop q) ht)
:else (recur (make-new-state st (pop q))
(assoc ht bd st))))))))
;; 双方向探索
;; 局面
;; (board space prev dir)
;; 解の表示
(defn print-answer-f [[bd _ prev _ :as st]]
(when (seq st)
(print-answer-f prev)
(println bd)))
(defn print-answer-g [[bd _ prev _ :as st]]
(when (seq st)
(println bd)
(print-answer-g prev)))
(defn print-answer-bi [[bd _ pv dir :as st] [bd1 _ pv1 _ :as st1]]
(if (= dir 'f)
(do (print-answer-f st) (print-answer-g pv1))
(do (print-answer-f st1) (print-answer-g pv))))
;; 盤面の生成
(defn make-new-state-bi [[bd sp _ dir :as st] q]
(reduce (fn [q0 x]
(let [newbd (move-piece bd x sp)
newst (list newbd x st dir)]
(conj q0 newst)))
q
(get adjacent sp)))
;; 双方向探索
(defn solver-bi [start goal]
(let [s0 (list start (.indexOf start 0) '() 'f)
s1 (list goal (.indexOf goal 0) '() 'g)]
(loop [q (conj (conj empty-queue s0) s1)
ht (hash-map)]
(when-not (empty? q)
(let [[bd sp _ dir :as st] (peek q)
[_ _ _ dir1 :as st1] (get ht bd)]
; (println bd)
(cond
(not st1) (recur (make-new-state-bi st (pop q)) (assoc ht bd st))
(not= dir dir1) (print-answer-bi st st1)
:else (recur (pop q) ht)))))))
;; 最長手数の局面
(defn make-new-state-max [[bd sp mv :as st]]
(reduce (fn [a x]
(let [newbd (move-piece bd x sp)
newst (list newbd x (inc mv))]
(cons newst a)))
'()
(get adjacent sp)))
(defn solver-max [start]
(loop [xs (list (list start (.indexOf start 0) 0))
hs (conj (hash-set) start)]
(let [[xs' hs'] (reduce (fn [[xs1 hs1] st]
(if (contains? hs1 (first st))
(list xs1 hs1)
(list (cons st xs1) (conj hs1 (first st)))))
(list '() hs)
(mapcat make-new-state-max xs))]
(if-not (seq xs')
(println xs)
(recur xs' hs')))))
このスライドパズルは 6 種類の駒 (┘┐┌└│─) を使っています。─と│は 2 個ずつあるので、局面の総数は次のようになります。
駒は次のように整数で表すことにします。
0: 空き場所 1: ┌ 2: ─ 3: ┐ 4: │ 5: └ 6: ┘
そうすると、8 パズルで作成したプログラムをそのまま利用することができます。それでは実行してみましょう。
(time (solver-bi [6 4 5 2 0 2 3 4 1] [1 2 3 4 0 4 5 2 6])) [6 4 5 2 0 2 3 4 1] [6 4 5 2 4 2 3 0 1] [6 4 5 2 4 2 0 3 1] [6 4 5 0 4 2 2 3 1] [0 4 5 6 4 2 2 3 1] [4 0 5 6 4 2 2 3 1] [4 5 0 6 4 2 2 3 1] [4 5 2 6 4 0 2 3 1] [4 5 2 6 4 1 2 3 0] [4 5 2 6 4 1 2 0 3] [4 5 2 6 0 1 2 4 3] [4 0 2 6 5 1 2 4 3] [4 2 0 6 5 1 2 4 3] [4 2 1 6 5 0 2 4 3] [4 2 1 6 5 3 2 4 0] [4 2 1 6 5 3 2 0 4] [4 2 1 6 0 3 2 5 4] [4 2 1 0 6 3 2 5 4] [4 2 1 2 6 3 0 5 4] [4 2 1 2 6 3 5 0 4] [4 2 1 2 0 3 5 6 4] [4 0 1 2 2 3 5 6 4] [4 1 0 2 2 3 5 6 4] [4 1 3 2 2 0 5 6 4] [4 1 3 2 2 4 5 6 0] [4 1 3 2 2 4 5 0 6] [4 1 3 2 0 4 5 2 6] [4 1 3 0 2 4 5 2 6] [0 1 3 4 2 4 5 2 6] [1 0 3 4 2 4 5 2 6] [1 2 3 4 0 4 5 2 6] "Elapsed time: 326.973143 msecs" nil
最小手数は 30 手になりました。実は、GOAL から最長手数となる局面が START なのです。生成した局面数は 14560 個、実行時間は 0.33 秒でした。双方向探索はやっぱり速いですね。手順を図で示すと次のようになります。空き場所は □ で表しています。
┘│└ ─□─ ┐│┌ ┘│└ ┘│└ ┘│└ □│└ │□└ │└□ │└─ │└─ │└─ │└─ ─│─ ─│─ □│─ ┘│─ ┘│─ ┘│─ ┘│□ ┘│┌ ┘│┌ ┘□┌ ┐□┌ □┐┌ ─┐┌ ─┐┌ ─┐┌ ─┐┌ ─┐┌ ─┐□ ─□┐ ─│┐ │□─ │─□ │─┌ │─┌ │─┌ │─┌ │─┌ │─┌ │─┌ │─┌ ┘└┌ ┘└┌ ┘└□ ┘└┐ ┘└┐ ┘□┐ □┘┐ ─┘┐ ─┘┐ ─□┐ ─│┐ ─│┐ ─│┐ ─│□ ─□│ ─└│ ─└│ □└│ └□│ └┘│ │□┌ │┌□ │┌┐ │┌┐ │┌┐ │┌┐ │┌┐ □┌┐ ┌□┐ ┌─┐ ──┐ ──┐ ──□ ──│ ──│ ─□│ □─│ │─│ │─│ │□│ └┘│ └┘│ └┘│ └┘□ └□┘ └─┘ └─┘ └─┘ └─┘ └─┘
ちなみに、最長手数の局面は全部で次の 6 通りあります。
user=> (time (solver-max [1 2 3 4 0 4 5 2 6])) (([6 2 5 4 0 2 3 4 1] 4 30) ([6 2 5 2 0 4 3 4 1] 4 30) ([6 2 5 4 0 4 3 2 1] 4 30) ([6 4 5 4 0 2 3 2 1] 4 30) ([6 4 5 2 0 4 3 2 1] 4 30) ([6 4 5 2 0 2 3 4 1] 4 30)) "Elapsed time: 771.34293 msecs" nil
これを図に示すと次のようになります。
┘─└ ┘─└ ┘│└ ┘│└ ┘│└ ┘─└ │□─ ─□│ ─□│ ─□─ │□─ │□│ ┐│┌ ┐│┌ ┐─┌ ┐│┌ ┐─┌ ┐─┌
生成した局面数は 90720 個になりました。しがたって、 このパズルは駒をランダムに配置しても、必ずゴールに到達できることがわかります。
このパズルは局面の総数が 540 通りしかありません。
電球(3 通り) * 空き場所(6 通り) * N (5 通り) * O (4C2 = 6 通り) = 540 通り
解は幅優先探索で簡単に求めることができます。詳細はプログラムリスト２をお読みください。ちなみに、GOAL までの最長手数は 56 手で、局面は全部で 3 通りあります。問題 B はその中の 1 つです。
user=> (solver-max '[L1 L2 N O O F F S]) (([F N L1 L2 O O F S] 7 56) ([O F L1 L2 N O F S] 7 56) ([N O L1 L2 F O F S] 7 56)) nil
┌─┬─┬───┐ ┌─┬─┬───┐ ┌─┬─┬───┐
│Ｆ│Ｎ│ 電球 │ │Ｎ│Ｏ│ 電球 │ │Ｏ│Ｆ│ 電球 │
├─┼─┼─┬─┤ ├─┼─┼─┬─┤ ├─┼─┼─┬─┤
│Ｏ│Ｏ│Ｆ│ │ │Ｆ│Ｏ│Ｆ│ │ │Ｎ│Ｏ│Ｆ│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
図 : 最長手数の局面
L L が電球を表し、_ が空き場所を表します。
(0) (1) (2) (3) (4) (5) (6) (7) L L O N L L O _ L L _ O _ L L O O L L O O L L O O L L O O L L O O F F _ O F F N O F F N O F F N _ F F N F _ F N F F _ N F F N _ (8) (9) (10) (11) (12) (13) (14) (15) O L L _ O _ L L _ O L L F O L L F O L L F _ L L F L L _ F L L O F F N O F F N O F F N O _ F N O F _ N O F O N O F O N O F O N _ (16) (17) (18) (19) (20) (21) (22) (23) F L L O F L L O F L L O _ L L O L L _ O L L O _ L L O N L L O N F O _ N F _ O N _ F O N F F O N F F O N F F O N F F O _ F F _ O (24) (25) (26) (27) (28) (29) (30) (31) L L _ N _ L L N F L L N F L L N F L L N F L L N F L L _ F _ L L F F O O F F O O _ F O O F _ O O F O _ O F O O _ F O O N F O O N (32) (33) (34) (35) (36) (37) (38) (39) F O L L F O L L _ O L L O _ L L O L L _ O L L N O L L N O L L N F _ O N _ F O N F F O N F F O N F F O N F F O _ F F _ O F _ F O (40) (41) (42) (43) (44) O L L N _ L L N L L _ N L L N _ L L N O _ F F O O F F O O F F O O F F O O F F _
L L が電球を表し、_ が空き場所を表します。
(0) (1) (2) (3) (4) (5) (6) (7) N O L L N O L L N O L L N _ L L N L L _ N L L F N L L F N L L F F O F _ F O _ F F _ O F F O O F F O O F F O O _ F O _ O F _ O O (8) (9) (10) (11) (12) (13) (14) (15) N L L F _ L L F L L _ F L L F _ L L F O L L F O L L _ O _ L L O _ F O O N F O O N F O O N F O O N F O _ N F _ O N F F O N F F O (16) (17) (18) (19) (20) (21) (22) (23) N L L O N L L O N L L O N L L O N L L _ N _ L L _ N L L F N L L _ F F O F _ F O F F _ O F F O _ F F O O F F O O F F O O _ F O O (24) (25) (26) (27) (28) (29) (30) (31) F N L L F _ L L F L L _ F L L O F L L O F L L O F L L O _ L L O F _ O O F N O O F N O O F N O _ F N _ O F _ N O _ F N O F F N O (32) (33) (34) (35) (36) (37) (38) (39) L L _ O L L N O L L N O L L N _ L L _ N _ L L N F L L N F L L N F F N O F F _ O F F O _ F F O O F F O O F F O O _ F O O F _ O O (40) (41) (42) (43) (44) (45) (46) (47) F L L N F L L N F L L _ F _ L L F O L L F O L L _ O L L O _ L L F O _ O F O O _ F O O N F O O N F _ O N _ F O N F F O N F F O N (48) (49) (50) (51) (52) (53) (54) (55) O L L _ O L L N O L L N O L L N O L L N _ L L N L L _ N L L N _ F F O N F F O _ F F _ O F _ F O _ F F O O F F O O F F O O F F O (56) L L N O O F F _
;;;
;;; no_off.clj : NO-OFF パズルの解法
;;;
;;; Copyright (C) 2025 Makoto Hiroi
;;;
;; 盤面
;; 0 1 2 3
;; 4 5 6 7
;; 駒
;; S : 空, L1, L2 : 電球
;; N, F, O
;; 隣接リスト
(def adjacent
[[1 4] ; 0
[0 2 5] ; 1
[1 3 6] ; 2
[2 7] ; 3
[0 5] ; 4
[1 4 6] ; 5
[2 5 7] ; 6
[3 6]]) ; 7
;; キュー
(def empty-queue (clojure.lang.PersistentQueue/EMPTY))
;; 局面
;; (board space prev)
;; 駒の移動
(defn move-piece [board x space]
(let [piece (get board x)]
(cond
(= piece 'L1) ; 電球を左へ
(if (== (dec x) space)
(assoc board space 'L1 x 'L2 (inc x) 'S)
board)
(= piece 'L2) ; 電球を右へ
(if (== (inc x) space)
(assoc board space 'L2 x 'L1 (dec x) 'S)
board)
:else (assoc board space piece x 'S))))
;;; 解の表示
(defn print-answer [[bd _ prev :as st]]
(when (seq prev)
(print-answer prev)
(println bd)))
;; 盤面の生成
(defn make-new-state [[bd sp _ :as st] q]
(reduce (fn [q0 x]
(let [newbd (move-piece bd x sp)
newst (list newbd (.indexOf newbd 'S) st)]
(conj q0 newst)))
q
(get adjacent sp)))
;; 幅優先探索
(defn solver-bfs [start goal]
(let [s0 (list start (.indexOf start 'S) '())]
(loop [q (conj empty-queue s0)
ht (hash-map)]
(when-not (empty? q)
(let [[bd _ _ :as st] (peek q)
st1 (get ht bd)]
(cond
(= bd goal) (print-answer st)
st1 (recur (pop q) ht)
:else (recur (make-new-state st (pop q))
(assoc ht bd st))))))))
;; 最長手数の局面
(defn make-new-state-max [[bd sp mv :as st]]
(reduce (fn [a x]
(let [newbd (move-piece bd x sp)
newst (list newbd (.indexOf newbd 'S) (inc mv))]
(cons newst a)))
'()
(get adjacent sp)))
(defn solver-max [start]
(loop [xs (list (list start (.indexOf start 'S) 0))
hs (conj (hash-set) start)]
(let [[xs' hs'] (reduce (fn [[xs1 hs1] st]
(if (contains? hs1 (first st))
(list xs1 hs1)
(list (cons st xs1) (conj hs1 (first st)))))
(list '() hs)
(mapcat make-new-state-max xs))]
(if-not (seq xs')
(println xs)
(recur xs' hs')))))