[뉴스] Northeastern 대학교 연구발표: 모든 3x3x3 큐브 26회전이면 충분하다!! 논문 첨부됨.

[최일규.]

"Northeastern University Researchers Solve Rubik's Cube in 26 Moves". Detailed paper.

Northeastern 대학교 연구발표: 모든 3x3x3 큐브 26회전이면 충분하다!! 논문 첨부됨.

Northeastern 대학교 연구발표 모든 3x3x3 큐브 26회전이면 맞춘다

대부분의 아이들이 한때 한번쯤은 가지고 놀았을만한 장난감이기는하지만 Northeastern 대학교 컴퓨터 과학과 교수 Gene Cooperman과 대학원생 Dan Kunkle의 연구 결과는 애들놀음이 아니다. 둘은 큐브를 어떻게 섞든지간에 26회전이면 충분히 맞출수있다는 연구 결과를 내놓았다 -- 새로운 발견이다. 역사적으로 가장 적은 회전수는 27회전이였다. 이 인기많은 퍼즐에대한 놀라운 관심은 왜일까?

"큐브는 조사와 경우의 수의 문제들을 유용하게 풀수있는 대상이다." Cooperman이 말했다. "조사와 경우의 수는 인공지능부터 작업까지 다양한 분야의 연구원들을 필요로하는 큰 연구 영역이다. 큐브는 연구분야가 다른 연구원들의 여러가지 조사방법들을 하나의 잘알려진 문제에 적용하여 서로 비교분석할수 있도록 해준다."

Cooperman과 Kunkle은 이 새로운 기록인 연구결과를 두개의 큰 방법으로 성취할수있었다: 그들은 RAM의 확장으로 7테라바이트의 큰 용량을 크나큰 표들을 저장하기위해 사용하였고 수학적 그룹이론을 이용하여 회전, 그리고 그룹의 회전을 더 빠르게 계산할수있는 방법을 개발하였다.

Cooperman과 Kunkle은 수학적 그룹이론에서는 집합의 가족이라불리는 곳인 구성의 집합의 가족에다가 큐브의 모든 경우의 수를 집어 넣었다. 그후, 그들은 한 회전을 모든 집합에 적용하여 그 결과를 보았다. 수학적 그룹이론의 새로운 기술을 이용하여 이 방법을 100,000,000회/초로 컴퓨터에 적용시켰다.

지난 1997년 5월, U.C.L.A. 컴퓨터 과학 교수 Richard Korf는 기본적인 큐브의 이상적인 해결책을 찾았다고 발표하였다. 그의 발표에 의하면 이상적인 회전수의 중앙값은 18회전이고, 그는 모든 큐브가 최대 20회전이면 맞추어질수있다고 믿었다. 하지만, 이것을 증명할수없었고, 그 이후로 아무도 27회전 아래로 큐브를 맞출수있다고 증명할수있는 사람이 나타나지않았다.

"Korf는 큐브의 하나의 상태에대해서 이상적인 해결책을 찾기위해 오랜시간이 걸리는 프로그램을썼다" Kunkle이 말했다. "우리 프로그램은 처음에는 계산을 약간은 미리해놓고, 그리고 매우빨리 - 약 1초안에 - 큐브가 어떠한 상태에있더라도 26회전, 혹은 그 아래의 회전으로 맞출수있는 해결책을 제시 한다."

Cooperman과 Kunkle은 20테라바이트의 저장소를 받기위해 2006년 National Science Foundation에서 Cooperman과 동료들이 받은 200,000불을 이용하여 Northeastern 대학에 있는 Teragrid 컴퓨터 들을 이용하였다.

늦 1970년에 헝가리에서 Erno Rubik에의해 발명된 큐브는 아마도 이시대의 가장 유명한 조합 퍼즐 일것이다. 큐브는 10억가지의 조합을 나타낸다고들 표현하지만, 이는사실 과소 평가한것이다. 사실은, 4.3조 (4.3252 x 10^19) 보다도더 많은 조합의 다른 경우의 수가 존재한다.

아래는원문

Northeastern University Researchers Solve Rubik’s Cube in 26 Moves

It’s a toy that most kids have played with at one time or another, but the findings of Northeastern University Computer Science professor Gene Cooperman and graduate student Dan Kunkle are not child’s play.  The two have proven that 26 moves suffice to solve any configuration of a Rubik's cube – a new record.  Historically the best that had been proved was 27 moves. 

Why the fascination with the popular puzzle?

