초보자용 루빅큐브 맞춤 동작열의 계산

다국어 초록 (Multilingual Abstract)

Solving Rubik’s cube means making a given cube to have each cube-face with one color, either of green, white, blue, yellow, orange, or red by rotating planes of the cube. ‘God’s number 20’ found in 2010 showed that any cube configuration can be obtained by less than or equal to 20 moves from the one-face one-color configuration. However, due to the enormous size of state space of cube, many researchers are still interested in computing the minimum length of move sequence for a given cube configuration. With the same reason, all cube patterns cannot be input to pattern database. Thus, there is a limit for computing the minimum length of solution move sequence by using cube pattern database.
As the first step to develop a cube solution system utilizing cube pattern database, we implement a cube solution algorithm before utilization of pattern DB. After defining a class for the data and operations of the cube, we implement methods according to a beginner’s cube solution guide step by step into the class. Our cube solution system solves a given configuration by changing the up-front edge in 24 ways and produces one move sequence for each case. The answer of our cube solution system for a given configuration is one of the sequences with the shortest length which are obtained by shortening the produced sequences for the configuration. In addition, we observe the length of move sequence at each step, and compare the length to the one of existing solution.

참고문헌 (Reference)

1 박우전, "바둑게임 패턴 데이터베이스의 설계 및 구현" 한국정보기술학회 7 (7): 173-180, 2009

2 汪光, "루빅큐브의 패턴데이터베이스 설계 및 구현" 한남대학교 대학원 2014

3 "http://www.ws.binghamton.edu/fridrich/cube.html"

4 "http://www.worldcubeassociation.org/results/"

5 "http://www.sks1004.com/ 3x3 Edison Cube"

6 "http://ruwix.com/the-rubiks-cube/mathematics-of-therubiks-cube-permutation-group/"

7 "http://ruwix.com/home/"

8 "http://rubiks.com/"

9 "http://math.berkeley.edu/~hutching/rubik.pdf"

10 "http://cubesci.tistory.com/"

11 "http://cubekorea.cyworld.com/"

12 "http://cube20.org"

13 T. Y. Kim, "Report - Implementation of the cube simulation program through the analysis of Rubik's Cube" Korea Foundation for the Advancement of Science and Creativity 2013

14 Tomas Rokicki, "God's number is 20"

15 Richard E. Korf, "Finding Optimal Solutions to Rubik's Cube Using Pattern Databases" 700-705, 1997

16 Sturtevant, Nathan R., "Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters" 2014

17 Erik D. Demaine, "Algrithms for Solving Rubik’s Cubes" Springer Berlin Heidelberg 689-700, 2011