特攻隊

RPGツクール、パズル、プログラミング等々。

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
※パズルを解く為のヒントとなり得るかどうかは微妙です。
 読み物としてお楽しみ下さい。



あるパズルの状態が、解けている状態か、解けていない状態か、の
判定方法について考える。

今回は「スタンプ」については考えない。

以後、オムレツを○、魚を△、肉を×で表す。




「キャロル先生」では、5×5のフィールドを使っているが、
簡略化の為に、まず始めに、2×2のフィールドで考えてみる。

2×2のフィールドの場合。オブジェの座標を次の文字で定める。


a b
c d


a、b、c、dには、○、△、×のいずれかが入る。

このa、b、c、dに○、△、×を代入したとき、そのパズルの状態が
解けた状態か解けてない状態かは、次の条件で判断出来る。



・解けた状態
 aとb、aとc、bとd、cとdのいずれかが同じオブジェ……(i)

・解けてない状態
 上記以外



ここで、解けてない状態について着目してみる。

「キャロル先生」では、オブジェが3つしか出てこないから、
a、b、c、dの4つのうち少なくとも2つは同じオブジェである。

しかし解けてない場合、その2つの配置は、(i)を満たしてはならないので、
同じオブジェがあるならば、その位置の組み合わせはaとdまたはbとcである。

そして、aとdが同じオブジェであった場合、b、cは
それと同じオブジェであってはならないし、

bとcが同じオブジェであった場合、a、dは
それと同じオブジェであってはならない。


…以上を簡単に書くと、↓の様な状態が解けてない状態である。


○△   ○△
×○   △○



このような状態を、「ねじれ状態」と呼ぶ事にする。


ちなみに、逆の解けている状態は↓こんな感じの状態。

○○   ○○   ○○   ○○
○○   ○△  △△  △×



2×2のフィールドのパズルが解けていないことの必要十分条件は、
そのフィールドがねじれ状態になっていることである(ねじれ状態の定義)



さて、ここでフィールドを5×5に拡張してみる。
座標を次のように定める。


(1.5) (2.5) (3.5) (4.5) (5.5)
(1.4) (2.4) (3.4) (4.4) (5.4)
(1.3) (2.3) (3.3) (4.3) (5.3)
(1.2) (2.2) (3.2) (4.2) (5.2)
(1.1) (2.1) (3.1) (4.1) (5.1)


ここで、文字p.q.r.sを導入し、

(p.q) (r.q)
(p.s) (r.s)

の4つの組について考える。(条件:1≦p<r≦5 かつ 1≦s<q≦5)

この4つの組は、
フィールドの水平方向、鉛直方向を辺に持つ長方形の四隅を形作る。
(以降、この条件を満たす長方形を、単に「長方形」と呼ぶことにする)

イメージ的には↓こんな感じ。(p=2、q=4、r=5、s=2の場合)


p  r
○○○○○
○×○○× q
○○○○○
○×○○× s
○○○○○


(×が(p.q)(r.q)(p.s)(r.s)を表す)


たしかに×が長方形の四隅を形作っている。

ここで、この

(p.q) (r.q)
(p.s) (r.s)

を2×2のフィールドに見立てて、これらがねじれ状態のとき、
この(p.q)(r.q)(p.s)(r.s)を含む5×5のフィールドが、
解けた状態となり得るかどうかを考えてみる。

5×5のフィールドが消えて行く過程を考える。

消えて行く過程で
この4つのタテ座標の一致、ヨコ座標の一致が崩れる事がないのは
明らかなので、

この4つのどれかが初めて消えるとき、それは

・(p.q) (r.q)が一緒に消える(ヨコ消し)
・(p.s) (r.s)が一緒に消える(ヨコ消し)
・(p,q) (p.s)が一緒に消える(タテ消し)
・(r.q) (r.s)が一緒に消える(タテ消し)

のいずれかの場合に限られる。

この4つの場合のどの場合をとっても、
(p.q) (r.q)
(p.s) (r.s)
がねじれ状態になる事は無い。

よって、5×5のパズルが解けた状態である為には、
(p.q) (r.q)
(p.s) (r.s)
はねじれ状態であってはならない。

p.q.r.sは、1≦p<r≦5 かつ 1≦s<q≦5 の範囲で
任意の値をとり得るので、この範囲で(p.q.r.s)のとり得る場合の数を
計算すると、


5C2 × 5C2 = 100通り
(計算が難しい人もいるかも知れないが、さして重要ではないので、
 たくさん長方形が作れるんだな、程度に理解してくれればOK)


つまり、パズルが解けた状態である為には、
フィールド上に作れる100通りの長方形の四隅のうち、
どれもがねじれ状態であってはならない。



これで、次の命題が真であることが証明された。

命題A
パズルが解けた状態である ⇒ フィールド上の任意の長方形の四隅がねじれ状態ではない




さて、この命題は、直感的にも分かりやすい事実だが、
実はこの命題、逆も成り立つ。つまり


命題B
フィールド上の任意の長方形の四隅がねじれ状態ではない ⇒ パズルが解けた状態である


もまた真である。こちらは直感的には真偽の判断はつかないだろう。
これも成り立つことをこれから示す。



続きは次回。
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://mozuku88.blog134.fc2.com/tb.php/103-48b40e8f
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。