Rubik's Race(루빅스 레이스) 풀이

게임하러 가기: https://joonas-yoon.github.io/rubik-s-race/

Rubik's Race

개발기: https://joonas.tistory.com/120

---

게임을 계속 해보면, 사람의 직관으로 풀리기는 한다. 이러한 직관을 나름 생각해본 알고리즘(풀이) 글로 옮길까한다.

 

풀이

먼저, 게임의 목표는 주어진 3x3 패턴에 맞게 5x5의 중앙에 위치한 3x3 자리를 똑같게 만드는 것이다.

1번부터 9번까지의 칸에 맞는 색깔을 하나씩 채우면 된다. 순서대로 색깔을 맞추면서, 맞춰진 색깔의 칸은 움직이지 않도록 고정한다.

빈칸으로 원하는 색깔을 옮기는 것이 또 다른 문제인데,
위 그림과 같이 9번 칸에 주황색을 채우는 상황을 생각해보자.

검은색 화살표처럼 주황색 칸과의 경로가 만들어지고, 이 경로대로 빈칸을 계속 움직인다면 주황색이 조금씩 전진해서 그림의 빈칸(9번) 자리에 언젠가는 도착하게 된다.

빈 칸 → 주황색의 경로와 주황색 → 빈칸의 경로가 서로 겹치지 않도록 주의해야 한다.

여기에는 여러 경우가 있다. 그중에서, 주황색 칸까지의 경로가 가장 짧은 것을 선택하면 더 적은 움직임으로 채울 수 있다.

이미 채운 칸(위 그림에서 1, 2번 칸)은 건드리지 않기로 했기 때문에, 경로를 찾을 때 그 부분은 피한다.

 

요약

1. 9개의 칸을 패턴에 맞게 하나씩 채운다.
2. 채우는 칸을 찾을 때, 빈칸과 가장 가까운 경로를 만드는 색깔 칸을 고른다. (이미 패턴에 맞게 채운 칸은 건드리지 않는다.)
3. 원하는 색깔을 그 자리에 채울 때까지, 찾은 경로대로 빈칸을 움직인다.
4. 1~3번 과정을 모든 패턴을 맞출 때까지 반복한다.

 

최악의 경우를 계산해 봤을 때, 총 700번을 움직인다. 근데 이런 경우가 나오기는 굉장히 힘들다.
위 풀이대로 한다면 100~200번 내외로 풀린다.