暇潰しに丁度いい

　スマホ弄っていたら広告を見かける人も多いと思いますが、最近ボトルに色分けされた水が入っていてそのボトル内の水を同一色に並べ替えるゲームに嵌っています。ウォータソートパズルとか水選別パズルとか呼ばれてるようで、大抵の問題は何回かやり直せば正解にたどり着けるのですが、どうしても解けないパターンに出会って、「そもそもこれに解答は存在するのか？」という疑問を持ったのでプログラムを作って確認することにしました。

とりあえずGrokに聞いてみる

　最近プログラミングに関する技術的な調べものをする際にGrokを何度か使ってみて、Googleで調べるより効率的かもと思っていたので試してみました。
　上記の画像ファイルをアップロードしてGrokに「このウォータソートパズルの解答手順を教えてください」と聞いてみたところ
「ボトルは１２本ですね」とか言いながら解答手順を即答しましたが、
画像の認識が間違っているので「よく見てください、ボトルは１３本です」と送ると
「申し訳ありません、画像をよく確認したところ、ボトルは12本ではなく13本ですね」とかいいながら、また間違った問題のまま解答手順を列挙してきました。
更に「ボトルは上段に７本、下段に６本です。下段の右側に空のボトルが２本有ります」と訂正すると
「ご指摘ありがとうございます」とかいいながら、またまた間違った問題のまま解答手順を列挙してきました。
こんな感じでやり取りが延々続いて解答は得られませんでした。問題の画像を正確に認識するのが難しいみたいです。それにしても解答の速さに驚いたのですが、画像の認識さえ正確に出来れば解答手順も正確に答えられるのでしょうか？ 以下のテキストを貼り付けて再度Grokに聞いてみました。

      [RED, SKY_BLUE, RED, YELLOW],
      [MAGENTA, PINK, AQUA_GREEN, RED],
      [AQUA_GREEN, YELLOW_GREEN, PURPLE, BLUE],
      [SKY_BLUE, MAGENTA, ORANGE, YELLOW],
      [PURPLE, PINK, ORANGE, YELLOW_GREEN],
      [PURPLE, BLUE, PINK, AQUA_GREEN],
      [ORANGE, YELLOW, AQUA_GREEN, PURPLE],
      [SKY_BLUE, BLUE, GRAY, GRAY],
      [SKY_BLUE, YELLOW_GREEN, MAGENTA, RED],
      [YELLOW, MAGENTA, ORANGE, GRAY],
      [YELLOW_GREEN, GRAY, PINK, BLUE],
      [],
      []

　すると今度は「提供された色のリストに基づき、ウォーターソートパズルの解答手順を日本語で説明します」と言いながら手順を示してきたのですが、ボトルの最上段に存在しない色を移動していたり、ルールを無視した手順を何回も示してきました。
根気よく訂正し続ければ解答できるのかもしれませんが、自分には無理そうに思えたので諦めました。

自分で解答プログラムを作る

　以前の記事で紹介した将棋パズル解答プログラムとほぼ同じコードで解決できそうなのでやってみました。BFS（幅優先探索）を使って一手ずつ局面を進めてすべてのボトルの色が一色に揃う解答画面に辿り着いた時点で探索を終了し、その手順を遡って表示します。
　BFSでは解答までの最短手順を表示しますが、実行時間がかなりかかります。PCのスペックにもよりますし、問題によってもかなり解答までの時間が大きく変化するのですが、ボトル５本（内、空ボトル２本）なら１秒も掛かりませんけど、ボトル９本（内、空ボトル２本）だと３〜４時間掛かりました。冒頭で紹介しているボトル１３本（内、空ボトル２本）では数日掛かるのでしょうか？実際に作ってみる前の想像以上に時間が掛かるのはマンカラの時と同じですね。

DFS（深さ優先探索）版も作ってみる

　解答を得るのにあまりにも時間がかかりそうなのでDFS版も作ってみました。するとBFS版だと数日掛かると思われた上記の問題が１秒掛からずに解答を得ることが出来ました
　但しDFS版で得られた解答手順は最短手順とは限りません。でも、そもそも解答が存在するのかどうかを知りたいというのが目的だったので満足です。上記の問題もDFS版で出力された解答手順通りにやればアプリ上で実際に解けました。

解けない問題はあるのか？

