トップページへ

イラストパズルとは、「お絵かきパズル」、「イラストロジック」とも呼ばれている、 雑誌、携帯電話ゲームなどで人気のあるパズルです。
下図のように上部と左部に数の列（設定数列）が問題として提示され、その数の列に合うように、 升目（セル）の中を塗り分けて画像を完成させるパズルです。

作者も、このパズルが掲載された雑誌をときどき購入してパズル解きを楽しんでいますが、 行・列の数が大きくなると、解くのに時間がかかり、問題によっては途中で解を断念することがあります。
イラストパズルは、設定数列を丹念に論理的に追って、セルを塗り分けていくことに楽しみがありますが、 未解決の問題が残るのは残念なことです。
そこで、パソコンを使ってこのパズルを解くソフトウエアを作ってみようと思い立ち、作成したのが「MyIllustPuzzle」です。
このソフトウエアは、イラストパズルを解くためのものであって、パズル自体を楽しむものではありません。
従ってパズル愛好者の方々からは非難を受けることになるかもしれません。
そのために、通常のソフトウエア紹介の項ではなく、習作を扱う「ソフト関連Trial」として、このソフトウエアを紹介することにしました。
いずれかの機会に、イラストパズル自体を作成して、公開するようなサイトが作れたらと思っています。
（なお、続編として小型、難問イラストパズルの解法に関するソフト関連Trial記事を、No.102に公開しました。）

このソフトウエアでは、Try１〜４の四段階の試行（Try）で、セルの白黒を確定していきます。
ここで使用する用語を以下のように定義します。
　　行・列 ： 行または列
　　設定数列 ： 問題で指定される各行・列の数の並び
　　黒数合計 ： 問題で指定される各行・列の設定数列の数値の和
　　ブロック ： 設定数列の各要素
　　ブロック数 ： 問題で指定される各行・列のブロックの数（設定数列の要素の数）
　　有効数合計 ： （黒数合計）＋（ブロック数）−１
　　動かし代（シロ） ： 各行・列の全セル数（列または行の数）−有効数合計

Try１
Try１は、１つの行・列に属する全セルの状態が確定できる場合に有効な方法です。
例として、行数が１０行の問題があるとして、
設定数列が［１０］というブロック数が１の列では、その列の全てのセルが黒に確定できます。
設定数列が［２，７］というブロック数が２の列では、上から２個のセルが黒、上から３番目のセルが白、 残りの下７個のセルが黒に確定できます。
このように、（（黒数合計）＋（ブロック数）−１）が１０となる列では、全てのセルが確定できます。
この（（黒数合計）＋（ブロック数）−１）は便利な数値なので、前項で定義したように有効数合計と呼び、他のTryでも利用します。
本ソフトウエアでは、Try１メソッドとして、この確定方法を実装しています。

Try２
Try２は、動かし代が小さい行・列に対して有効な方法です。
具体例があった方がわかりやすいので、問題の列数が１０列で、設定数列が［２，５］というブロック数２の行を例として Try２の方法を説明します。
この例で、対象行の左端から設定数列［２，５］に従ってセルを埋めていく左詰め方式と、 対象行の右端からセルを埋めていく右詰め方式とで、セルの状態を表示してみます。

　　（左詰め）　■、■、□、■、■、■、■、■、□、□
　　（右詰め）　□、□、■、■、□、■、■、■、■、■

この左詰めと右詰めで同一位置のセルの状態を較べて、両者の場合とも黒であって、しかもそれが同一のブロックに 属するものである場合、その位置のセルは黒として確定することができます。
上の例では、左から６〜８番目がこの条件に合致します。
左から４番目も両者は黒になっていますが、その黒は左詰めの場合は第２ブロックに属するもの、 右詰めの場合は第１ブロックに属するものと、属するブロックが異なっていて、前記条件からはずれているので、 その位置のセル状態を確定するまでには至りません。
この確定方法をプログラムで実現するために、白は−１、黒にはブロックの番号（０から始まる番号）を付与して、 左詰め、右詰めで−１以外の同一の値となる位置を見つけるようにします。

