「ルービックキューブは26手以内で揃う！」記事へのコメント

あながち間違いじゃないな

[Anonymous Coward]

タイムアタックで２０秒程度で揃うのであればその程度なんだろうな

逆に考えると全部揃った時点から２６回動かすとすべての手になりうる事を証明すればいい

36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36*36

2.9098126 × 1040通り？

最低18手

[targz (14071)]

リンク先の論文にもある通り、少なくとも18手が必要なことは証明されています。

まず、状態数は、角(3面見えている)が8個、辺(2面見えている)が12個のピースがあるので、辺のピースを1つ固定するとすれば、3⁸ x 2¹² x 8! x 11! = 43 252 003 274 489 856 000 通りあります。
最初の1手は18通りの選択肢 (36じゃないですよ) があり、2手目以降は15通りです (17通りでもないです)。ここから、17手以上必要あることが分かります。あとちょっと工夫すると、17手では不足で18手必要というのが分かるようです。

Re:最低18手

[Anonymous Coward]

おいおい、リンク先には「18手が必要なことは"証明されている"」なんて書いていない。
「18手が必要なことを示した」とでも言うのが妥当じゃないか？

>His research showed that the median optimal solution was 18 moves,
>and he believed any cube could be solved in no more than 20 moves.

>However, he was unable to prove this, and no one has ever been able to
> prove that it could be solved in less than 27 moves.

Re:最低18手

[phason (22006)]

18 movesが必要であることを示した(= 証明した)が，彼の信じる「20手あればすべて解ける」
を証明はできていない，ってんだから18手が要る事は証明されてんでは？
#確か17手で到達可能な全状態数と，ルービックキューブの取り得る全状態数を比較して後者の
#方が大きいから最低でも18手は必要，っていう証明だった気がする．

Re:最低18手

[Anonymous Coward]

数学では「示す」と「証明する」は同じ意味なんですが……。