352. ルービックキューブは20手以内で解ける コンピュータの力も借りてその証明がなされたと

 2010年 8月26日掲載  2014年 5月 5日再掲


コンピュータ・シミュレーションもかつて、四色定理(Wikipedia)がコンピュータを用いて証明されたように、数学にとっても強力な武器となっています。四色定理(ししょくていり/よんしょくていり)とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理です。

さて、同じくコンピュータを用いてルービックキューブが20手以内で溶けるとの証明がなされたとの発表がありました。四色問題はWikipediaによると、

四色定理の証明法は次の2段階に分けられる

どんな平面グラフをとってきても、その集合に属するグラフのどれか一つがサブグラフとして含まれるグラフの集合を考える。このような性質をもつグラフの集合を不可避集合という。
うまい不可避集合をとると、それに属するどのグラフも次の意味で可約にできる。すなわち、そのサブグラフを含むグラフがあったとき、そのサブグラフを除いたものが4色塗り分け可能なら、グラフ全体も4色塗り分けできる。
実際、もし四色問題の反例となる、塗り分けに5色以上必要なグラフがあったとしたなら、その中でノードの個数が最小のものを考える。すると、1.よりこのグラフは不可避集合に属するサブグラフを含む。2.により、このサブグラフを除いた、より小さなグラフが既に四色問題の反例を与える。しかし、それは最小反例をとってきたという仮定に反する。

アッペルとハーケンはコンピュータによる実験を繰返し、プログラムを何度も書き換えながら、可約なグラフから成る約2000個のグラフからなる不可避集合を求めた。当時の最高速のスーパーコンピュータを1200時間以上使用したといわれている。


という過程を経て証明された。

しかしながら、今回のルービックキューブの証明は、「実質的なしらみつぶし」とあるように、厳密な意味では証明にはなっていないように思う。さらに検討を続け、20手までで解けない例外が一つでも出てくれば、提出された定理は崩れ去ることになる。


そこでさらに調べてみると、ルービックキューブ(Wikipedia)には次の記載があり、数学の対象として真剣に検討されてきた歴史が記述されている。そして、この7月に20手が証明されたとある。

最少手数
「いかなる状態でも、最多でも○○手で各面が揃った状態に戻せる」という数のことを「神の数字(God's Number)」と呼ぶ。長い間研究対象とされてきたが、2010年7月、Morley Davidsonを中心とするグループの発表によって終止符が打たれた。

2010年7月、Morley Davidsonを中心とするグループによって、20手であることが示された[11][12]。上述のスーパーフリップの件とあわせて、これが真の「神の数字」と証明されたことになる。余談だが、このグループのメンバーには上述のトマス・ロキッキも含まれている。



Asahi.com 8月18日
ルービックキューブ、20手で必ず解ける 数学者ら実証
立方体の各面の色をそろえるパズル、ルービックキューブは、初期の配置がどんなにでたらめでも20手で解けることを、ケント州立大(米オハイオ州)の数学者ら米独の研究チームが証明し、発表した。

 チームは、米ネット検索大手グーグルが提供した多数のパソコンの計算時間の空きを利用。実質的なしらみつぶしを行い、どんな配置でも20手以下で解けることを示した。


ルービックキューブマシン(YouTube)ではシミュレーションをしながら実際にルービックキューブを動かしていく動画を提供しています。20手までとはいっていませんが、実際にここまでできるのだと、説得力のある画像となっています。これ以外にも、YouTubeにはルービックキューブに関する多くの動画が投稿されています。


20手以内とはいかないようですが、人間の能力にも素晴らしいものがあります。20秒以内でルービックキューブを解いています。YouTubeより。
Yumu Tabuchi One Hand WR 16.90 avg World Rubik's Cube Championship 2009




文書リストに戻る ホームに戻る