Rubicキューブのシミュレータ

Winning WaysのRubicキューブの直し方(curing)が分ってきた. 実はその理解のために今回のシミュレータを書いたような次第だ.

島内本では6つの面をtop, north, east, south, west. bottomというが, 今回はWinning Ways流(というかDavid Singmaster流)にUp, Back, Right, Front, Left, Downとする.

各面の回転は時計まわりにU,B,R,F,L,D; 反時計まわりにはU',B',R',F',L',D'. またWinning Waysの説明には, 真ん中の段の回転もあり, それにはギリシア文字α,β,δ,γ,ε,ωを使う. εとωはeastとwestのようで覚えやすい.



このブログでは, 各小体の面を下の図の左のように表す.



右の図は操作の順で, まず下段の辺の2面体Aから始めEへとステージを進める.

A) Aの2面体を向きも合わせて定位置に置く.
B) Bの3面体を向きも合わせて定位置に置く.
C) Cの2面体を向きも合わせて定位置に置く.
D) Dの2面体を定位置に置く. 向きは気にしない.
E) Eの3面体を定位置に置く. 向きは気にしない.
F) Dの2面体とEの3面体の向きを合わせる.

Winning Waysではこれらの各ステージを

A) Aloft, Around (Adjust) and About.
B) Bottom Layer Corner Cubelets.
C) Central Layer Edge Cubelets.
D) Domiciling the Top Edge Cublets.
E) Exchanging Pairs of Top Corners.
F) Finishing Flips and Fiddles.

という.

ステージA) 下段は操作しにくいから, 上段のDの位置に集めてから各側面を回転してAに置く. Aのステージは簡単で, Aloft, Aroundなどはあまり関係ない.

ステージB) すでに置き終えたAの2面体に影響しないようにBの3面体を置く. 例えば面の図のpsの3面体(矢印の先)を置くには, それが上段にあればcnq の位置に来るように上段を回転し, 底の面の色がqにあればB1, nにあればB2, cにあればB3を実行する. 3面体が下段にあればいづれかの操作で上段に上げてから今の操作を行う.



図A) B1:F'U'F 底の面の色がqにあるとき
図B) B2:RUR'底の面の色がnにあるとき
図C) B3:F'UFRU²R' 底の面の色がcにあるとき

3面体が下段に移る他, orの2面体や上段のキューブにも影響があるが, そこは後で処理するので問題ではない.

ステージC) etかblにあるDの2面体をorのC(矢印の先)に移動する. 下段が揃っているから, 単純な面の回転は出来ない.



図D) C1:URU'R'U'F'UF oの色がUの面にあるとき
図E) C2:U'F'UFURU'R' rの色がUの面にあるとき

ここまでで下段と中段が揃う. この後は上段の2面体Dと3面体Eの入れ替えになる.

ステージD) 上段の2面体etとgを交換する.



図F) D1:UFRUR'U'F' 2面体bl, 3面体ai, cnq, hvも替わったように見えるが, これらは向きが替わっただけで, 位置は前のままである. 上段の2面体, 3面体の向きは最後のステージFで修正するから, 今は気にしない.

ステージE) 3面体cnqとhvを交換する(mono swapという).



図G) 1月22日のブログのG)巡回 で3面体aiがcnq, cnqがhv, hvがaiに移動している. これを3面体の交換2回でもとに戻す.
図H) 上段のT'の回転.
図I) E:FDF²D²F²D'F'=M_sを実行. Hの赤丸と青丸の3面体を交換した. 中段と下段にも変化があるが, 上段はこの2つが変わっただけなのに注意.
図J) 上段のT'の回転.
図K) E=M_sを実行. Jの赤丸と青丸の3面体を交換した. 上段の3つの3面体は希望の位置に移った. M_s²=1なので, 中段と下段がもとに戻ることに注意.

ステージF) 上段の3面体と2面体の向きを合わせる.

3面体の場合


図L) 1月22日のブログのH)ねじり で3面体cnqが時計回りに, hvが反時計回りにねじれている.
図M) F1=(F'RFR')²=M_aで3面体cnqを反時計回りに回転する. 中段と下段にも変化があるが, 上段はこの3面体が回転しただけなのに注意.
図N) 上段のT'の回転.
図O) F2=(RF'R'F)²=M_cで時計回りに回転する. 中段と下段はM_aM_c=1で元に戻る. 後は上段をT回転する.

2面体の場合


図P) F)隣辺向き替え で2面体blとetの向きが反転している.
図Q) F2=(εR)⁴=M_eでblを反転する.
図R) 上段をT'回転する.
図S) F2=M_e を実行する. 中段と下段はM_e²=1で元に戻る. 後は上段をT回転する.

