Solving the Rubik's Cube Optimally is NP-complete
In this paper, we prove that optimally solving an $n \times n \times n$ Rubik's Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an $n \times n \times n$ Rubik's Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik's Square---an $n \times n \times 1$
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へとステ
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(青)
Rubicキューブのシミュレータ
情報処理学会誌にRubicキューブの話を書いたのは2005年7月号であった. その話題は島内先生の名著(島内剛一:ルービック・キューブ免許皆伝, 日本評論社(1981))の置換をHaskellで記述することであった. (この本はルービック・キューブと数学パズル, 日本評論社(2008)として再刊された.) 最近Winning Waysを見ていたら, Rubik's Hungarian Cubeなる話題があり, いろいろ書いてあるが結構ややこしい. 我が家にもRubicキューブはあったが, 最近は見当たらないので, 私のことだからPostScript(とProcessing)でシミュレータを書いた. それを使ってWinnig Waysの方法を試みているのだが, なかなかうまくはいかない. 今回はとりあえずシミュレータの話だ. 学会誌にあった絵だが, 下の図でAは魔方体を横からみた図で, この
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Of solving the rubik's from scratch
