哪段程式碼最能代表程式設計師的暴力美學？

2018-03-04知識

證明：任意組合的三階魔術方塊，均可在20步之內還原。

先看看Reddit上對於這個問題的討論

This is a great example of brute force. I thought this would be proved by maths, but they just tested all the possible(relevant) cases, I love it.

路人甲：暴力證明的典範！簡單粗暴的證明！

Brute force never fails, unless of course you’re not using enough of it.

炮灰乙：沒有什麽問題是暴力解決不了的！如果有，那就再暴力一點！

據傳，三階魔術方塊有約合4.3千兆種不同的可能組合狀態[註1]。就算是每秒鐘能轉出十種不同組合的神級玩家，想要嘗試所有的組合，也要花1500億年的時間才能如願 (作為比較，我們的宇宙目前還不到 140 億歲)。

因此，「三階魔術方塊的最小還原步數」也被稱為「上帝之數」。在此之後的三十多年中，數學家們透過多次助攻一步步收窄上帝之數的範圍。

然而最後，人頭被谷歌舊金山總部的超級主腦電腦搶走[註2]。下面是由電腦模擬出的每種步數對應的狀態總數，同時也證明了三階魔術方塊的上帝之數是20。

最後是一些小註釋~

1.計算三階魔術方塊可能的組合狀態總數

魔術方塊的中心塊不可變化位置；

魔法的8個角塊各有3個方向，在不同位置、方向的可能性為 8!\times 3^{8} 種；

魔術方塊的12個棱塊各有2個方向，在不同位置、方向的可能性為 12!\times 2^{12} 種；

另外，如果你拆解並還原過魔術方塊，會出現以下3種情況：

有一個角塊方向需要調整，出現這種情況只有 \frac{1}{3} 的可能性可以正常還原魔術方塊；

有兩個角塊的位置需要互換，有 \frac{1}{2} 的可能性可以正常還原魔術方塊；

有兩個棱塊的位置需要互換，有 \frac{1}{2} 的可能性可以正常還原魔術方塊。

所以只有 \frac{1}{3}\times\frac{1}{2}\times\frac{1}{2} 的可能性可以直接還原魔術方塊。

即三階魔術方塊可能的組合狀態總數為

8!\times 3^{8}\times 12!\times 2^{12} \times\frac{1}{3}\times\frac{1}{2}\times\frac{1}{2}=43252003274489856000種

2.遍歷所有組合狀態的步驟

首先將魔術方塊狀態群根據 H\left(<U,R2,F2,D,L2,B2> \right) 子群分解成 2217093120 個右陪集，其中每個陪集中的元素個數為 19508428800 。

利用魔術方塊的對稱性（即對於狀態A及整體轉動S, S^-1 A S和A同解）將陪集的個數降為 55882296 ，即約為總量的 \frac{1}{40} 。

暴力求解每個陪集。

參考資料：

God's Number is 20

Super flip