MATLABでピクロス

DSのピクロスを借りてやってみたんですよ。
やってみると解き方が単純だったので、こりゃMATLABあたりで解くプログラム作れそうかな、と思ってやっちゃいました。

人間が解く場合、縦横のラインで確定しているマスを埋めていきますよね。
そこを、全組み合わせのうち、数字の列が一致するもののANDをとって埋めていく、って形で落とし込んでみました。
それだけでほとんど解けるわけですが、それだけだと確定するマスが無くなって、仮説・検証しないと解けない問題もあります。

それを解けるように仮説・検証のアルゴリズムも入れて、完成させました。
ほぼ必然的に、解を持たない問題や、解が一意に決まらない問題も判定できるようになりました。
そこで最後に、仮説・検証しないと解けない問題をしらみつぶしに調べてみました。

------------
% picros.m を使った、Fix法で解けないが解が一意に決まるピクロス問題を検索する
% テストmファイル。２×２～４×４を検索します。４×４以上にしかないけど。

clear

for PicDim = 2 : 4

SingleFixed = 0;
MultiPicros = 0;
MultiFixed = 0;
tois = PicDim^2;

mon = dec2bin( linspace( 0 ,2^tois -1, 2^tois) );

for cnt=1 : 2^tois
mondai = reshape(mon(cnt,:,:),PicDim,PicDim);
[x,y]=makepic(mondai);
[ans , state ] = picros( x,y );

if state == 'MF'
mondai
MultiFixed = MultiFixed + 1;
elseif state == 'SF'
SingleFixed = SingleFixed + 1;
elseif state == 'MP'
MultiPicros = MultiPicros + 1;
else
'ErrorPicros'
break
end

end

PicDim
SingleFixed
MultiPicros
MultiFixed

end
------------

代表的パターンは２×４で、
　　１
　２１
１□■
１■□
１■□
１□■

４×４の全組み合わせ65536のうち、確定するマスを埋めるだけで解けるのが51234、仮説・検証が必要なのが1124、解が一意に決まらないのが13178でした。
つまり、ランダムにマスを埋めてピクロスの問題にすると、２割が解けない問題になり、２％が仮説・検証が必要な難問になるわけです。（４×４の場合ですが）
問題を作るだけなら比較的簡単そうですが、うまいこと難問を作るのは難しそうですね。
感想として、ピクロスはただ解くこと、解法を作ること、問題を作ること、の三段階で楽しめるパズルと思いました。


ピクロス解答　picros.m
-------------
function [ ans , state ] = picros( x , y )
%picros ピクロスを解きます。
% ピクロス数列を受けて、解と状態を返します。
% 状態は、SF:Fix法のみで解けた、MF:Fix法では解けないが一意の解に至った、
% MP:複数の解があり、一意に解が定まらない、EP:解が存在しない、です。

sx = size( x , 1 );
sy = size( y , 2 );

pans = repmat( 'N' , sx , sy ) ;

[ ans , state ] = fixfil( pans , x , y );

if find( ans == 'N' )
for cnt = 1 : 100
[ ans , state ] = fixchance( ans , x , y );
if state == 'OK'
[ ans , state ] = fixfil( ans , x , y );
if length(find( ans == 'N' )) == 0
state = 'MF';
break
end
end
end
else
state = 'SF';
end


function [ ans , state ] = fixchance( ans , x , y )
%fixchance Fix法で解けないピクロス問題を、仮説と検証により判断します。
% 不明ピクロスを'N'で埋めたピクロス像とピクロス数列を受けて、解と状態を返します。
% 状態は、MP:複数解の可能性が発生した場合、EP:エラーピクロスが発生した場合、
% OK:仮説により、何らかのピクロスが埋まった場合。

kansN = find( ans == 'N' );
Ncnt = length( kansN );
state = 'OK';

for cnt = 1 : Ncnt
kans0 = ans;
kans1 = ans;
kans0( kansN( cnt ) ) = '0';
kans1( kansN( cnt ) ) = '1';

[ ans0 , state0 ] = fixfil( kans0 , x , y );
[ ans1 , state1 ] = fixfil( kans1 , x , y );