　　（左詰め）　０、０、-1、１、１、１、１、１、-1、-1
　　（右詰め）　-1、-1、０、０、-1、１、１、１、１、１　

このようにすれば、行・列の数が増え、ブロックの数が増えても、容易に判定することができます。
本ソフトウエアでは、Try２メソッドとして、この確定方法を実装しています。

Try３
Try３は、上下左右の四辺に黒または白の既決セルがある場合に、その行・列に対して適用できる方法です。
具体例として、１０行１０列の問題で、左端が以下のように黒に決定されている行について検討をしてみます。
　　（検討開始状態）　■、？、？、？、？、？、？、？、？、？
この行の設定数列が［３，２］である場合に、少なくとも以下の部分まではセルの状態を決めることができます。
　　（決定可能状態）　■、■、■、□、？、？、？、？、？、？
もし初期状態が以下のようになっていて、設定数列［３，２］である場合には、
　　（検討開始状態）　■、？、？、？、■、？、？、？、？、？
以下のようにその行の全てのセルを既決にすることができます。
　　（決定可能状態）　■、■、■、□、■、■、□、□、□、□
次に左端が白に決定されている以下のような行で、検討をしてみます。
　　（検討開始状態）　□、■、？、？、？、？、？、？、？、？
この行の設定数列が［３，２］である場合に、少なくとも以下の部分まではセルの状態を決めることができます。
　　（決定可能状態）　□、■、■、■、□、？、？、？、？、？
Try３は、以上のようなセル状態決定方法を一般化して、上下左右の四辺に適用したものです。
本ソフトウエアでは、IsChangedByTry３というブール型のメソッドとして、この確定方法を実装しています。

Try４（しらみつぶし法）
Try４は、検討対象の行・列に対して、その設定数列に基づいてとり得る全てのケースの状態を調べて、 どのケースでも■（または□）であるセルを、■（または□）と確定していく方法です。
Try４の方法を説明する便法として、既にTry２で取り上げた列数１０、設定数列［２，５］の例をTry４の方法で検討してみます。
この問題の場合には、以下の６ケースがとり得る全てのケースになります。
　　　（ケース１）　■、■、□、■、■、■、■、■、□、□
　　　（ケース２）　■、■、□、□、■、■、■、■、■、□
　　　（ケース３）　■、■、□、□、□、■、■、■、■、■
　　　（ケース４）　□、■、■、□、■、■、■、■、■、□
　　　（ケース５）　□、■、■、□、□、■、■、■、■、■
　　　（ケース６）　□、□、■、■、□、■、■、■、■、■
上記６ケースで、全て■になるのは左から６〜８番目のセルであり、この位置のセルを■と決めることができます。
この例には、全て□になる位置のセルはありません。
行・列の数が小さいこの例ではTry２の方法でも処理できますが、行・列の数、ブロックの数が増えて Try２の方法では決められないような状況にもTry４の方法は対応することができます。
しかし行・列、ブロックの数が増えると、とり得る全てのケースの数は飛躍的に増加するため、 データ処理に多大の時間を要するようになります。
そこでTry４では、既決のセルが見つかっている場合には、既決のセルの状態に合致しないケースを除く方法をとります。
例えば、上記例で左から３番目のセルが既に■に決まっている場合には、リストアップしたケース１〜３は評価対象外にすることができ、 ケース４〜６のみで評価ができるようになります。
このように、既決のセルが多いほど評価対象のケースを絞ることができて、データ処理に要する時間を減らすことができるので、 できるだけ多くのセルを既決にしておくことが重要となります。
あとは、このアルゴリズムをプログラムに反映させれば良いことになります。
本ソフトウエアでは、IsChangedByTry４というブール型のメソッドとして、この確定方法を実装しています。

その他の処理方法
Tryを続けてセルの状態が確定していくごとに、各行・列の黒数合計と黒確定セル数とを比較し、 もし両者が一致した場合には、その行・列の未決セルを全て白色セルとして確定することができます。
本ソフトウエアでは、IsCrFinishedというブール型のメソッドとして、この確定方法を実装しています。