この方法はM_s²=1, M_aM_c=1, M_e²=1をうまく利用していて面白い.

Rubicキューブのシミュレータ

シミュレータが出来たので島内先生の本の6面体完成術を実装することにした.

今回はその大体のやり方を書くことにしよう.

島内流にいうとRubicキューブには26個の小体があり, その内訳は隅にある3面体8個, 辺にある2面体12個, 面の中央にあり動かない1面体6個とである.

島内流の完成術は
A. 3面体を向きは無視して正規の位置に移す.
B. 2面体を向きは無視して正規の位置に移す.
C. 2面体の向きを揃える.
D. 3面体の向きを揃える.
である.

この各手順で主に使われるのが, 1月22日のブログにあった
E) 単純3角形 9a(Bで使う)
F) 隣辺向き替え24a(Cで使う)
G) 巡回 28a(Aで使う)
H) ねじり 33a(Dで使う)
の操作である.

まず6面の色を番号で表す.
上t 0(白)
北n 1(緑)
東e 2(橙)
南s 3(黄)
西w 4(赤)
下b 5(青)

隅(赤字で示す)と辺(青字で示す)も番号で表す.

3面体は正規の位置での3つの色を昇順に並べて表す. 隅番号0,1,2,...にある3面体は順に
[012],[023],[034],[014],[125],[235],[345],[145]

2面体は正規の位置での2つの色を昇順に並べて表す. 辺番号0,1,2,...にある2面体は順に
[01],[02],[03],[04],[12],[23],[34],[14],[15],[25],[35],[45]

現在 隅0にある3面体を知るには, 54の面の色のリストから0,15,18の位置の色をとりだし, 昇順にソートする. こうして8つの隅にどの3面体がいるかが分る.


[ランダムにした出発点]

Aの手順では, [012]を隅0に戻すことから始めて, 隅7まで戻すことである. 最初の頃は間単だ. たとえば[012]が隅番号n=0,1,2,3の何れかにあれば, 面tをnだけ左回転する. n=4,5,6,7なら面bをn-4だけ右回転し隅4に置き, 面eを左回転する.

[023]は隅2にいれば, 面sを右回転. 3にいればw右, s右だ. n=4,5,6,7なら(n+3)%4だけ右回転して隅5へ移し, sを左回転する.

このようにして上の4個はなんとかなる. 下の隅はまとめて対処する.

4つの3面体の相対位置により, 巡回 28aを1回か2回使うと, 正規の位置に収まる.


[3面体が元の位置にもどる]

次はBの手順で, 今度は隅に影響を与えないよう, 単純3角形 9aだけで対応する. これも辺0に[01]を移すのがもっとも楽で, 7になるとなかなか苦しい. 下の面の8,9,10,11は, Aの手順の最後のようにまとめて対応する. これも巡回を2回使うことで無事に完了する.


[2面体も元の位置に戻る]

Cの手順は隣の辺と一蓮託生なので, たとえば辺0の向きを変えると, 辺1,4,3,7のどれかも向きが変わる. それでせっかく揃っていた向きも壊れるかもしれない.

まず一筆描きの辺の順を決める. たとえば0,1,2,3,7,8,4,9,5,10,6,11とする. 辺0の2面体の向きが違っていたら, 0と1の辺の隣辺向き替えを行う. 次に辺1の2面体の向きを調べ, 違っていたら1と2の辺の隣辺向き替えを行う. このように順々に向き替えを続けるとこの手順は完了する.


[2面体の向きを揃える]

Dはねじりで, これは向きが揃うまで同じ操作を2回やらなければならないかもしれない. これも一筆描き, 0,1,2,3,7,6,5,4のように実行すれば 終わる.


[3面体も向きを揃える]

手順AやBの小体の移動に較べると, 向き替えははるかに簡単であった.

問題はそれぞれの操作がある位置についてしか書いてないことで, 人手で揃えるときはキューブをその向きになるよう持ち替えるのだが, 私はx,y,z軸について操作を回転した操作を生成するSchemeのプログラムを書き, あらゆる方向の操作を用意した上で好きな位置で処理が出来ようにした.

乱数を発生させてキューブをこねたあと, 元へ戻すプログラムを走らせると, 一瞬にして完成するのが感動的である. もちろん途中経過を出力しているから, 手順を追って完成させていることも確認できる.

Rubicキューブのシミュレータ

Rubicキューブのどの面をどう回せといわれても, 手でやっていれば, 手順が複雑になってくるとつい間違えてしまうのは誰にも経験があろう.

