nigoblog

技術系会社のCEOブログ~私的編~

ルービックキューブにハマる~そしてアルゴリズムへ~

f:id:nigohiroki:20121009234619p:plain

最近なぜだかルービックキューブにドハマリしてます。
元々はルービックキューブのアルゴリズム使ってなんかできないかなというのがきっかけなんだけど、

攻略サイトを見ながら崩しては完成させ、崩しては完成させを繰り返し、
約20回ほどやりました

なのにいっこうに覚える気配がない笑

ただなんとなくコツを掴んできたのと、
一つの真理を発見しました。

それは
ルービックキューブは場所の入れ替えによって完成する

たぶん何も見ずに六面揃えられる人は「今更なにいってんだコイツ」状態かとは思いますが、
そしてエスケープする場所もないんだから当然っちゃあ当然なんだけどもね。

でもその入れ替えにも色々あって、
最大3個の入れ替えがあることを発見しました。
単純に2つの場所の入れ替えではなく3個の位置でサイクリックに移動するようなことが考えられます。
つまりもしかしたらルービックキューブはベクトルで表せられるのではないかと考えました。

ここでベクトルのお話なのですが、

A = (1, 2, 3)

このようなベクトルがあった時

A' = (1, 3, 2)

と入れ替えが起きたとします
この時、距離が「1」離れたというような考え方をします。
また

A" = (3, 1, 2)

このような入れ替えの場合距離は「2」離れたとします。
さらにベクトルは行列に拡張できるため、

(A, A', A")

とすると

1 1 3
2 3 1
3 2 2

というようなRank 3 の行列ができます。
つまり結局よくわからんって感じです笑

ただ行列で表せるというのは間違い無いと思っていて、
行列で表せる→グラフで表せる!
コンピュータで解くには
グラフの探索によるアルゴリズムでルービックキューブを解くという結論に自分の中で達しました。

グラフの探索は
1. 幅優先探索
2. 深さ優先探索
があります。このどちらかを用います。

するとルービックキューブを解くためのフローチャートは
1. データモデルを用意する
2. 終了条件を決定する
3. ある位置からみた目的のマスを探索する
4. 入れ替えを行う。
5. 3~4を繰り返す。

もちろん全数探索では3でルービックキューブの矛盾が生じるので、ルービックキューブに応じたグラフを形成する必要があるかとは思いますが…

というかなり素人考えですが、

ルービック・キューブと数学パズル (数学ひろば)

ルービック・キューブと数学パズル (数学ひろば)


今度この本を見てしっかり勉強しようと思います。

ではでは今日は妄想のお話でした。

いつかルービックキューブを解くアルゴリズムを応用して何かに利用したいと思います!!