上図がパズル解法プログラムのフローチャート的流れ図です。
フローチャートの正しい記述方法にはなっていませんが、わかりやすさに重点をおいたので このように表したことをご了解ください。
後述するメイン画面の［実行］ボタンのクリックで解法プログラムは開始されます。

まず、アルゴリズムの項に記載したＴｒｙ１、Ｔｒｙ２が実行されます。
続いて、timespan（上図では［ｔｓ］）を０．１秒として、Ｔｒｙ３、Ｔｒｙ４のループ処理に入ります。
ここで timespan とは、Ｔｒｙ４を実行するときに使用する上限処理時間です。
Ｔｒｙ４では各行・列単位で可能性のあるケースをしらみつぶしに抽出していきますが、 行・列によってはケースの数が莫大となり、処理に長い時間が必要となります。
一方、それだけの時間をかけてもその行・列の状態が確定できるとは限りません。
そこで、１つの行・列の処理時間を timespan 以内として、その時間を超えた場合には その行・列の処理はとりやめにして、次の行・列に移るようにします。

Ｔｒｙ３、Ｔｒｙ４では、各処理過程で１つでもセルの状態が確定された場合にはtrueが返され、 １つも確定されなかった場合にはfalseが返されます。
そして、Ｔｒｙ３、Ｔｒｙ４のいずれもが false となったときに、その timespan でのセル確定が限界に達したことになるので、 timespan を増やして処理を続けます。
Ｔｒｙ３、Ｔｒｙ４では以下の事態に至ったときにループ処理は終了となり、パズル解きは終了または中止となります。
　１）　全てのセルの状態が確定され、パズルが完成したとき（上図の［completed］時）。
　２）　メイン画面左上方に表示される［キャンセル］ボタンがクリックされたとき（上図の［canceled］時）。

「MyIllustPuzzle」では、パズル画面のスペースが大きくとれるようにするため、パズルの状態を表示する画面（メイン画面）と、 パズルの問題に相当する設定数列の入力画面（初期設定画面）を別々に構成しました。
使用可能な最大行数は６０行、最大列数は１２０列です。

初期設定画面

この画面では、パズルの通常左部に表示されている行設定と、 パズルの通常上部に表示されている列設定との、設定数列を入力します。
入力された問題データは、［保存］ボタンでＸＭＬファイルに保存されます。
設定数列の入力後に［実行］ボタンをクリックしてメイン画面を開きます。
この画面では、新規入力分だけでなく、保存されている既入力データを［開く］ボタンで呼び出して、使用することもできます。

メイン画面
　　　　（左図：パズル開始時画面、右図：パズル完成時画面）


この画面で、［実行］ボタンをクリックしてパズル解きを開始します。
パズルの実行中、タスクバーに timespan、確定セル数、ループ回数、検査中の行・列番号が表示されます。
実行中のパズルは、画面左上に表示される［キャンセル］ボタンのクリックにより中止することができます。
パズルの完成後に、［確認］ボタンで結果が正しいことを確認します。
パズルの中断時、または完成時の状態は、［保存］ボタンにより保存することができます。保存ファイルの形式はＣＳＶファイルです。

評価テストに使用したパソコン
CPU：Intel Core2 CPU, 2.1GHz
RAM：1.9GB
OS：Windows XP Professional (SP3)

評価テストに使用したパズルの問題
パズル雑誌「イラストパズル」、「ロジックパラダイス」中の問題を使用してテストを行いました。

テスト結果
下表の８種のサイズのパズルを対象にして、全８５件の評価テストを実施しました。
サイズが50×50までのものは、パズルを完成させることができましたが、50×60サイズでは、 10件中3件が予定していた最大テスト時間（２時間）を越え、その時点で全セルの半分も確定できていなかったので、 テストを中断しました。
従って、今回使用したパソコンでは、50×60サイズ程度が本ソフトウエアで解を得られる限界と考えています。

ソースコードのダウンロード
Visual C# 2008(.NET Framework 2.0)で作成したプログラムのソースコードを公開します。
（2011.01.07 バグが見つかり、修正しました）

ご質問、ご意見、ご感想、バグ等のご連絡は、 こちらへ

トップページへ