초보자용 루빅큐브 맞춤 동작열의 계산 (Computation of Move Sequences for Rubik’s Cube Solution for Beginners)

서지정보

· 발행기관 : 한국정보기술학회
· 수록지 정보 : 한국정보기술학회논문지 / 13권 / 2호 / 153 ~ 162페이지
· 저자명 : 박우전

초록

루빅큐브 풀이란, 주어진 큐브를 각 큐브면이 녹, 백, 청, 황, 주황, 적색 중 한 가지 색이 되도록, 큐브날개를 돌려 맞추는 것을 말한다. 2010년에 발견된 ‘신의 수 20’은, 한면 – 한가지 색인 큐브모양으로부터 20회이내의 동작으로 가능한 모든 큐브모양에 도달할 수 있다는 것을 알게 했다. 그러나 가능한 큐브상태 공간의 방대함으로 인해, 아직도 많은 연구자들은 주어진 큐브를 푸는 최소길이의 동작열 계산에 흥미를 느낀다. 같은 이유로 모든 큐브패턴의 DB입력은 불가능하며, DB에 의한 최소길이 동작열 계산은 한계가 있다.
큐브패턴 DB를 이용하는 큐브 풀이 시스템 개발을 위한 첫 걸음으로, 패턴 데이터베이스 이용에 앞서 큐브해법 알고리즘을 구현한다. 큐브데이터 및 연산을 하나의 Java클래스로 정의하고, 구현된 클래스를 사용하여, 초보자용 해법공식을 보완한 후, 공식의 단계별 메소드를 정의된 클래스에 구현한다. 구성된 큐브해법 시스템은 주어진 큐브를 24방향으로 놓고 각각의 경우에 대한 풀이 동작열을 생성한다. 주어진 큐브에 대한 우리의 큐브 해법시스템의 답은, 생성된 동작열의 단축과정을 거친 후의 동작열 중 최단 길이인 것들 중 하나이다. 또한 구현된 해법에 의한 맞춤 동작열의 길이를 단계별로 관찰하고, 기존 해법과 비교한다.

영어초록

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.

참고자료

· 없음