パズルを解くことは知的好奇心を掻き立てる意味で好きでが、パズルを解くアルゴリズムを考えことも好きです。
お絵描きロジック
ロジックパズルの一種で、お絵描きロジック、イラストロジック、ノノグラムなどと呼ばれているパズルがあります。
マス目の縦と横の数字の列があり、ある規則に従って、マス目を塗って行くと、モザイクのイラストが現れるもの。
10年以上も前に、そのパズル本を買い、自分で解きながら、プログラムでも解けるのではと思っのが始まり。雛形を作ったのは良いけど、結局全然とけません。その後、ずっと放置してましたが、この年末何時、コロナ禍にあってどこにも行けないので、時間の浪費とは思いつつ、つい、パズル雑誌に手を出してしまいました。
作りっぱなしの解法プログラム(未完)
ルール概説
各行列毎に、
・数字が連続すること黒のマス目の数を表す。
・複数の数字がある場合は、その順番通りに塗って行く。
・数字と数字の間は、1マス以上の白マスを置く
を満足する様に、黒マスと白マスを決定する。
詳しくは、
解法アルゴリズムの枠組み
パズルの解き方の説明として、色々紹介がありますが、アルゴリズムの形に変換するのは意外と大変です。
基本は、
・一行/一列単位で考えられる解法
・行と列の組合せで考えられる解法
・(多分)ある仮定を置いて、矛盾の有無を調べて決定する解法
があり、一マス塗れたら全ての解法を試してみて、それをくり返すということになります。
単一の解法でも、黒(塗れるか)の場所を確定するものと、白(塗れない)の場所を確定するものち分けられます。
プログラム作成
これから、ひとつずつ解法をアルゴリズム化していき、解法プログラムを作って行く予定。
目標は、100マス×100マスのパズルが解けること。かなり、難しいですけどね。