“The Rubik's cube is a testing ground for problems of search and enumeration,” says Cooperman.  “Search and enumeration is a large research area encompassing many researchers working in different disciplines – from artificial intelligence to operations.  The Rubik's cube allows researchers from different disciplines to compare their methods on a single, well-known problem.”

Cooperman and Kunkle were able to accomplish this new record through two primary techniques: They used 7 terabytes of distributed disk as an extension to RAM, in order to hold some large tables and developed a new, “faster faster” way of computing moves, and even whole groups of moves, by using mathematical group theory.

Cooperman and Kunkle put all of the configurations of a Rubik's cube in a family of sets of configurations (called a family of cosets in mathematical group theory).  They then looked at the result of applying a single move to all of the configurations of a coset at once.  They simulated this on a computer at a rate of 100,000,000 times per second, using a new technique in mathematical group theory.

In May 1997, U.C.L.A. computer science Professor Richard Korf announced that he had found the first optimal solutions to Rubik's Cube. 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.

“Korf had written a program that spends a long time to find optimal solutions for single states of the Rubik's cube,” says Kunkle.  “Our program first does a large pre-computation and then it very quickly - in about a second - finds a solution in 26 moves or less for any state of Rubik's cube.

Cooperman and Kunkle used computers at Teragrid (teragrid.org) and at Northeastern, part of the first node from a $200,000 grant Cooperman and colleagues received from the National Science Foundation in 2006 to obtain 20 terabytes of storage.

Rubik's Cube, invented in the late 1970s by Erno Rubik of Hungary, is perhaps the most famous combinatorial puzzle of its time.  Its packaging boasts billions of combinations, which is actually an understatement. In fact, there are more than 43 quintillion (4.3252 x 10**19) different states that can be reached from any given configuration.

출처: http://www.speedcubing.com/

http://www.neu.edu/nupr/news/0407/rubik.html

번역: 최 일 규

무단 복재, 배포를 금합니다.

번역문의 저작권은 최일규에게 있음을 알려드립니다.

이 글을 허가 없이 무단으로 도용하실 경우

법적 책임을 물을 수도 있으니 주의해주시기 바랍니다.

[최호림]

메가밍크스도 26회전에 가능한가..

[한지원]

그건 좀;;

[Cubeο]

모든큐브라고 되있는데 ...ㄷㄷ.... 아닌가요?

[이준용]

모든33큐브아닐지..

[램。]

모든 333큐브일거같아요...444도 26회전은 불가능할건데..

[[TC]신동운]

모든 큐브 ㄷㄷㄷ

[큐브™]

기가밍크스가 만약 그러먼 ㅇㅅㅇ

[이뱅]

헐ㄱ-;;

[Rubix-cube]

22는 물론 가능 하겠지만 33은 아무리 생각해도,,,

[이동주2]

오호~~!!

[박현수]

음....프리드리히라도 26은 힘들지 않나요?? ㅇㅅㅇ

[박건영.]

최소회전수잖아여 ㅋㅋ

[[TC]신동운]

그래서 맞추는 방법은요??

[유정도]

모든큐브가 26회전? ㄷㄷ

[공민욱]

저 333은 20회전이내로 맞출수 있는 프로그램이 있음,. ㄷㄷ

[큐브™]

26회전이라... 27회전은 그럼 누가한거죠?

[[TC]신동운]

운영자 다운 명석한 해답입니다.

[서민국]

26회전이라;;;;;;; 저는 F2L도 안끝났는데 26회전 넘어가네요~ ㅎㅎ

[못難놈]

허머나 난 100회정도회전해서 1분인데 ㄷㄷㄷ;;; 어덯게26회전을 허거걱;;;;;

[레빈s]

흠?

[최일규.]

네, 모든 3x3x3 큐브로 수정했습니다~

[이따봐요]

쌩뚱맞은 소리지만 저랑 이름이 비슷하세요...

[이수찬]

프로그램 원리는 이해가 전혀;;

[안큐]

이제 큐브인들은 필요없다는건가..

[윤주형]

오래걸려도 맞추는 즐거움이 있잖아요 ㅋㅋ

[행님]

20회전도 가능한데....

[박승권]

그대신 그 공식이 무지 많고 어려울듯...

[수준미달큐버]

흠 공식 많이 어려울듯 싶네요

[김무성]

제가 가진 프로그램으로 해본 결과 아무리 복잡하게 섞어도 21회전안에는 맞춰지든데요.. 특별한 규칙이 있긴 한거 같든데.. 그걸 알고 싶을 따름...

[윤한슬]

큐브 익스플로어를 만든 사람이 원리를 알고 있을거라 생각햇었는데...