2009/11/18 郭君逸教授專題演講
演講者：
單 位：
日 期：2009年11月18日 PM 14:30
地 點：國立高雄大學理學院408室
講 題：
摘 要：
The upper bound of the number of moves required to solve any state of Rubik's cube has been a matter of long-standing conjecture for over 25 years (since Rubik's cube appeared. This number is called "God's number"). The bound of 17 to 52 was first proved in 1982. An upper bound of 29 was produced in the early 1990's. Silviu Radu proved the new upper bound of 27 in 2006. Gene Cooperman and Dan Kunkle prove that 26 moves suffice, but there is yet a gap in the paper. This gap seems to be fixed, but the corrected paper is not available yet. In May 2008 Tomas Rokicki proved, that 23 moves suffice, analyzing more than 200,000 cosets of the phase 2 subgroup of the Two-Phase-Algorithm. This is indeed a big leap forward! There is still no paper available for the proof, but the method is similar to the method Rokicki describes in for 25 moves. In August 2008 Tomas Rokicki reduced the upper bound to 22 moves after having analyzed 1:28 million cosets within 50 core-years of CPU time. A paper will be available soon. In this talk, I will show a combinatorial approach to counting in Rubik's cube and a general solution to every twisty puzzle.