前回に引き続きイラストロジックの解答アルゴリズムを紹介します。
前回記事↓
前回記事では1マスの解答パターンを「○」「・」「●」の3種類を分けて説明していましたが、これらの3種類の解答を数字とおいて行列演算で解答アルゴリズムを構築していきます。
行列演算を行うことでより高速に計算を処理することができます。
なぜなら、前回記事における「○」「・」「●」はそれぞれを判定するためにプログラム上では文字列操作で行う必要があり、1つ1つのマスを検証したりする必要があります。代わりに行列演算だとそれらを一括で行えたりします。
またプログラムのコード自体もより簡略化することができます。
具体的に数字に置き換えるのは次の通りです。
白マス「・」=0
未確定マス「○」=1
黒マス「●」=2
前回記事における初回解答の図1は次のようになります。
図1：初回解答
具体的に追加解答でのアルゴリズムは次のようになります。
図2：追加解答(黒マスが追加、該当数字が1つ) その1
追加解答に該当する数字3のパターン行列に計算を適応します。
解行列A、パターン行列Cとおき、CAにおいて最大値と一致する要素が有効(OK)で、それ以外を無効(NG)と判定できます。
有効、無効をもとに無効化行列Dを作成します。
DCを計算するとパターン行列で無効な行を0にしたC'が計算されます。
C'において行合計行列QをかけてC'Qを計算すると、C'の各行での合計が計算されます。このC'Qの総和を数字(=3)で割った値が有効パターンの数となります。
列合計行列PとC'をかけてPC'において0の要素は白マス「・」、有効パターン数と一致する要素は黒マス「●」、それ以外は未確定マス「○」となります。
以上で1つの数字におけるパターン行列に新しい追加解を適応して新しい解を出力できます。
追加解がほかの数字に該当する場合は次のようになります。
図3：追加解答(黒マスが追加、該当数字が1つ) その2
次に追加解が白マス「・」の場合も考えます。
先ほどの演算と同様に計算することができます。
図4：追加解答(白マスが追加、該当数字が1つ) その1
次は数字の解答範囲(開始位置、終了位置)がずれる場合の演算です。
図5では数字のパターン行列をもとに開始位置、終了位置を計算しています。
図5：パターン行列から開始位置、終了位置を計算 その1
連番基本行列B、逆連番基本行列B'を用意します。
終了位置はBC'Qの最大値を数字で割った値で求まります。
開始位置はB’C'Qの最大値と解答パターン個数などを利用して求まります。
なお、開始位置はBC'Qの最小値で求まりそうな気もしますが、これは演算上必ず最小値は0になってしまうので一工夫しています。
図5ではわかりにくいと思いますので、より大きなパターン行列での計算例は図6のようになります。
図6：パターン行列から開始位置、終了位置を計算 その2
ここで出てきた行合計行列Q、列合計行列P、連番基本行列B、連番逆基本行列B'はプログラムの中では最初に用意しておいて、大きさを指定して必要な時に呼び出すことで計算を高速化することができます。
またmax,sumなどはVBAでの標準の関数を利用することができます。
イラストロジックの解答アルゴリズムの紹介は以上です。
実際に開発したプログラムは技術流出の懸念から公開は致しません。
興味のある方は直接ご連絡ください。
Twitter
あと、詳しく調べていませんが今回紹介したアルゴリズムはどこにも転がっていなかったので、あわよくばまだ誰も発表していないものかもしれません。
自分で論文で出すのはめんどくさいので、共著で論文出したいって人もまた連絡ください。
PR
ExcelVBAでのツール開発を承っております。（対応実績350件以上 2023.8月）
お気軽にご相談ください。
