ルービックキューブは 20 手で完成できる 36
ストーリー by reo
Rokicki 先生の次回作にご期待下さい 部門より
Rokicki 先生の次回作にご期待下さい 部門より
ルービックキューブをどんな状態からでも最小手数で完成できる人がいたとして、最悪の場合何手必要か。この数は「神の手数」と呼ばれ、多くのパズル愛好家や研究者等の興味の対象であった。これまで、神の手数は 20 手以上 23 手以下であることが知られていたが、このたび Morley Davidson、 John Dethridge、 Herbert Kociemba、 Tomas Rokicki は神の手数が 20 手であることを計算により明らかにしたと発表した。計算には、 Google により提供された余剰 CPU 時間、のべ 35 年分 (4 コア 2.8 GHz の Nehalem 換算) が使われた。
実際に計算に要した時間は数週間だったそうです。よしパパがんばっちゃうぞと予言してらっしゃった方がおりましたが。
さっきからルービックキューブやっているんですが... (スコア:5, おもしろおかしい)
あと1面そろえるのが難しくて...
Re:さっきからルービックキューブやっているんですが... (スコア:3, おもしろおかしい)
Re:さっきからルービックキューブやっているんですが... (スコア:2)
Re:さっきからルービックキューブやっているんですが... (スコア:2)
Re:さっきからルービックキューブやっているんですが... (スコア:2)
>あと1面そろえるのが難しくて...
数学的直観主義ですね
Re:さっきからルービックキューブやっているんですが... (スコア:1)
5面まで揃えば、あとちょっとです!
// がむばってくだしあ
それはそうと、私の観察と実験によると、
「ルービックキューブを有限の時間と手順で解くことは不可能」
という結論が導かれるのですが ……
Re:さっきからルービックキューブやっているんですが... (スコア:1)
それはまだ、観察不足なだけです。もうあと56.7億年ぐらい観察を続けてください。
fjの教祖様
Re: (スコア:0)
すべての煩悩が無くなるもんね
Re:さっきからルービックキューブやっているんですが... (スコア:1, 参考になる)
Re: (スコア:0)
手が18本ほど不足しているようです。
Re:さっきからルービックキューブやっているんですが... (スコア:1, おもしろおかしい)
千手観音がやれば1手で完成できますね。
# 「あと1人月かかります」→「じゃあ30人いれば1日で終わるんだな。今すぐ人を集めろ」
Re: (スコア:0)
1人月≒20人日 (スコア:0)
1人月の発注で30日働いてくれるんなら儲けもんですな。w
22 手以下であることはわかっていました (スコア:2)
22 手以下であることは 2008 年にわかっていたみたいです。タレコミで「23 手以下」と書いてしまったのは単純に確認し忘れです。すみません。
Re: (スコア:0)
個人的な経験として 40 手だと思っていました
やっぱり突き詰めれば半分になっちゃうんだなぁ
Re: (スコア:0)
今よりさらに突き詰めていけば、いずれ10手になりそうですね
人類はどこまで行ってしまうのか
さすがに20手なら (スコア:1)
キュービックルーマン [fujitv.co.jp]の負けは無くなるかな?
(20手だとしても、その手順がすぐに解るとは限らないので、結局負けるんだろうな)
※キュービックルーマンが昭和っぽくて好きだからIDで
キャラクタールービックキューブの場合 (スコア:1)
キャラクターの顔などが印刷されてるルービックキューブの場合、
大抵向きがあるので20手超えるんでしょうなぁ
こっちの最小手も誰かよろしく
Re: (スコア:0)
え?
最善手でなければ (スコア:0)
ルービックキューブをはじめて知ったのは、30年ほど前のI/O誌でした。
PC-8001の時代だったんですねぇ。
最善手でなければ、このハードでも解法は提示できてました。
今でも教えてくれるPCソフトはあるのかしらん
とおもったら、解いてくれるロボットがあったか。(しかもLEGO)
Re:最善手でなければ (スコア:1)
絵柄付きキューブは何手? (スコア:0)
Re:絵柄付きキューブは何手? (スコア:2)
あれ? これって必ず向きも復元されませんか? 各面のセンターの位置関係って、回転操作しても保存されそうな気がするのですが。
# ネタだったら野暮コメントすいません。
Re: (スコア:0)
相対関係は固定ですが
絶対位置を指定するか否かを聞いてるんじゃね?
Re:絵柄付きキューブは何手? (スコア:2)
うおお。オラこんがらがってきたぞ。色の位置関係は保存されるけど、センターの向きまで保存されるとは言えない気がしてきた…。
柄キューブってやったことがないので(というか、ノーマルすら揃えるのに成功したことがない)、識者の解説希望です。
Re:絵柄付きキューブは何手? (スコア:3, 参考になる)
センターの向きは保存されません。
今ググってみて解説 [planet-puzzle.com]を見つけたけど
初めて
痛柄キューブ作ってみた時は色揃えてから結構手こずった…最悪の場合? (スコア:0)
壊れていたら修理するって手数が発生するような?
はたまた錆びて動かなかったら油をさすとか、シールがいたずらで張りかえられていたりとか・・・
#あ~、心が荒んでるな・・・
Re: (スコア:0)
ルービックキューブじゃないけど (スコア:0)
Re: (スコア:0)
書き忘れた。
盤面は初級 9x9。
でWindows 7のようにクリックした最初の場所の周りに絶対爆弾が1個もないって条件ではない
Windows XPのようにクリックした最初の場所にだけは絶対爆弾がない(クリックした瞬間ゲームオーバーではない)という条件
Re: (スコア:0)
一手目で爆弾を踏むと、左上に爆弾が逃げていくので。
# 左上から右へ未開封非爆弾マスをスキャン、右端到達毎に1つ下の列を探索、最初に見つけた未開封非爆弾マスに爆弾を移動
左上を開けるルールだと、左上に爆弾がいた場合に逃げた爆弾が隣に来るので、1手クリアの確立はちょっと下がりそうですね。
180度回転は (スコア:0)
Re:180度回転は (スコア:3, 参考になる)
1 手扱いです。
タレコミでは省略しましたが、ルービックキューブの完成手順の手数の数え方にはいろいろあります。今回の計算では、 face turn の回数を数えています。 face turn とは、キューブの 6 個の面のうち一つを、 90 度か 180 度回転させることを指します。 90 度回転にはさらに時計回りと反時計回りがあるので、 1 手でできることは全部で 18 通りあることになります。
face turn で数える場合のほかに、 180 度回転を認めない quarter turn での手数もある程度調べられているようですが、現時点でどの程度わかっているのか僕は知りません。今回の結果から、 quarter turn で数えた場合の最悪手数は 20 手以上 40 手以下であることは簡単にわかりますが、たぶんもっと良い評価が既に知られているでしょう。
そういえば、どちらの数え方でも、キューブの 3 列のうち真ん中の列だけを回転させる行為 (slice turn) は 1 手とは認めていません。これを認めたらどう変わるんでしょうね。
Re: (スコア:0)
> そういえば、どちらの数え方でも、キューブの 3 列のうち真ん中の列だけを回転させる行為 (slice turn) は 1 手とは認めていません。これを認めたらどう変わるんでしょうね。
とりあえず10手以上20手以下であることは簡単に分かりますね。
Re: (スコア:0)
Re:180度回転は (スコア:2)
何に対するコメントかがわからないので、おっしゃる意味がわかりません。