チョコレート・パズルを解くプログラム

softark.net > 記事 > チョコレート・パズル

チョコレート・パズル

2006年のバレンタイン・デー(の数日後)に、コンビニをやっている義妹から、「明治ミルク・チョコレート・パズル」と「明治ブラック・チョコレート・パズル」とを貰った。

キャスト・パズルが有名な株式会社ハナヤマの商品だ。ええと、勝手に画像を拝借するといけないのですね。宣伝になって良いと思うのだけれども。仕方がない、リンクしておこう。株式会社ハナヤマ > PUZZLE

ミルク・チョコレート・パズル

ミルク・チョコレート・パズルは、長方形のケースの中に、形の違う12個のピースが入っている。それぞれのピースは、正方形を5個つなぎ合わせたものだ。

遊び方は簡単で、ケースからピースを取出してよく混ぜ、もう一度ケースに戻せばよい。うまくピースを組み合わせると、全体が6x10の長方形になって、ケースにぴったりと納まるのだ。

ピースは、裏返して使ってもかまわない。

難易度は「ピュア(甘め)」だと書いてある。

確かに解答は2339通りもあるのだが、だからと言って簡単な訳ではない。

これは、ペントミノという有名なパズルだ。

ブラック・チョコレート・パズル

ブラック・チョコレート・パズルは、長方形のケースの中に、形の違う11個のピースが入っている。それぞれのピースは、正方形を6個つなぎ合わせたものだ。

これも遊び方は同じである。うまくピースを組み合わせると、全体が6x11の長方形になって、ケースにぴったりと納まる。

ただし、ミルク・チョコレートと違って、ピースを裏返して使うことは出来ない。

難易度は「ビター(苦め)」だと書いてある。

確かに解答は1通りしかないのだが、だからと言ってミルク・チョコレート・パズルに比べて2339倍も難しい訳ではない。

これは、ヘキソミノというパズルのサブセットだ。

作者は、その筋では有名な、芦ヶ原さん。

ホワイト・チョコレート・パズル

ブラックもミルクも難しすぎる、という訳で、チョコレート・パズルの第三弾として発売されたのが、ホワイト・チョコレート・パズルだ。長方形のケースの中に、形の違う8個のピースが入っている。ピースは、正方形を6個つなぎ合わせたものが3つ、正方形5個のものが3つ、正方形4個のものと正方形3個のものが1つづつある。全部L字型をしている。

これも遊び方は同じ。うまくピースを組み合わせると、全体が5x8の長方形になって、ケースにぴったりと納まる。

ピースは、裏返して使ってもかまわない。

難易度は「スイート(とろける甘さ)」だそうだ。うまいなあ。

解答は7764通りある。本当にすごく簡単かどうかは、僕は知らない。まだ手に入れていないのだ。

これは、名付けるとすれば、L字型8ピース・ポリオミノ、ということになるようだ。

作者は、これもその筋の、小田原さん。

解答図は入っていない

どのパズルにも解答図は入っていない。

「最初はピースをバラバラにして遊ぶ前に、収納されている組み合わせよく覚えておくとよいでしょう」という、やんわりとした注意書きが箱に書いてあるのだが、そんなものを誰が読むだろうか。少なくとも、うちの子供たちは読まなかった。多分、ほとんどの人が、何気なくケースからピースを取り出して遊び始めるだろうと思う。そして、しばらくの間(根気が続く限り)やってみて、どうもこれは難しいぞ、と気がつく。しかし、その時は既に遅いのである。

解答が分らない限り(ピースをケースに収納しない限り)は、片付けることが出来ない。どうすんの、これ。

プログラムでチョコレート・パズルを解く

ウェブで検索すると、「ペントミノを解く」というページが見付かった。コンピュータでプログラムを組んでペントミノを解いているのである。

とりあえず、ミルクの方は、このページで解答(例)を得ることが出来た。

しかし、ブラックの方の解答は載っていない。仕方がないので、というか、面白そうだったので、自分でプログラムを組んでみた。

かみさんからは「何を一生懸命仕事をしよるかと思たら、あんたと言う人は」と、えらい権幕で怒られることになったのだが、おかげで、ミルクもブラックも、無事にケースに戻すことが出来た。

プログラムを作って動かしてみるとよく分るのだが、これらのパズルは「プログラムで解く」という遊び方で遊ぶべきものだ。プログラマ向けのパズルなのである。コンピュータ・プログラムを使わずに解こうとするのは、よほど暇を持て余している人でなければ、やめておいた方が良い。