　BFS版で問題を解くためにあまりに時間が掛かるので、DFS版を作ってみるまでは「この問題には解が存在しない」と言い切るための条件はなんだろう？とか「解が存在することを証明するにはどうすればいいのか？」なんて難しく考えていたのですが時間の無駄でした。解けるかどうか判断するには「DFSアルゴリズムで作られた解答プログラムで確認すればいいだけ」ですね、スタックオーバーフローに見舞われない限りは…。
　逆に空ボトル２本で解けない問題を作る方が難しいのかもしれません。ちなみに空ボトルを１本にすれば解けない問題はすぐに出来上がりますが、解は存在するけど解くのが難しい問題というのを意図的に作るのは難しいと思います。将棋パズルの記事や３三将棋アプリの記事でも書きましたが、問題を解くよりも、難しい問題を作る方が難しいというのはウォーターソートパズルに関しても言えそうです。
　あと「ボトルの数がどれぐらい増えれば空ボトルが最低３本必要になるのか？」とか「空ボトル２本で解けるのは全体のボトル数が何本が限界？」とかの問題を考えるのも面白いかもしれませんが、ボトル１本あたりの色の数とかも考慮し出すとキリが無いので何か汎用的な法則を見つけ出すのは大変でしょうね。

ヒント機能はどうなってるのか？

　アプリの中にはヒント機能が実装されているものも有ります。ヒント機能があるということはアプリが解答も知っているということなので、DFS版を作ってみるまでは予め用意した問題だけを出題してるのだろうか？と考えたりしましたが、そんなことはなくDFSなら簡単にリアルタイムでヒントが出せそうです。つまり、確認はしてませんがヒント機能があるウォーターソートパズルアプリが出すヒントは最短手順のヒントではないと思われます。

プログラムの解説（Nodeクラスの役割）

　プログラムは水を入れる入れ物であるBottleクラス、ボトルを収納するBoxクラス、開始局面を頂点とするゲーム木を生成して格納するNodeクラスの３つのクラスを使っていますが、Nodeクラスについて解説します。
　まずBFSの場合は、一手目の操作で現れ得る局面をすべて調べてから二手目の局面を調べるという順番なのでゲーム木を横方向に走査していく形になります。同じ手数の局面を横方向に全部調べてから次の手数の局面を全部調べるので、最終的に解答手順を表示する時に縦の手順に変えなければいけません。横方向に局面を蓄積（addメソッド）していって、最終的に辿り着いた完成局面から、今度は開始局面までを縦方向に手順を再帰的に遡って辿り着くようにして表示しているのがNodeクラスの役割です。
　次にDFSの場合は開始局面から指定された深さの末端ノードまで一気に読み進めて、末端ノードを調べ尽くしたら指し手を遡ってまた隣の経路を末端ノードまで読むという感じでゲーム木を縦方向に読み進めます。だからBFSのように局面を蓄積していく必要はなく、毎回辿った履歴を上書き（replaceメソッド）していけば最終的に辿り着いた完成局面までの履歴が残ります。今回作ったプログラムは先にBFSのプログラムを作ったのでNodeクラスのようなものを用意しましたが、DFS版だけ作ることを考えるのならNodeクラスのようなもので再帰的に局面を辿るようにしなくても、外部変数の配列を一つ用意して局面が進む度に上書きしていけば開始局面から完成局面までの一本のルートが配列に残ります。昔、オセロのパズル（DFS版）を作った時はそんな感じで作りました。→github
　偉そうに解説していますが、実際そうなっているかどうか詳しく確認していませんし、バグってるかもしれません。自己責任でご利用ください。
　将棋もプログラミングも直感精読!!、特に直感が大事だと思います。

答えを知るために必要なプログラムの変更箇所

　game_bfs.rbでもgame_dfs.rbでも、ボトルを格納するためのBoxオブジェクト生成部分を書き換えればいろんな問題に対応できます。色数を増やす場合は色の定義ファイル（const.rb）と表示部分（box.rb）を修正する必要があります。

 box = Box.new(
   [
     Bottle.new([PINK, YELLOW_GREEN, GRAY, PINK]),
     Bottle.new([BLUE, YELLOW_GREEN, ORANGE, YELLOW]),
     Bottle.new([ORANGE, YELLOW, BLUE, PINK]),
     Bottle.new([RED, ORANGE, ORANGE, PINK]),
     Bottle.new([GRAY, YELLOW, BLUE, RED]),
     Bottle.new([YELLOW_GREEN, RED, BLUE, GRAY]),
     Bottle.new([YELLOW_GREEN, GRAY, RED, YELLOW]),
     Bottle.new,
     Bottle.new
   ]
  )