私の出身校の後輩が、ハンガリーで行われたルービックキューブの大会で世界一になりました。(縦横奥行き3列の部門)
新聞によると、このタイプのルービックキューブの色の組み合わせパターンの数は、京(兆の次)のオーダーになるそうです。
ふと思ったんですけど、色のパターンを入力したら、自動的に解法(どうひねくりまわせば色がそろうか)を教えてくれるアルゴリズムというか、コンピュータプログラムは作れるんでしょうか。(もちろん有限時間内の最短の道のりで。)
答:作れるにきまってるじゃないか。人間が解けるんだから。ですか?
「知の森」を復活させねばなあ。
A 回答 (8件)
- 最新から表示
- 回答順に表示
No.8
- 回答日時:
I/O 1981年3月号に横澤信夫さんが「ルービック・キューブ解法プログラム」という記事を掲載されています。
BASIC での解法で、最適化されたものではないという断り書きがあります。参考文献に、
参考文献
1)神谷真吾:“ルービック・キューブの解き方”I/O,
'80年10月号
2)数学セミナー,’80年11月号
3)N-BASICプログラム教本
が載ってます。
No.7
- 回答日時:
なるほど。
ルービックキューブ(もしくはハンガリアンキューブ)は、操作が数学で言う群になるんで、群論の教材としても使われました。3x3x3のキューブを回して作れる可能な色の配置の数は (3^8)(2^12)(8!)(11!)通りです。
以下、3x3x3の話にします。手に持ったキューブの各面をFront, Back, Left, Right, Up, Downと名付け、それぞれの面を(面に向かって)時計回りに90°回転する操作をF, B, L, R, U, Dと表します。また反時計回りは ' を付けて表します。キューブを上面、中間層、底面に分けて考えます。そして、中間層を右に90°回す(上から見て半時計回りに回す)操作をεと書きます。(最初にアルゴリズムを[論文として証明付きで]構成したのはアン・スコットって人ですけれども、この記法はシングマスターさんが考えたもの。)
簡単な操作の組み合わせだけで色を揃えるには、以下の手順だけで可能です。
(1) 底面の辺のキューブを正しい位置にする。(簡単ですんで省略)
(2) 底面の角のキューブを正しい位置にする。これは、
F'U'F, RUR', F'UF, RUUR'
のどれかの手を使えばできます。
(3) 中間層の辺にあるキューブを正しい位置にする。
URU'R'U'F'UF, U'F'UFURU'R'
を使うことによって、底面を全く変化させずに可能です。
(4)上面の辺にあるキューブを正しい位置にする。ただし向きが狂っていても気にしない。
UFRUR'R'U'F'
を用いることで、中間層、底面を変化させずにできます。
(5) 上面の角にあるキューブを正しい位置にする。ただし向きが狂っていても気にしない。
FDFFDDFFD'F'
で隣接した角にあるキューブを交換することができます。
(6) 上面の辺と角にあるキューブの向きを直す。
(F'RDR')^2, (RF'R'F)^2, (εR)^4
を使うと他の部分が乱れません。( ^n はn回繰り返すという意味。)
もちろん、各段階で色の並び方を見て、どの操作を適用すべきかを判定する必要があります。それはここでは省略しますが、簡単にプログラミングできることはお察し戴けるでしょう。かつてフリーソフトも見かけたことがあります。という訳で、ご質問への答はYES。
しかし競技をやる方々にしてみれば、こんなのは初歩も初歩、「バイエル」みたいなもんだろうと思います。彼らはこんな冗長な手順の代わりに、一連の操作から成る特殊な「フレーズ」をいっぱい憶えていて、特定の部分を変化させずに別の部分を素早く動かすために利用するようです。
もちろん、「何回操作したか」ではなく「何秒で操作したか」を測るのですから、数学的な最短手順とはまた違った話です。ほとんど自動的に手が動くまでに練習し、さらにキューブが物理的に滑らかに回るように手入れをして、F1マシンのように磨き上げていると聞きます。
もっと別の、より数学らしい方法も証明されています。その方法では、キューブの配色の状態を、ある計算式で「点数」に変換する。そして、可能な操作(F, B, L, R, U, Dおよびその逆回転)のうちから「それをしたら点数が小さくなるようなもの」を一つ選んで実行する。すると、(ただ一つの状態を除いて)どの状態でも常に「点数をより小さくできる操作」が存在する。(点数を小さくできるような操作が存在しない唯一の状態というのは、もちろん、全ての面の色が揃っている状態のことです。)
「ある(条件分岐を含む)手順が、どんな状態から始めても最悪何手で各面を揃えることができるか」を考えると、「最悪何手掛かるか」の手数が最小であるような手順を求める、という問題が考えられます。そのためにはまず、「どんな手順を使おうとも最低x手掛かるような状態」とはどんなものか、そしてxの最大値は幾らか、を考える必要があるでしょう。(ANo.6のリンクは「xが25であることを(スパコンで?)証明した」というハナシですね。)
「任意の状態に対して、最小の手数で各面を揃えるための手順を作り出す」ことができるアルゴリズムを求む、となるとまた別の問題です。もちろん、そういうアルゴリズムは実際に構成できます(総当たりで調べるだけです)が、そのための計算量をどこまで小さくできるか、が本当の問題です。
他にもいろんな問題が考えられますんで、嘗ての流行時には数学の分野として「キューブ学」なるものを提唱する方まで居たようです。そろそろ復活してもいいんじゃないかなあ。
No.6
- 回答日時:
2chの科学板でそんな話題をみかけました。
残念ながら、アルゴリズムについてはあまり詳しく載せてませんが、
文章の印象だと、ありそうですね。
つまり、「アルゴリズムの存在証明」だけでなく、
すでに具体的にアルゴリズムが構成されていそうです。
参考URL:http://news21.2ch.net/test/read.cgi/scienceplus/ …
回答ありがとうございます。ご紹介のURLを見ました。
ルービックキューブがどんな状態(パターン)であっても、26手以内で
色合わせができるということが証明されたようですね。
「スーパー・コンピューターで63時間かかった」という意味は、
26手より多く手が必要なパターンが存在しないのを確かめるのに
それだけの時間がかかった、ということでしょうか。(?)
だとすると「ルービックキューブの解法プログラム」なるものは
お仕着せで人間がコンピュータに与えるしかなく、コンピュータが
解法を教えてくれるわけではない、ということですよね。
No.5
- 回答日時:
私は、自分で開発した方法で、100動作前後でできます。
自分用のメモは書いてありますが、プログラム作りは断念しました。理屈上は可能ですが、断念の最大理由は、状態・動作と画面表示とのインターフェースの設計が、とても面倒だからです。コンピューターでやるときは「特定の2つのコマの交換法」を繰り返しせば、プログラムの記述自体は短くなるはずです。しかし実技上の動作数は、とても大きくなります。
もちろん、私の方法は、最短動作数ではありません。理論的な最短動作数は「最大の場合で30手前後」だという記事を、昔読んだことがあります。
回答ありがとうございます。
ハンガリーでチャンピオンになった後輩は、新聞報道では、
500種類の解法パターンを暗記していたそうです。
> 「特定の2つのコマの交換法」を繰り返しせば、
> プログラムの記述自体は短くなるはずです。
> しかし実技上の動作数は、とても大きくなります。
プログラムとしてはわかりやすいけど、方法は愚直だということですね。
プログラムとしてもスマートでわかりやすく、手数も最短というのは、
無理なことなのでしょうね。きっと。
No.4
- 回答日時:
#2です。
#3の動画見ました。感動モンですな。
PC-8001の解法プログラムですが、動画を見てちと思い出しました。
PC-8001のプログラムは動画のような3Dではなく、1面3×3に区切ったサイコロの展開図のような表示だったと思います。
今手元にありませんが、実家に帰ったときに確認してみます。
回答ありがとうございます。
> 1面3×3に区切ったサイコロの展開図のような表示だったと思います。
ルービックキューブを回転させてとき「コマ」がどう移動するかの
方程式?(変換式?)は、簡単に作れるでしょうけど、6面の色を
きれいにそろえるプログラムは、どうすれば作れるのか、私には見当が
つきません。膨大な解法パターンのデータベースを参照するようなプログラム
じゃ、しょうがないですよね。(チェスや将棋のプログラムはこれに近い?)
No.3
- 回答日時:
ありました。
関連リンクに1000×1000×1000を解いている動画があります。20×20×20で4時間かかっているので恐ろしく長い時間を掛けているみたいですね。回答ありがとうございます。
時間はコンピュータの性能によりますよね。
スーパーコンピュータなら、1000分の1秒もかからないのかもしれません。
私も質問を出してから気がついたのですが、ポイントは「最短の道のり」を教えてくれるプログラムを作れるのかどうか、じゃないでしょうか。
(数学カテゴリの質問としては。)
トライアンド・エラーで、そろったかどうか途中で確かめながら、試行錯誤するようなプログラムじゃ、しょうがないですよね。(人間と同じ。)
No.2
- 回答日時:
古い話ですが、ルービック・キューブが大流行していた1980年頃、工学社から出ていたパソコン雑誌「I/O」(アイ・オー)にPC-8001用の「ルービック・キューブ解法プログラム」が掲載されていたと思います。
自分はPC-8001を持っていなかったので、詳細は分かりませんが当時流行していたプログラム、BASICで書かれていました。
同じ号に「ルービック・キューブ解法」が載っており、それまでは分解して組み直すしか、色を揃えることが出来ませんでしたが、それを見ながら色が揃えるうちに、自分で揃えられるようになりました。
先日またルービック・キューブに触れる機会がありましたが、解法は見事忘れていました。
回答ありがとうございます。
> 1980年頃、工学社から出ていたパソコン雑誌「I/O」(アイ・オー)に
> PC-8001用の「ルービック・キューブ解法プログラム」が掲載されていたと思います。
うーん、いい話ですねえ。(私は懐古趣味者なんです。若き日が懐かしい。)
このプログラムは、囲碁や将棋のプログラムと比べたら、特段に、ものすごく簡単なロジックになるんでしょうけど、その方程式(?)が、私には、皆目見当がつきません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『4色問題③』 2 2022/11/14 00:31
- 仕事術・業務効率化 効率的な勉強方法(分野問わず)を教えてください 1 2023/08/16 01:33
- 数学 『数学的帰納法のトリセツ』 4 2022/06/06 07:34
- その他(悩み相談・人生相談) 仕事でわからないことがあるとパニックになり、生きていく自信すらなくしてしまう 3 2022/06/06 21:03
- 仕事術・業務効率化 自分は、マイペースで行動の段取りに無駄が多いです。 ものを動かすにしても、1個だけ動かせば解決するも 1 2023/07/07 21:41
- ホームページ作成・プログラミング グリッドレイアウトHTMLとCSS 1 2023/02/22 02:36
- 哲学 政治とは 共同自治であり 愛である。 2 2022/04/02 10:57
- 仕事術・業務効率化 YouTuberって職種ってなんだかんだ楽だよね? 5 2023/03/12 00:55
- その他(ホビー) ルービックキューブなかなか揃わない ルービックキューブを揃える時にLBL法を使っているのですが、側面 1 2023/07/18 18:46
- 哲学 人間はカオスだ!?:国家権力の三権分立と神なる三位一体とのフラクタル構造? 56 2022/11/28 17:29
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
[ EXCEL VBA ] 図形を読み込む...
-
Dijkstraて
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
小町算(+,-のみ)のトレースです。
-
ドロネー三角形のプログラム
-
c言語で画像から文字を認識 キ...
-
JPEG圧縮で8×8に分割する理由に...
-
三次元形状曲面の導出法
-
Stuck
-
ハッシュアルゴリズム
-
詰め将棋をとくのは、アルゴリ...
-
アルゴリズム・ネストループ方...
-
ゲームプログラミングC/C++、SR...
-
データ構造とアルゴリズムの違...
-
巡回セールスマン問題
-
かけ算に関してのアルゴリズム
-
パックマンプログラム
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Stuck
-
アルゴリズムとプロトコールの違い
-
画像から文字を認識してテキス...
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
期間重複チェックがわかりません
-
gooという検索エンジンの後にGo...
-
2つのテキストファイルを比較...
-
ハッシュアルゴリズム
-
理系の高校生です。大学で情報...
-
あいまい検索(文字列一致率)
-
デジタル時計のアルゴリズム
-
経路探索について
-
グループを均等に分けるには?...
-
m個の数字をn個のグループに分...
-
乱数って・・・
-
確率論的な麻雀の勝ち方を教え...
-
多変数関数の最小値を求めるプ...
-
OpenCVのライセンスについて
おすすめ情報