その点, シミュレータはプログラムをしっかり書けば何回でも正しく処理できる.

Winning WaysにはElena Conwayが好んだパターンを作る手順が書いてある. どんなパターンか興味があったが, シミュレータを使えばそのパターンを作るのは簡単であった.

Aは4 Windows. Bは6 Windows. CはChequers. DはHarlequin. EはStripey. FはZigzag. Gは4 Crosses. Hは6 Crossesというらしい.

手順は省略する. Winning Ways, Vol. 4, p. 876参照.

Rubicキューブのシミュレータ

情報処理学会誌にRubicキューブの話を書いたのは2005年7月号であった. その話題は島内先生の名著(島内剛一:ルービック・キューブ免許皆伝, 日本評論社(1981))の置換をHaskellで記述することであった. (この本はルービック・キューブと数学パズル, 日本評論社(2008)として再刊された.)

最近Winning Waysを見ていたら, Rubik's Hungarian Cubeなる話題があり, いろいろ書いてあるが結構ややこしい. 我が家にもRubicキューブはあったが, 最近は見当たらないので, 私のことだからPostScript(とProcessing)でシミュレータを書いた.

それを使ってWinnig Waysの方法を試みているのだが, なかなかうまくはいかない.

今回はとりあえずシミュレータの話だ.

学会誌にあった絵だが, 下の図でAは魔方体を横からみた図で, この方向を南(S)とする. 上はトップ(T)とする. 右にわずかにみえる面は東(E)である. 当然みえない右の方に西(W), 向こう側に北(N), 下にボトム(B)の面がある.

BはTの面を回転しているところで, 時計廻りをt(あるいはt+), 反時計廻りをt-という. CはSの面の回転で, s(s+)とs-になる. DはE面の回転e(e+)とe-である. (どの図もちょうど45度回ったところで, 回転方向は分からない.)

今回のシミュレータはカラーで, 上の図では見えなかった3面が右につなげて描いてある.

Bの図では左半分の上段の色が右回転した(t)後であることを示している. C, Dはsとeの結果である.

この下の図も(図の記号は違うが)学会誌の図で, 島内本にある基本操作
E) 単純3角形 9a
F) 隣辺向き替え24a
G) 巡回 28a
H) ねじり 33a
を示す. そのシミュレータ版が次だ. 54の面には次のように0から53の番号が振ってあり, リストに各面の色が入っている. 回転によりその色を入れ替えている. 例えば回転tについては

((0 2 8 6) (1 5 7 3) (15 24 33 42) (12 21 30 39) (9 18 27 36))

のような置換のリストがある. つまり面0は2へ行き, 2は8へ行き, 8は6へ行き, 6は0へ行くを示す. t-はこのリストを逆に読む. まだ前途遼遠だが, 出来たところまでをまずアップロードしよう.

MacMahonのSuperdomino

MacManonの3色四角形Superdominoにはジグソーパズル風の変形がある. つまり黒は黒と接するが, 白は灰と接するのである. それでも解はある.

白と灰の間の線を凹凸にするとジグソーパズルになるのである. そのジグソーdominoを前回のブログの3色四角形superdominoの図に対応させて描くと次のようになる.


The Winning Waysにはそれを利用したJohn Conwayの1968年のクリスマスカードの絵がある. (ウェブを探したらやっとここに見つかった.)

とりあえず制約条件をすこし修正してプログラムを走らせると, 次の解がまず得られた. この境界をジグソーに対応させたのがその下の図だ.


このジグソーパズルが通常のそれと違うのは, 絵にまったく頼らずに完成することである. それも多くの解(余詰め?)が存在する. ユニーク解にするためにはやはり絵を描くことになろう. それでCheshire Catの絵に上の解を重ねてみたのが下の図だ.


1年ほど前, IBMカードを作ったcraftroboを使って切り出せば, ジグソーパズルが作れるはずだが, こんなに優しいジグソーパズルは作るまでもあるまい.

MacMahonのSuperdomino

The Winning WaysにMacManonのSuperdominoという話題がある. 正n角形で辺と中心で出来る二等辺三角形をm色に塗り分けたものである. m色n角形superdominoという.

4色三角形superdominoは24種, 3色四角形superdominoも24種類ある.



5色五角形superdominoは, 各色を1回ずつ使い裏返しは同じとみると12種だ. この12種で辺の両側が同じ色になるように正十二面体に貼ることができるかがクイズである.

五角形は置いておき, 三角形では辺の長さが三角の辺の2倍の正六角形の中に, 周囲を同一色にし, 内側の相対する辺が同じ色になるように詰めるのがクイズ. 四角形では4×6の長方形で同様にするというのがクイズである.

