ＸＯＲ開発チームによる「XORの法則」

　本家のＸＯＲ開発チームがゲーム制作中の1985年頃に、XORに関して見つけたという法則を教えていただきました。それを紹介します。

　■「XORの４歩則」　(ＸＯＲ開発チーム)

「XORの４歩則」
　XORのある面がn歩の解を持つとする。この時、この面はn-4歩で解ける可能性はあるが、n-3歩、n-2歩、n-1歩で解けることはありえない。

【略証】

XORのある面の道の部分を、出発点が白となるような白黒市松模様の上にかぶせることを考える。
たとえば１面目であれば

××××××××××××××× ××××××黒白黒×××××× ××××××白×白×××××× ×白黒白黒白黒白黒白黒白黒白× ×黒××××白×白××××黒× ×白黒白黒白黒白黒白黒白黒白× ××××××白×白×××××× ××××××黒×黒×××××× ××××××白黒白×××××× ×××××××××××××××

とする。ここで、白いマスの数をw、黒いマスの数をbとおく。この面をn歩で解いた際のXOR坊やの
移動経路は、必ず「黒白黒白…」となり、その長さがnであるということである。
ここで、移動経路の黒の個数をbb、白の個数をwwとおくと、bb=wwもしくはbb=ww+1であり、かつ、
ある非負整数xおよびyについて bb=b+2x、ww=w+2y-1 が成立する。

case 1) bb=wwのとき:	n = bb+ww = 2b+4x = 2w+4y-2
case 2) bb=ww+1のとき:	n = bb+ww = 2b+4x-1 = 2w+4y-1

したがって、非負整数xとyを考慮に入れるならば、nは4つ飛びの値しか取りえない。Q.E.D.

　■「XORの歩数の下界」　(ＸＯＲ開発チーム)

「XORの歩数の下界」
　XORのある面の道の部分を、出発点が白となるような白黒市松模様の上にかぶせ、白いマスの数をw、黒いマスの数をbとおく。この時、この面をクリアするための歩数は、

　w+bが偶数のとき、w+b-1+abs(w-b)
　w+bが奇数のとき、w+b-1+abs(w-b-1)

を下回らない。[abs(x)はxの絶対値]

【略証】

　この面がn歩で解けたと仮定すると、n≧w+b-1は自明である。
この時のXOR坊やの移動経路における黒の個数をbb、白の個数をwwとおくと、
bb≧bおよびww≧w-1より、n=bb+wwに関して、以下が成立する。

case 1)	w+bが偶数のとき　nが奇数となることから、bb=ww+1である。よってn=2bb-1=2ww+1となり、　n≧2b-1かつn≧2w-1といえる。∴ n≧w+b-1+abs(w-b)
case 2)	w+bが奇数のとき　nが偶数となることから、bb=wwである。よってn=2bb=2wwとなり、　n≧2bかつn≧2w-2といえる。∴ n≧w+b-1+abs(w-b-1)

(補足)
１面目はw=23,b=19であるから、45歩を下回らない。したがって、現在の制限歩数45は、
クリアするための歩数の下限であり、これ以下に縮まることはありえない。

　■　補足説明　(ｔａｋａｋｅｎ)

　「XORの４歩則」に関して、ここでは「ＸＯＲの開始局面は出発点(白マス)の１ヶ所だけが既に塗られている」という前提で説明されています。だから、黒いマスでは bb=b+2x であるのに対し、白いマスでは ww=w+2y-1 と白マスが既に塗られている分 -1 が付きます。
ちなみに、この等式をもっと親切にクドクドと書き直せば、こうなります。

ある非負整数xおよびyについて bb=b+2x、ww=w+2y-1 が成立し、

case 1) bb=wwのとき: 　n = bb+ww = bb + bb = b+2x + b+2x = 2b+4x
　n = bb+ww = ww + ww = w+2y-1 + w+2y-1 = 2w+4y-2

case 2) bb=ww+1のとき: 　n = bb+ww = bb + bb-1 = b+2x + b+2x-1 = 2b+4x-1
　n = bb+ww = ww+1 + ww = w+2y-1+1 + w+2y-1 = 2w+4y-1

　尚、出発点の１ヶ所だけが既に塗られているという条件を外しても、4つ飛びの値しか取りえないことに変わりはありません。
　また、「XORの歩数の下界」についても、case 1) の場合を使ってもっとクドクドと書き直せば、こうなります。

case 1)

　w+bが偶数のとき
　白マスの１つが既に塗られているのでnは奇数であり、
　実際の経路は「黒白黒白……黒白黒」となるので、bb=ww+1である。

　　　n = bb + ww = bb + bb-1 = 2bb-1
　　　n = bb + ww = ww+1 + ww = 2ww+1

　ここで、bb≧bおよびww≧w-1であることから、さらに、

　　　n = 2bb-1 ≧ 2b-1
　　　n = 2ww+1 ≧ 2w-1

　といえる。n≧2b-1かつn≧2w-1ということは、n≧max(2b-1,2w-1) である。
　　[max(x,y)はxとyのうち大きい方の値を取る]
　これを一般式 max(x,y)=(x+y+abs(x-y))/2 で展開すると、
　n≧w+b-1+abs(w-b) が得られる。

　この下界値は「解ける可能性のある最小値」になっているので「XORの４歩則」と合わせて、
歩数の下界値をLBとすると解となる歩数nは、n=LB+4i (iは整数) という式で表すことが出来ます。
もちろん、LBは数理上の下界値であり、実際の最短経路値ではありません。

　また、総ての道が1回の通過で済む順路が存在したときの歩数は、w+b-1 なので、
wまたはbのうち少ない方の地点を、どうしても3回通らなければならない箇所は、

　　w+bが偶数のとき、abs(w-b)/2 ヵ所
　　w+bが奇数のとき、abs(w-b-1)/2 ヵ所

必要ともいえます。この地点を「整合点」と呼ぶことにし、整合点は交差点でなければならない。
何故なら通路に整合点があった場合、その地点に隣接するいずれかのマスも必ず3回通ることに
なり、これでは整合性が改善されない。１面目で言えば、黒マス交差点のうち２ヵ所に整合点
を持たせる必要がある。整合点以外の場所を3回通れば、それと異なる色のマスのどこかも3回
通って整合性を保つ必要が出てきます。

　ホームページへ戻る　恐怖の1000面パズル「XOR」を解くへ戻る