参考リンク

ペントミノを解くプログラムについて興味があるプログラマの方には、ウェブ上にある次の二つの文献を参照することを強くお奨めする。

「ペントミノを解く」

中村さんによるもの。特に、「第5章 C言語版の高速化あれこれ」が面白い。

「Cパズルプログラミング-再帰編」 > ペントミノ

「初心者」を名乗る藤原さんによるもの。ペントミノの項だけでなく、みんな面白い。どこが初心者なんだかよく分らない。

さらに、ホワイト・チョコレート・パズルの作者による以下のサイトも参考になる。

「ジャグラー小田原の箱詰めパズル天国」 > 「第４１回　明治ホワイトチョコレートパズル」

作者である小田原さん自身によるホワイト・チョコレート・パズルの簡単な紹介のページ。

その他の回をあちこち覗いてみる事をお奨めする。箱詰めパズル一般についての概説としてちょうど良いと思う。

Bitter(64).exe

Bitter.exe は、中村さんや藤原さんの文献を参考にして僕が作った、チョコレート・パズルを解くプログラムだ。

2006年3月に公開した時は、ミルクとブラックに対応したものだったが、2008年1月、ホワイトにも対応したものにバージョン・アップした。

お二人のプログラムに比べると、長所は、ミルクだけでなくブラックとホワイトにも対応していること、グラフィカルなインターフェイスを持っていること、ゲームの途中で停止・再開が出来ることであり、短所は、遅いことである。

2010年1月、Bitter.exe はおかしな方向に進化した。英語スキンと中国語(簡体字)スキンを手に入れたのである。パズルを解く性能は全く進化していない。

さらに、64-bit 版 Windows 専用の Bitter64.exe も作った。32-bit 版との速度の違いが気になったが、結果はあんまり変り映えがしなかった。ミルクを解く速度は若干速いが、ホワイトでは逆にかなり遅くなる。

ダウンロード

BitterSetup.exe

32-bit 版 Bitter.exe のインストーラ。64-bit 版の Windows にもインストール可能。

Bitter64Setup.exe

64-bit 版 Bitter64.exe のインストーラ。32-bit 版の Windows にはインストール出来ない。

bitter-src-2010-01-22.zip

Bitter.exe および Bitter64.exe のソース。Microsoft Visual Studio 2008 の VC++ プロジェクト一式である。

気が向いたらどうぞ。好きなように弄ってもらっても、一向に構わない(BSD License の下にあるものとする)。ただし、藤原さんのソースの方がはるかに簡潔で面白く、読んで為になる。

プログラムの使い方

念のために、プログラムの使い方を一通り説明しておこう。

これが、チョコレート・パズルを解くプログラム、Bitter.exe だ。

使い方は簡単で、まず、ゲームのモードとピースの表示方法を選ぶ。

次に、「スタート」ボタンを押すと、プログラムが解答の探索を開始する。

ゲームのモード

ゲームのモードは、以下の八通りを選ぶことが出来る。

No	モード	ピース		盤面サイズ		解答数	難易度
		タイプ	数	縦	横
1	ミルク	ペントミノ	12	6	10	2,339	100
2	ミルク 5x12			5	12	1,010	93
3	ミルク 4x15			4	15	368	49
4	ミルク 3x20			3	20	2	294
5	ミルク 8x8			8	8	65	831
6	ブラック	ヘキソミノ	11	6	11	1	2,842
7	ホワイト	ポリオミノ	8	5	8	7,764	18
8	ホワイト 7x7			7	7	95	47

難易度は、総試行回数を解答数で割った値(すなわち、一つの解が見つかるまでの平均的な試行回数)を、ミルク(6x10)の場合を100とした相対値で示したものである。この数値から見る限りでは、「ピュア(甘め)」「ビター(苦め)」「スイート(とろける甘さ)」と言われている難易度は、だいたい正しいものだと言って良い。

「ミルク 8x8」は、盤面の中央に 2x2 の空白を空けて、ドーナッツ状にピースを並べる。同様に、「ホワイト 7x7」は、盤面の中央に 3x3 の空白を空ける。そうしないと、数が合わない。

ウィンドウのサイズは「ミルク (6x10)」に最適化されている。

それ以外のモードでは、図のように、ブロックのサイズを小さくして、盤面全体がウィンドウに収まるように調整して表示している。そのため、モードによっては、盤面の上下または左右に大きな余白が生ずることになる。