if state0 == 'NG' & state1 == 'OK'
state = 'OK';
ans = kans1;
break
elseif state0 == 'OK' & state1 == 'NG'
state = 'OK';
ans = kans0;
break
elseif state0 == 'OK' & state1 == 'OK'
state = 'MP';
break
else
state = 'EP';
break
end

end


function [ pans , state ] = fixfil( pans , x , y )
%fixfil ピクロス数列より確定するピクロスだけを埋めます。
% 不明ピクロスを'N'で埋めたピクロス像とピクロス数列を受けて、確定解と状態を
% 返します。状態は、エラーピクロスになるものだけをNG、ならないものはOKです。

sx = size(x,1);
sy = size(y,2);
state = 'OK';

dx = dec2bin( linspace( 0 ,2^sx -1, 2^sx) )';
dy = dec2bin( linspace( 0 ,2^sy -1, 2^sy) )';
[kari ,tmpy] = makepic(dy);
[kari ,tmpx] = makepic(dx);
tmpx = tmpx( 1:size( x,2 ) , : );
tmpy = tmpy( 1:size( y,1 ) , : );

for cnt = 1 :100
oldans = pans;

index = zeros(sy,1);
for cy = 1 : sy
ci = 0;
nofi = find( pans( : , cy ) == 'N' );
alfi = find( pans( : , cy ) ~= 'N' );
for ct = 1 : 2^sy
if tmpy(: ,ct) == y(: , cy)
if length(alfi) ~= 0
if dy(alfi , ct) == pans(alfi , cy)
ci = ci + 1;
index(cy,ci) = ct;
end
else
ci = ci + 1;
index(cy,ci) = ct;
end
end
end

utmp = dy( :, (index(cy,find(index(cy,:)))));
utmpl = utmp == repmat( '1' , size(utmp));
if size(utmp , 2) == 0
elseif size(utmp , 2) == 1
pans( : , cy ) = utmp;
else
nowfi = find(~any(utmpl'));
if length(nowfi) ~= 0
pans( nowfi , cy ) = utmp(nowfi);
end
nowfi = find(all(utmpl'));
if length(nowfi) ~= 0
pans( nowfi , cy ) = utmp(nowfi);
end
end
if ci == 0
state = 'NG';
break
end

end

%%%%%%%
index = zeros(sx,1);
for cx = 1 : sx
ci = 0;
nofi = find( pans( cx , : ) == 'N' );
alfi = find( pans( cx , : ) ~= 'N' );
for ct = 1 : 2^sx
if tmpx(: ,ct) == x(cx , :)'
if length(alfi) ~= 0
if dx(alfi , ct) == pans(cx , alfi)'
ci = ci + 1;
index(cx,ci) = ct;
end
else
ci = ci + 1;
index(cx,ci) = ct;
end
end
end

utmp = dx( :, (index(cx,find(index(cx,:)))));
utmpl = utmp == repmat( '1' , size(utmp));
if size(utmp , 2) == 0
elseif size(utmp , 2) == 1
pans( cx , : ) = utmp;
else
nowfi = find(~any(utmpl'));
if length(nowfi) ~= 0
pans( cx , nowfi ) = utmp(nowfi);
end
nowfi = find(all(utmpl'));
if length(nowfi) ~= 0
pans( cx , nowfi ) = utmp(nowfi);
end
end
if ci == 0
state = 'NG';
break
end
end

if oldans == pans
cnt;
break
end
end



function [ x , y ] = makepic( a )
%makepic ピクロス像を、ピクロス数列に変換します。
% ピクロス像はCHARの二次元配列で受けて、ピクロス数列は二次元の数列２つで返します。

[sx, sy] = size(a);
x= zeros(sx,sy);
y= zeros(sx,sy);

for cntx = 1 :sx
n = 1 ;
nn = 0;
for cnty = 1:sy
if a(cntx , cnty) == '1'
nn = nn + 1;
x(cntx,n)=nn;
elseif nn ~= 0
nn = 0;
n = n + 1;
else

end
end
end

for cnty = 1 :sy
n = 1 ;
nn = 0;
for cntx = 1:sx
if a(cntx , cnty) == '1'
nn = nn + 1;
y(n,cnty)=nn;
elseif nn ~= 0
nn = 0;
n = n + 1;
else

end
end
end