[WP]no.017 お絵かきロジック解法

お絵かきロジック(おえかきロジック)は、縦と横の数字をヒントに塗り潰すマス目を割り出し、そのとおりに塗り潰していくと、最終的に絵(または文字)が浮かび上がるタイプのペンシルパズル。ののぐらむ、イラストロジック、ピクロスとも呼ばれている。


引用:2015/09/21 Wikipedia https://ja.wikipedia.org/wiki/%E3%81%8A%E7%B5%B5%E3%81%8B%E3%81%8D%E3%83%AD%E3%82%B8%E3%83%83%E3%82%AF

お絵かきロジックの基本的なルール等の説明は放棄。Wikipediaに載ってます。

特に捻った解法など無し。「基本的なルール」をそのままコンピュータがやるだけです。

しかし、基本的なルールに乗った解法でも解けない問題が存在します。
「直感」と「運」が要求される問題で、普通に人が解いても消しゴムで全消し、なんてよくあります。
こうなったらブルートフォースか人工知能を実装するくらいでしょうか。
人が介入する作戦もアリかもしれません。


全体を解くプログラムは載せず、根幹部分だけの実装。

言語はHSP3。変数確保等面倒なことを考えなくて済む・グラフィカルに確認するときは有利な言語だから。


次のようなプログラムを考えます。


35|??????????
       ↓
35|?■■??■■■■?

35|???■?????? 一部が既に確定済み
       ↓
35|□■■■□■■■■■


やや無駄が多い記述。
実はこのプログラムは正確ではない。後述。
#cmpopt varinit 1

// マスの数
size=10
// 現在のセルのマスの状態
// -1未確定 0空白 1ブロック
cell=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
// 埋めるブロックのサイズ
fill=3,5

//size=10
//cell=-1,-1,-1,1,-1,-1,-1,-1,-1,-1
//fill=3,5

//size=15
//cell=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
//fill = 4,5,2

// -------------------------------------

nfill=length(fill)

// fillだけでどれだけ占有するか
sp=-1
repeat nfill
sp++
sp+=fill.cnt
loop
sp = size - sp // 余裕

if (sp<0) : mes "warning" : stop
if (sp==0) : mes "nothingToDo": stop // ぴったり

dim offset,nfill
dim temp,size

lpc=0
offset.0 = -1
repeat
if (sp <= offset.(nfill-1)) :break

offset.0++
// 桁上げ
repeat nfill-1
if (sp < offset.cnt){
offset.cnt=0
offset.(cnt+1)++
}
loop

// 和
s=0
repeat nfill
s+=offset.cnt
loop
if (sp < s):continue

// cell check
i=0 : f=0
repeat nfill
// 空ける所がブロックで確定していたら×
repeat offset.cnt
if (cell.i==1):f=1
i++
loop
repeat fill.cnt
// 埋める所が空白で確定していたら×
if (cell.i==0) : f=1
i++
loop
// 空ける所がブロックで確定していたら×
if (i<size):if (cell.i==1) : f=1
i+=1 // スペース
loop

if (f) : continue

// 加算する
i=0
repeat nfill
i+=offset.cnt
repeat fill.cnt
temp.i++
i++
loop
i+=1 // スペース
loop

//offset表示
//t=""
//repeat nfill
// t+=strf("%d ",offset.cnt)
//loop
//logmes t

lpc++
loop

if (lpc==0):mes "warning:lpc=0" : stop
if (lpc==1){
// 確定
repeat size
cell.cnt = (temp.cnt==1)
loop
}else{
// 部分的な確定
repeat size
if (temp.cnt == lpc) : cell.cnt=1
loop
}

t=""
repeat size
switch cell.cnt
case -1
t+="?"
swbreak
case 0
t+="□"
swbreak
case 1
t+="■"
swbreak
default
t+="XX"
swend
loop
mes t

stop


offset配列はこんな感じ
数字(fill)が3・4、全体の大きさ(size)が10の時、次の状態をとる
offset| 想定するセルの状態
0 0 |■■■□■■■■□□
1 0 |□■■■□■■■■□
2 0 |□□■■■□■■■■
0 1 |■■■□□■■■■□
1 1 |□■■■□□■■■■
0 2 |■■■□□□■■■■
よく見ると3進数っぽい挙動してますね。そんな感じの実装です。
ただし、offsetの合計は余裕(自由度sp)以下でなければならないので、条件外ならcontinueさせます。

「// cell check」は、既にcell配列にセットされている事実と矛盾が無いかチェックします。
offsetに従って塗りつぶしていったとき、塗りつぶそうとしているセルが塗りつぶしてはいけないセルだったりした場合、矛盾と判定し、continueさせます。

塗りつぶす点を1、塗りつぶさない点を0として、それぞれのセルに対して、全ての状態の合計を求めます。
数字(fill)が3・4、全体の大きさ(size)が10の時
3 4 |3563236653

offsetの状態の数は6。
合計が6のマスは「全ての可能性でそのブロックが塗りつぶされる」はずです。



実はこのプログラムは不完全だったり。
次の状態を実行すると不完全さに気づきます。
	
size=15
cell=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1
fill = 4,4,2

セルが次の状態の時、確定するはずですが、片方しか実装していません。
全ての可能性を網羅した時、
●全ての可能性でそのブロックが塗りつぶされる。
○全ての可能性でそのブロックが塗りつぶされない。
が確定するはずですが…

「// 確定でないので候補」周辺に次の記述を挿入すると解決します。
if (temp.cnt == 0) : cell.cnt=0


「ここに書くまで気が付かなかったんじゃないの?」という勘の鋭い思考は不要です。



2015/09/22 追記

まだ穴があった…
次のパターンもうまくいきません。
	size=15
cell=-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1
fill = 5


cellcheckが完全に網羅できてなかったようです。
「cellcheck」の「repeat nfill ~ loop」の後ろに追加します。

while (i<size)
// 空ける所がブロックで確定していたら×
if (cell.i==1) : f=1
i+=1 // スペース
wend
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : HSP3 アルゴリズムとデータ構造

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1467位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
265位
アクセスランキングを見る>>