ピースの表示

ピースの表示の仕方は、以下の五通りを選ぶことが出来る。

No	表示	ピースの表示の仕方
1	なし	すべての解答の探索が完了するまで、一切の表示をしない。
2	解答のみ	解答のみを表示する。途中経過は表示しない。
3	高速	準備動作も含めて、すべてのピースの動きを表示する。
4	中速
5	低速

「中速」以下を選べば、ピースの動きを追って、プログラムの思考過程をおぼろげながら理解することが出来るかもしれない。

思考過程といっても、大筋は、順序立てて総当たりの試行錯誤をしているだけだ。

準備動作が見た目に少し面白いかもしれないが、何をしているかと言うと、向きを変えたものを含む全てのピースについて、置くことが出来る盤上の位置をあらかじめ記録している。後に続く探索の段階では、ピースを置けるか置けないかという判定の処理が何度も繰り返されることになるが、その判定の処理を軽くするための仕込みをしている訳だ。

「解答ごとにストップ」

「解答ごとにストップ」にチェック・マークを入れると、プログラムが解答を見付けるたびに一時停止する。

ただし、「表示」が「なし」の場合は、「解答ごとにストップ」の設定は出来ない。

「初期化」ボタン

「初期化」ボタンは、ゲームを初期状態に戻すためのボタンだ。

初期化するたびに、ピースの形状と色はランダムに割り当てらる。従って、同じモードでも、ゲームを行うたびに、解答の出現順序も、それぞれの解答に辿り着くまでの試行回数も、異なるものになる。

なお、「初期化」ボタンを押さなくても、「モード」を変更すると、ゲームの状態は初期化される。

「スタート」ボタン

「スタート」ボタンは、ゲームの状態に応じて、以下のように名称や状態と動作が変化する。

ゲームの状態		ボタンの名称・状態	動作
初期状態		「スタート」	解答の探索を開始
解答探索中	表示あり	「ストップ」	解答の探索を一時停止
	表示なし	(無効)	(一時停止不可)
一時停止中		「再スタート」	解答の探索を再開
解答探索完了後		(無効)	(最初の解答を再表示して停止)

「表示なし」で探索をすると、一時停止することが出来ず、探索が完了するまで待たなければならない。しかし、余程非力なCPUは別として、もっとも解答数の多いモード(ホワイト)でも、3秒以内に探索を完了すると思う。

「解答表示」ボタン

「解答表示」ボタンは、解答の探索が完了した後に、解答だけを表示させるためのボタンである。

表示の仕方は、「表示」と「解答ごとにストップ」の設定に応じて変る。

「解答ごとにストップ」が ON の場合

「解答表示」ボタンを押すたびに、探索順に従って、1個づつ、解答を表示して停止する。

最後まで表示したら、最初に戻って繰返す。

「解答ごとにストップ」が OFF の場合

「解答表示」ボタンを押すと、探索順に従って、解答を連続して表示する。

解答を表示する速度は、「表示」のモードに従う。

最後まで表示したら、最初に戻って繰返す。

「解答表示」ボタンは「ストップ」ボタンに変る。「ストップ」ボタンを押すと表示を停止する。

「終了」ボタン

Bitter.exe を終了させる。

システム・メニュー

プログラムの左肩のアイコンをクリックすると、システム・メニューが表示される。

以下のメニュー項目がサポートされている。

移動

ウィンドウをキーボードで移動する。

閉じる

プログラムを終了して、ウィンドウを閉じる。

言語スキン

日本語、英語、中国語(簡体字)の中から、言語スキンを選ぶことが出来る。

ヘルプ

ヘルプ・ファイルを表示する。

オンライン・ヘルプ

ウェブ上のヘルプ・ページを表示する。

バージョン情報

プログラムのバージョン情報を表示する。

ただし、インストール時に「言語スキン」オプションを選択しなかった場合は、言語スキンの変更は出来ない。また、インストール時に「ヘルプ」オプションを選択しなかった場合は、ヘルプ・ファイルは表示出来ない。

日本語のインストーラで「標準」セットアップを選んだ場合、言語スキンはインストールされないが、ヘルプ・ファイルはインストールされる。

---

以上、何かお気づきの点があれば、お気軽にフィードバックを下さい。

• 記事 目次

• チョコレート・パズル (日本語)
• Chocolate Puzzle (in English)