四角形の, 周囲を黒にした解の一例は以下だ.



十年ほど前, 情報処理学会誌にプログラム・プロムナードの連載があり, 私はそこで「計算機用ジグソーパズル」という記事を書いた. それ以外にも探索問題のプログラムはなんども書いたからちょっとやってみたが, 最初の解が出てくるまでは存外大変であった.

プログラムを書くには24個の箱とその辺を下の図のように番号をつける.



制約としては箱0の辺0の色は2, 箱0の辺3の色は2, 箱1の辺0の色は2, 箱2の辺3の色は箱0の辺1の色, ...のようになる.

そして4色四角形のsuperdominoのプールから, 必要に応じて回転しながら, 制約に合うものを探すことになる.

しかし闇雲に初めても最初の解もなかなか現れない. ある週末, プログラムを走らせたまま帰宅したら, 次の週の初め, 夛くの解が出ていたから, 方針としては良かったのだが, これではあまりにも手抜きであったのでなるべく準備をしてからやりなおすことにした.

左上の箱から番号順に詰めていくとすると, まず辺0がg₀, 辺3がg₃, 辺1と辺2はどうでもよいdomino の集合を*g₀??g₃とする. ?は0,1,2だから要素が9個の集合が出来る. 箱5,11,17,23用には辺1が2だから要素数3の*g₀2?g₃. 箱18から22用には辺2が2だから要素数3の*g₀?2g₃. 箱18用には辺1と2が2だから要素数1のg₀22g₃を用意する.

*2222は(((2 2 2 2) (23 0)))
*02?2は(((0 2 0 2) (13 0)) ((0 2 1 2) (15 0)) ((0 2 2 2) (17 0)))
で, 要素は((u r d l) (i j))の形である. u, r, d, lは上右下左の色(0,1,2), iはdomino番号(0〜23), jは90度の回転した数(0〜3)である.

プログラムの中心は次のようだ.

(define (test n ps is js)
 (define (up ps) (caddr (list-ref ps 5)))
 (define (left ps) (cadar ps))
 (define (try *????)
  (for-each (lambda (x)
   (let ((p (car x)) (i (caadr x)) (j (cadadr x)))
    (if (not (member i is))
     (test (+ n 1) (cons p ps) (cons i is) (cons j js)))))
      *????))
 (case n
  ((0) (try *2??2))
  ((1 2 3 4) (case (left ps) ((0) (try *2??0))
                             ((1) (try *2??1))
                             ((2) (try *2??2))))
  ((5) (case (left ps) ((0) (try *22?0))
                       ((1) (try *22?1))
                       ((2) (try *22?2))))
  ((6 12) (case (up ps) ((0) (try *0??2))
                        ((1) (try *1??2))
            ((2) (try *2??2))))

あとは同様なのでしばらく省略.

  ((24) (begin (display ps) (newline) (display is) (newline)
   (display js)) (newline))))

