TurnOver Ver3 の結果 2000.05.13 deepgreen ライツアウトのアプローチを８めくりパズルに適用した結果の報告です。 （１）８めくりパズルの解を計算する式 （２）実際に、解を求めるまでの時間の測定 □８めくりパズルの解を計算する式 ルールが少し違うので連立式が変わりますが、基本的には同じです。 ［８めくりパズル］ ［ライツアウト」 □□□ ■■■ □□□ □■□ □■□ ==> ■□■ □■□ ==> ■■■ □□□ ■■■ □□□ □■□ ［４ｘ４の場合の連立式］ 式xx pushパターン 問題面 1 -2--56---------- a--------------- 2 1-3-567--------- -b-------------- 3 -2-4-678-------- --c------------- 4 --3---78-------- ---d------------ 5 12---6--90------ ----e----------- 6 123-5-7-901----- -----f---------- 7 -234-6-8-012---- ------g--------- 8 --34--7---12---- -------h-------- 9 ----56---0--34-- --------i------- 10 ----567-9-1-345- ---------j------ 11 -----678-0-2-456 ----------k----- 12 ------78--1---56 -----------l---- 13 --------90---4-- ------------m--- 14 --------901-3-5- -------------n-- 15 ---------012-4-6 --------------o- 16 ----------12--5- ---------------p ［４ｘ４の場合の連立式の解］ 式xx pushパターン 問題面 1 1-----------345- ---d-fgh-j------ 2 -2----------3-56 --c-ef-hi-k----- 3 --3---------34-6 -b--e-gh-j-l---- 4 ---4---------456 a---efg---k----- 5 ----5-------3-5- -bcd-f-h-jkl---- 6 -----6---------6 ab-de---ij-l---- 7 ------7-----3--- a-cd---hi-kl---- 8 -------8-----4-6 abc-e-g-ijk----- 9 --------9-----56 -b---fgh---l---- 10 ---------0---456 a-c-ef-h--k----- 11 ----------1-345- -b-de-gh-j------ 12 -----------234-- --c-efg-i------- 13 ---------------- abc-e-g---klm--- 14 ---------------- a-cd---h-jkl-n-- 15 ---------------- ab-de---ijk---o- 16 ---------------- -bcd-f-hij-----p 実際の８めくりパズルは、すべての位置を反転するというゲームなので、 ａ，ｂ，．．．ｐ＝１となり、式13〜式16は０＝０になります。 最終的には、以下の式になります。 式xx push位置 計算式 1 1--------------- 345- +(1) // ---d-fgh-j------ 2 -2-------------- 3-56 +(0) // --c-ef-hi-k----- 3 --3------------- 34-6 +(0) // -b--e-gh-j-l---- 4 ---4------------ -456 +(1) // a---efg---k----- 5 ----5----------- 3-5- +(0) // -bcd-f-h-jkl---- 6 -----6---------- ---6 +(1) // ab-de---ij-l---- 7 ------7--------- 3--- +(1) // a-cd---hi-kl---- 8 -------8-------- -4-6 +(0) // abc-e-g-ijk----- 9 --------9------- --56 +(1) // -b---fgh---l---- 10 ---------0------ -456 +(0) // a-c-ef-h--k----- 11 ----------1----- 345- +(0) // -b-de-gh-j------ 12 -----------2---- 34-- +(1) // --c-efg-i------- 13 ------------3--- 3--- 14 -------------4-- -4-- 15 --------------5- --5- 16 ---------------6 ---6 x13−x16を決めると、他の変数は自動的に上記の式で求まります。 □ 実際に、解を求めるまでの時間の測定 ［サイズ］ 最小手数 探索時間（秒） 以前の結果 24 x 24 276 0.75 d=4 487 sec 26 x 26 396* 1.3 2834 28 x 28 428* 1.7 11256 30 x 30 384* 2.0 １３.５Ｈ 32 x 32 448* 2.7 ７６ Ｈ 34 x 34 568 4.0 d=4 36 x 36 700* 5.1 38 x 38 608* 7.1 40 x 40 624* 9.0 42 x 42 852* 12.1 44 x 44 880 22.4 d=12 46 x 46 1056* 21.5 48 x 48 1088* 25.4 50 x 50 1052 171 d=16 52 x 52 1324* 43.6 注：＊は解が１つしか存在しない。 ｄ＝ｎ：制約のない自由変数の数（ｄ＝０の場合は、unique解） ３２ｘ３２を３日ががりでやっと解いたものが、わずか３秒たらずで 解けてしまったのは驚きです。 （おわり）