*** 2000-09-05 高橋謙一郎さんのＨＰ（掲示板）に投稿　***
       
０解から最長手数解を求める方法です。

ライツアウトの解の存在条件式のパターンと０解のパターンが一致することが
前提知識となります。（私のＨＰを参照してください）

５ｘ５のライツアウトの０解は、以下の３パターンである。
  　(p1)  -BCD-F-H-JKL-NOP-R-T-VWX-
    (p2)　A-C-EF-H-J-----P-R-TU-W-Y
    (p3)  AB-DE-----KL-NO-----UV-XY
p1,p2,p3は互いに独立ではなく、他の2つのＸＯＲにより求めることができる。

ｐｕｓｈ位置のＡ〜Ｙを以下のように分類する。
　（１）p1,p2,p3のいずれにもでてこないもの　：G,I,M,Q,Sの５個
　（２）p1,p2に共通にでてくるもの　　　　　 ：C,F,H,J,P,R,T,Wの８個　
　（３）p2,p3に共通にでてくるもの　　　　　 ：A,E,U,Yの４個
　（４）p3,p1に共通にでてくるもの　　　　　 ：B,D,K,L,N,O,V,Xの８個

最長手数の解を考えると、
（１）は無条件に１にすればよい（∵解の存在には関係ない）
（２）は、丁度半分を1にすることができる。半分を超えているものは０解
　　　とのＸＯＲにより半分未満の解が存在することになるので、丁度半分
　　　が最大となる。
（３），（４）も同様である。
なお、(2),(3),(4)を丁度半分づつ１にしたものは、解の存在条件をみたして
いることは明らかである。

よって、最長手数は、５＋８／２＋４／２＋８／２＝１５となる。

次に、最長手数解の個数について考える。
（２）の候補の選び方は、８個から４個選ぶ組み合わせ＝8！／４！＝７０
（３），（４）もそれぞれ、４！／２！，８！／４！となる。
全体としては　６ｘ７０ｘ７０＝２９４００パターン

これは、ｐｕｓｈパターンの数であるから、問題面の数としては、この１／４
になる。

　　　２９４００／４＝７３５０通り

これは、広井さんの探索結果と一致する。

参考までに、最長手数解を示す。
　　　（ｐｕｓｈパターン）　　　（問題面）
　　　　　１１１１１　　　　　　　１０００１
　　　　　１１１１１　　　　　　　０１１０１
　　　　　１１１００　　　　　　　１１１１１
　　　　　０１０１０　　　　　　　００１１１
　　　　　０００００　　　　　　　０１０１０