というわけでヒョンなことから NTGメンバーの海渡り問題(?)にチャレンジすることに。
元ねた(?)はこちら。

問題を簡単に書くと…

目的

日本にいる次の12人を舟で無事にアメリカに移動させる。
室内王者、黒豹、白鴎、根来、AL、悪夢、縞蜂、増山、架幽、桜、貞二、岡山

条件①

舟は1艘のみで1度に乗れるのは2人まで。1人でもよい。

条件②

行きも帰りも舟には次の中から1人乗る必要がある。
室内王者、黒豹、白鴎、根来、AL

条件③

日本、アメリカ、舟の上のどこでも以下の条件を満たす必要がある。

• 「室内王者」は「黒豹」がいないときに「桜」と一緒にいないこと。
• 「黒豹」は「室内王者」がいないときに「貞二」と一緒にいないこと。
• 「根来」は「室内王者」も「黒豹」もいないとき「桜」「貞二」「岡山」の誰とも一緒にいないこと。
• 「AL」は「根来」か「増山」と一緒にいること。
• 「増山」は「根来」も「AL」もいないときに他の誰とも一緒にいないこと。
• 「縞蜂」は「白鴎」がいないときに他の誰とも一緒にいないこと。
• 「貞二」は「室内王者」も「黒豹」もいないときに「岡山」と一緒にいないこと。
• 「桜」は「室内王者」も「黒豹」もいないときに「岡山」と一緒にいないこと。

ようは「宣教師と人食い人」の変形ですね～。
てか調べてみるとこの手のは「川渡り問題」として種種のバリエーションがあるようです。
『C言語による最新アルゴリズム事典』にある「宣教師と～」しか知らなかった…

ちなみにヘンゼルはっきり言ってこの手の問題は大の苦手。
多少のコツはあるものの基本的には総当たり。
すぐに投げ出しちゃいます。

ってことでプログラマらしくここは PC に解かせましょう。

でも PC を変えてから VC++ をインストールしていないんだった。
とりあえず手元にあってすぐ作れるものは…PHP?

仕方がないので不向きと知りつつもいろいろ工夫して作ってみますが…
やっぱりタイムアウトします。
もちろん試すのはサーバ上ではなくローカル。

php.ini をいじってタイムアウト時間をぐっと延ばすと、今度はブラウザがタイムアウト。
もっとがんばればどうにかなるかもだけどもともとスクリプト言語に向いた問題じゃないし。

というわけで久しぶりに VC++6.0 を取り出してインストール。
せこせこがんばって作ってみると…あっという間に解が出ました(笑)

最短解を見つけるまでの時間は 1秒未満。
その間に試したパターンは 1521180通り。さすが今時のマシンです。
船は 11往復半で全員をアメリカに移動させました。

ただ作っていて気付いたのですがどうも最短解が複数あるようです。
というわけでちょっと改良して別解もカウントする機能を追加。

今度は 24秒かかって 57759432通りのパターンを試し、11往復半で全員を
移動させる 16032個の解答を見つけ出しました。
1つ1つ確かめるなんてとても出来ないので合っているのかどうか判りませんが(笑)
でもこれだけ解があると人間でもがんばっていれば 1つくらい見つけられそうですね。

…てか総当たりしかないと決めつけたけど実はよりスマートな解法があったりするのかなぁ?
検索した限りでは見つからなかったけど。

ちなみに作ったツールはこれ。