testの引数はpsがそれまでのdominoの列, isはi, jsはjの列である. (test 0 '() '() '())で起動する.

プログラムをしばらく走らせると解が次々と現れる. とても全解探索する気分にならないが, Martin GardnerのNew Revised Edition Mathematical Diversionsの193ページに解の総数は12261と書いてあった.

1964年の初め, Stanford大学の計算センターで, Gary Feldmanが全解を求めるプログラムを書いた. Algolで書いたプログラムはB5000計算機で40時間かかったそうだ. 結果は8ページの"Documentation of the MacMahon Squares Problem," a Stanford Artificial Intelligence Project Memo No. 12で, 1964年1月16日に計算センターから刊行された.

なおこの話題によると2009年11月21日と29日のブログ 彩色立方体もMacMahonの考えたものらしい.

生後n日目

最近 還暦, 古希, 喜寿, 傘寿などの祝事で兄弟があつまる事が少くない. そういう折に私が「生れて何万何千日たった」と発言したので, まわりが似たような計算をしたがった.

私自身はJulian Date(DJ)が計算できる例の個人用電卓を携帯しているので, 「今日の日付を入力, JDに変換, 生れた日付を入力, JDに変換, 引き算」で簡単に得られる. もっともこれでは生れた日が第0日になり, 生れた日を第1日にする常識的な勘定と違うが, 満n日といえば良いかもしれない.

しかし一方, 「ちょうどn日になるのはいつかなぁ」にはJDだけでは片付かない. そこで誕生日とnを入力すると, 生後n日目になる日付を計算するウェブアプリを作ってみようと考えた.

アルゴリズムは私のブログ, 2011年5月23日のunix timeにあるのを使えばよい. 現在生きている人が対象なら, Julian Calendarは考えなくてよい. Gregorian Calendarが昔まで続いていたとするFixed Date(Rata Die)というのがあるから, 年月日からFixed Dateへの変換とその逆変換があれば, 出来たようなものである.

私はhtmlのウェブページは何回も書いたことがあるが, 計算するにはJavaScriptでも使うことになるであろう. O'reillyのJavaScriptの本は持っている. その例をみながらやって見ることにした.

<html>
<head>
<title>nth day after birth</title>
<script language="JavaScript">

この辺まではお作法のうちだ. JavaScriptでは整数の除算が見当たらなかったので, 整数除算の関数を作る.

function quotient(a,b){
var r=a%b;
var q=(a-r)/b;
return q;}

つぎは私のカレンダーのプログラムによく登場する前月までの日数の和のリストで, 平年用と閏年用を用意する.

var mon0=[0,31,59,90,120,151,181,212,243,273,304,334];
var mon1=[0,31,60,91,121,152,182,213,244,274,305,335];

次は年月日からFixed Dateを計算する関数rdだ.

function rd(y,m,d){
var a=(y-1)*365;
var b=quotient(y+3,4);
var c=quotient(y,400)-quotient(y,100);
var f=(((y%100)==0)?((y%400)==0):((y%4)==0))?mon1[m-1]:
  mon0[m-1];
return a+b+c+f+d-1;}

ご覧のように簡単だ.

反対にFixed Dateから年月日を求める関数grだ. ブログにあったアルゴリズムはfloor関数を使うが, JavaScriptにはないらしいので, 1で整数除算をすることにした.

function gr(rd){
var d0=rd+366-1;
var y400=quotient(d0,146097);
var d1=d0%146097;
var y100=quotient(d1/36524.25,1);
var d2=d1-146097+quotient(36524.25*(4-y100),1);
var y4=(y100==0)?quotient(d2,1461):
  (24-quotient((36523-d2)/1460.96,1));
var d3=(y100==0)?(d2%1461):(d2-quotient(y4*1460.96,1));
var y1=((y100>0)&&(y4==0))?quotient(d3,365):
  quotient(d3/365.25,1);
var d4=((y100>0)&&(y4==0))?d3%365:
  (d3-1461+quotient(365.25*(4-y1),1));
var y=y400*400+y100*100+y4*4+y1;
var leap=((y%100)==0)?((y%400)==0):((y%4)==0);
var e=leap?mon1:mon0;
var mon=0;
for(i=0;e[i]<=d4;i++){mon=mon+1;}
var d=d4-e[mon-1]+1;
document.write(y.toString(10)+" "+mon.toString(10)+" "
  +d.toString(10));
document.write("<br>");}

これでテストしてみるとうまく行く. 結果は関数の中でdocument.writeする.

ところでy,m,d,nの入力はどうするか. 読み込んだものは文字列らしい. 解説書で使えそうなものを探すと, データ間はカンマで区切り, カンマの位置をindexOfで探し, substringを取れば, それぞれのデータが得られることが分った. またそれだけだと文字列であるが, 0を引くと整数になるという奥の手も知った. こうして書いたのが下の<body>部分である.

</script>
</head>
<body>
<script language="JavaScript">
document.write("<br>");
var s,i,y,m,d,n;
s = prompt("Type in your birthyear,birthmonth,birthday and n
  as `2000,1,1,1000' without space", "");
i = s.indexOf(',');
y = s.substring(0,i);
s = s.substring(i+1,s.length);
i = s.indexOf(',');
m = s.substring(0,i);
s = s.substring(i+1,s.length);
i = s.indexOf(',');
d = s.substring(0,i);
n = s.substring(i+1,s.length);
document.write("y = " + y);document.write("<br>");
document.write("m = " + m);document.write("<br>");
document.write("d = " + d);document.write("<br>");
document.write("n = " + n);document.write("<br>");
y=y-0;
m=m-0;
d=d-0;
n=n-0;
var r=rd(y,m,d);
document.write("Your "+ n.toString(10) +"th day is ");
gr(r+n);document.write("<br>");
</script>
</body>
</html>

さて上のプログラムを呼出すと下のような画面が現れる.





例えばAlan Turingは1912年6月23日生まれ. その滿1万5千日目をみるには

1912,6,23,15000

と入力すると

y = 1912
m = 6
d = 23
n = 15000
Your 15000th day is 1953 7 18

と得られる. Turingは1954年6月7日に他界したから, 1万5千日とすこししか生きていなかったわけである.