No.6ベストアンサー
- 回答日時:
#2,4です。
ご参考になるか分かりませんが、私の解法を簡単にご紹介しておきます。
先日、テレビで名人クラスの演技を見ましたが、私の方法より4~5倍以上も速く、手順もまったく異なっていました。思うに、手順を短くしようとすれば、それだけパターンの暗記項目が増えるようです。私の方法は、暗記項目が比較的少なく、完成以来30年のブランクがありましたが、今でもスラスラと難なくできます。
第1段階:頂点コマ(8個)の完成。これは#5さんが挙げた2×2×2のものと、まったく同じことです。実物が市販されていますから、手にとって研究されるといいでしょう。見かけよりは、手こずりますが。
第2段階:互いに反対側にある2面の完成。まず2つの面心コマを合わせてしまえば、残りは8個の辺心コマです。この段階が最も簡単です。
第3段階:上記2面に挿まれたリング状の8個のコマの完成。ここは8種ほどのパターン分けが必要になります。ここで6色を3色とみなします。反対側にある色を「同色」とみなすと、パターンの種類が激減します。とにかく「見なし同色」のまま完成してしまうと、最後の修正は、極めて簡単です。(手数が多少長くなってもよければ、パターン分けをしない方法もあります。)
完成時に「数芸パズル」という雑誌に掲載してもらいましたが、これは学問的に高度な雑誌でした(現在は廃刊)。これに対して、私の論文は「できた!」という報告にすぎず、数学的な裏付けが希薄なためか、読者から何の反応もありませんでした。今でも、数芸パズル誌についてのWEBページは多数ありますが、私の報告に関する言及は1件もありません。
ご成功を祈ります。
お礼が遅くなり申し訳ありません。
3度の回答、本当にありがとうございます。
とても参考になります。
手順を短くすることを第一に考えるのか、覚えるパターンを少なくすることに重点をおくのか、その点についても考えているところでした。
Ishiwaraさんの方法は、私がこれまで調べたものとはまた違っていて、本当にたくさんの解法があるのだと改めて感じました。
自分のプログラムが組めるように、頑張って学習を続けたいと思います。
No.5
- 回答日時:
とりあえず論文を読んでみればどうです?
読んでどういう仕組みか自分で分からなければ先には進めません.
No.2さんのご意見が極めて妥当だと思います.
状態とその遷移規則の表現が一番厄介でしょうね.
9マスの「丸バツゲーム」とか,将棋や詰め碁
数独とかの解法プログラムと本質的な機構は同じかも
#膨大な状態空間から適宜枝仮りをするという意味.
普通のルービックキューブだと困難なので
2*2*2の小さなもので考えるのも手でしょう.
少しだけ数学ちっくに考察.
2*2*2だと一個の状態を表すのには
表面積の分,24個のパラメータが「最大」で必要.
この時点で「可能な状態の個数」は最大 24! 個
つまり,24個のものの並べ替え.数学でいうところの
24次置換群 S_{24}.
しかしこれは大きすぎ.実際には24!個もパターンはなく
一個のパターンに付き24個の重複がある
(同じパターンを回したりすることで同じものを
24回数えてしまっていることを意味する)
有限群論の「正六面体群」に相当.これをDと書くことで
考えるパターンは剰余群S_{24}/D(位数23!)まで抑えられます.
さらに,2*2*2の場合,「角」しかなく,角のパーツは
角にしか移動できないので,その分の束縛もあるので
更にパターンはへる.
こうしてできあがった群には生成元があるはず.
この生成元を一手による状態遷移に対応させるようにとれるはず.
生成元の集合をGenとする.
揃った状態をスタートの状態 e として,
eに対するGenの元の作用の結果が
「揃った状態」から一手で移る状態になる.
そう考えると,ルービックキューブの「状態」とは
eからGenの元の作用で遷移したものとみなせ,
ルービックキューブが解けるとは
「Genによる作用が推移的である」ことを意味する.
おそらくこれはものすごく難しいというわけではない気がする.
しかし,群論の知識はそれなりに必要だと思う.
さらに,状態遷移のグラフに表せば
そのグラフの位相幾何的な性質が何かを表現してることも
想像がつく
と,まあ・・・まじめに計算するとかなりつらそうなというか
余暇ではできなさそうなので
これにて・・・
お礼が遅くなり申し訳ありません。
回答ありがとうございます。
数学的な解法を考察するために、群論の学習も行っています。
また、プログラム上でルービックキューブの状態をどのように表すのか、
あり得ない状態を含まないために何を考えなければならないのか、
課題も多いですがプログラムを実現できるよう頑張りたいと思います。
No.4
- 回答日時:
#2です。
最短手数の証明などに使ったアルゴリズムは、おそらく解の実行プログラムには役に立たないでしょう。純数学的なアプローチは、将棋で言えば、初手から「香」が1つ上がる手も吟味するようなもので、実線の指針としては使えないでしょう。ただし、もし完成して、とんでもなく速いコンピューターができれば、それこそ絶対に勝てるプログラムとなります。
もしルービックキューブを実践的に解くプログラムを作りたければ、まず試行錯誤で「必ず完成する手順」を見出し、そのアルゴリズムをプログラムに展開するのが、最も賢明だと思います。もちろん、アッと驚くアルゴリズムが発見されて、容易にプログラムに乗ってしまう、という可能性が絶対にないとは断言できません。例えば「ニム」などというゲームは、その類のものです。
私の解法は、標準で100手ぐらい(所要時間で2分ぐらい)です。このくらいなら「凝り性」の方は、開発可能ではないでしょうか。手順開発よりも、状態や操作の記述のほうが、ずっとたいへんのように思われます。
2度も回答をいただきまして、本当にありがとうございます。
Ishiwaraさんがおっしゃるように、自分で「必ず完成する手順」を見出してプログラムにするという方法でやってみようと思います。
>手順開発よりも、状態や操作の記述のほうが、ずっとたいへんのように思われます。
これは私も感じていたのですが、頑張って取り組みたいと思います。
No.3
- 回答日時:
>ルービックキューブを23手以内で揃えられることが証明されたそうです。
この結果を出した
Tomas Rokickiさん(dvipsの作者として著名)の当該論文は
http://arxiv.org/abs/0803.3435
でPDFを入手できます.
以下,入手して数分眺めた印象のみです
精読してませんので,いい加減な感想です.
中身ですが・・・ざーーっと眺めた限り
数学というよりもやっぱり情報工学っぽい感じですね.
つまり,「数学的なエレガントさ」ではなく
「こんな風に総当りすれば解けるはず」という
アルゴリズムを作って
コンピュータにがしがし計算させる感じ.
ぱっと見て使われてそうな数学は
「グラフ理論」のように見えますが,
これはアルゴリズムでは普通にでてくるものですね.
あと20手未満にはできないだろうということも書いてます.
このアルゴリズムを実装しても多分「普通の感覚で」思うところの
「解いてくれるプログラム」にはならない気がします.
そういうプログラムを実装するのは
また別の困難がありそうです.
回答ありがとうございます。
「コンピュータにがしがし計算させる感じ」ということは、4325京以上の配置が考えられるルービックキューブの計算を、一般的に使われているコンピュータで計算することはやはり難しいのでしょうか?
私は「解いてくれるプログラム」をつくりたいと考えているのですが、そのためには何を学習したり調べたりすればよいのでしょうか?
アドバイスがあればよろしくお願いします。
No.2
- 回答日時:
自分で解法を編み出した者の一人です。
方法は、私の頭の中に「非数学的な」記述法で入っていて、説明はとてもたいへんです。具体的なプログラムを作ろうとしたことがありますが、「状態」と「着手」の記述がとてもややこしくて、放り出したままです。今回のご質問で、考えられることは、次のとおりです。
(1) 多分、英語の文献以外にはないでしょう。キーワードとしては、math recreations と思います。ざっと、数万件はあるようです。
(2) 最短手数に関する研究からは、具体的な着手法はまったく得られないでしょう。具体的な着手を調べて行って最短手数に到達する、というものではないからです。最短手数の研究は、抽象的な数式が並んでいるだけで、私たちが読んでも、一言半句も理解できないでしょう。
(3) 26手というのは「天文学的」に大きな集合であり、枝分かれ手順の全貌は「記憶」できないだけでんなく「記録」もできないと想像されます。
参考URL:http://www.newscientist.com/blog/technology/2007 …
回答ありがとうございました。
最短手数で揃えられることが証明されたということで、私は具体的にその数値を出すことができるのだと考えていましたが、それは間違いだったのですね………
私もルービックキューブを解くためのプログラムをつくりたいと考えているのですが、「最短で」ということを考えなければ、群論を学ぶことで解くことができるのでしょうか?また、他に方法がありましたら教えて下さい。
No.1
- 回答日時:
↓には25手と書いてあります。
群論みたいですね。
位相幾何学という話も聞いたことが有るような。
参考URL:http://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC% …
この回答への補足
質問に補足をさせていただきたいと思います。
実際に“どのような状態からは何手で揃う”というのを23手以内で教えてくれるプログラム(ソフト)を探しています。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(ホビー) ルービックキューブ よく、ルービックキューブを30秒以内に揃えている方がいますがその方たちはどのよう 1 2023/07/16 12:43
- その他(ホビー) ルービックキューブなかなか揃わない ルービックキューブを揃える時にLBL法を使っているのですが、側面 1 2023/07/18 18:46
- その他(エンターテインメント・スポーツ) ルービックキューブを買いました。楽しくて何度もやり、大体の手順が覚えられたのですが、退屈です。 パズ 4 2023/01/25 00:34
- その他(教育・科学・学問) ルービックキューブがやっと一面揃いました。 今53才、私が生きてるうちに6面揃うでしょうか? 1 2023/01/30 16:28
- 大学受験 AO、総合型選抜出願時に使用する活動実績報告書について 4 2022/06/27 01:21
- ライフスタイル・ヘルスケア メールアプリについて教えて下さい。 次の機能が全て揃ってるものを探しています。出来れば無料アプリが嬉 1 2022/06/09 13:27
- その他(買い物・ショッピング) みなさん、おはようございます(^^) バイクを買った後に、バイク用品店でなにを揃えれば良いと思います 3 2022/05/04 10:23
- その他(ファッション) この服探してます。 ベージュのセットアップで現在調べて、色々な店舗回ってるんですが、どうもサイズがな 2 2022/08/27 17:43
- その他(プログラミング・Web制作) プログラムの勉強のおすすめは 7 2022/12/09 20:09
- その他(趣味・アウトドア・車) 個人売買のトラブルについて。 自動車の個人売買をしました。 こちらが売る側です。 相手に名義変更をす 4 2022/04/06 07:32
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
BCDについて
-
[ EXCEL VBA ] 図形を読み込む...
-
Stuck
-
グループを均等に分けるには?...
-
画像から文字を認識してテキス...
-
Dijkstraて
-
期間重複チェックがわかりません
-
JPEG圧縮で8×8に分割する理由に...
-
多変数関数の最小値を求めるプ...
-
OpenCVのライセンスについて
-
データを圧縮したい
-
ルービックキューブを揃えるた...
-
5人のテストの点数を入力すると...
-
C♯で電卓を作成しています。演...
-
ドロネー三角形のプログラム
-
vbaで、連立方程式を解く方法に...
-
動画で間違ったこと言っている
-
トップダウン解析とボトムアッ...
おすすめ情報