이번 학기에 수강 중인 Computer Algorithm 강의에서 팀 프로젝트 과제가 2개 있었다. 이 글은 그 중 2번째 과제인 Sliding Puzzle에 관한 것이다.
문제
5*5 사이즈의 Sliding Puzzle이 있다. 24개의 퍼즐조각과 1개의 빈 칸이 있는데, 이 퍼즐을 완성하는 과정을 보여라. 완성된 퍼즐의 상태는 다음과 같다.
입력
퍼즐의 개수가 첫 줄에 주어지고, 이어서 각 퍼즐의 상태가 입력된다. 퍼즐의 상태는 25개의 수로 나열되는데, 이 중 1부터 24는 퍼즐조각을 나타내고, 25는 빈 칸을 나타낸다.
출력
각 줄에 퍼즐의 번호와, 빈 칸의 이동횟수, 이동과정(L, R, U, D)을 출력한다. 풀 수 없는 문제가 주어지면 -1을 출력한다.
입력 예시
15
1 2 3 4 5
6 7 8 9 10
11 12 13 14 25
16 17 18 19 15
21 22 23 24 20
1 2 3 25 4
6 7 8 9 5
11 12 13 14 10
16 17 18 19 15
21 22 23 24 20
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 25 18 19
21 22 23 24 20
1 2 3 4 5
6 7 8 9 10
11 12 13 14 25
16 17 18 20 15
21 22 23 19 24
1 2 3 4 5
6 7 25 8 9
11 12 13 15 10
16 17 18 14 20
21 22 23 19 24
1 2 25 4 5
6 7 3 9 10
11 12 8 13 15
16 17 18 14 24
21 22 23 20 19
1 2 3 5 10
6 7 8 25 4
11 12 13 9 14
16 17 18 19 15
21 22 23 24 20
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 22 17 19 20
25 21 18 23 24
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 25 20
21 22 23 19 24
1 25 2 3 4
6 7 8 9 5
11 12 13 14 10
16 17 18 19 15
21 22 23 24 20
6 1 2 25 4
7 3 8 9 5
11 12 13 15 10
16 17 18 14 20
21 22 24 19 23
7 6 2 3 5
1 8 25 4 10
11 12 13 9 15
16 17 18 14 20
21 22 24 19 23
6 1 2 3 4
11 12 7 8 5
16 17 25 9 10
21 18 13 14 15
22 23 24 19 20
1 2 3 4 5
6 7 8 9 10
11 12 14 19 15
16 17 25 13 20
21 22 18 23 24
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 24 23 25
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 25 19
21 22 23 20 24
출력 예시
#1 2 D D
#2 5 R D D D D
#3 3 R R D
#4 4 D L D R
#5 7 R R D L D D R
#6 10 D D R D R D L U R D
#7 8 R U L D D R D D
#8 6 R U R D R R
#9 2 D R
#10 7 R R R D D D D
#11 -1
#12 -1
#13 24 D L U U R R D D D L L L U U U U R R R R D D D D
#14 7 R U L D D R R
#15 -1
전략
문제는 위처럼 주어졌고, 6월 4일에 각 팀의 코드와 실행결과를 비교해보기로 예정되었다. 여러 개의 퍼즐이 입력으로 주어지고 일정 시간 내로 답을 출력하는 것이며, 유효한 출력결과에 대해 빈 칸의 총 이동횟수가 적을수록 높은 점수를 받는다. 즉, 최대한 정확하고 간결하며 빠르게 퍼즐을 맞춰야 하는 것이다.
우리 팀은 다음과 같은 결론을 내렸다.
- 빈 칸 이동의 최소횟수 및 그 경로를 찾자.
- 팀 당 코드실행 및 알고리즘 발표에 주어지는 시간이 수 분 내외이므로, 빠르게 경로를 찾자.
- 실행결과의 검증을 다른 팀이 직접 하도록 했으므로, 문제로 주어지는 퍼즐은 그 답이 간단할 것이다.
일반적인 A*, IDA* 알고리즘으로는 최단의 답을 정확히 구할 수 있지만, 빈 칸의 이동을 많이 요구하는 퍼즐일 수록 굉장한 시간과 메모리가 요구된다(실제로, 40번 이상의 빈 칸 이동이 필요한 퍼즐은 사실상 풀지 못한다.). 그런데 우리는 어떤 입력이 주어질지 모르므로, 무작정 이 알고리즘만을 이용하면 자칫 단 하나의 퍼즐도 풀지 못하게 될 수 있다. 이 문제를 해결하기 위해, 각 팀은 여러 방법을 선택했다. 어떤 팀은 5*5 퍼즐에서 일부만 먼저 맞추어 문제를 4*4 퍼즐로 간소화하고, 이를 다시 3*3 퍼즐로 간소화하는 방법을 택했다. 이 방법은 매우 빠르게 답을 구할 수 있지만, 최적의 답을 구할 수는 없다. 즉, 속도를 얻고 점수를 잃는 방식이다. 빈 칸의 이동횟수는 상관없이 퍼즐을 풀어내는 것만이 목표라면 이 방법은 아주 훌륭하다.
대부분의 팀은 놀랍게도 A* 또는 IDA*를 거의 그대로 이용했다. 복잡한 퍼즐이 주어지면 못 풀어낸다는 단점이 있는데, 놀랍게도 6월 4일 당일 주어진 문제와 모범 답안(최적의 답은 아니다)은 다음과 같았다.
실제로 주어진 입력
10
1 7 25 4 8
6 3 2 10 5
11 12 13 9 14
16 17 18 19 15
21 22 23 24 20
6 1 5 2 9
7 8 3 14 4
11 12 13 10 15
16 17 25 18 19
21 22 23 24 20
25 1 2 3 5
6 7 8 14 9
11 12 4 13 19
16 17 18 15 10
21 22 23 24 20
2 25 3 4 10
1 7 8 5 15
6 12 13 9 14
11 21 17 19 20
22 16 18 23 24
1 2 9 3 5
6 12 7 13 10
16 11 8 15 4
17 25 18 14 19
21 22 23 24 20
11 6 1 4 9
12 7 2 5 8
13 3 14 10 25
16 17 18 19 15
21 22 23 24 20
6 1 3 5 4
25 2 7 14 8
11 12 9 13 10
16 17 18 19 15
21 22 23 24 20
6 1 3 5 10
25 2 7 9 4
11 12 8 14 15
16 17 13 19 20
21 22 18 23 24
6 1 4 10 9
8 3 2 25 5
11 7 12 18 13
16 17 14 20 15
21 22 23 19 24
11 2 6 3 5
25 7 9 4 10
12 1 8 13 14
16 17 18 20 15
21 22 24 19 23모범 답안
#1 16 R R D L U L D L U R D R D R D D
#2 27 R R U L U U L D R U L D L L U R R R R D L U R D D D D
#3 18 R R D D R R D L U U L U R D R D D D
#4 31 D L U R D L U R R R D D R U U L L L D L D D R D L U R R D R R
#5 26 L U R R U U R R D D L U R U L D L D L U R D R D R D
#6 28 L L L L U U R R R D R U L L D D L L U U R R D R R D D D
#7 25 U R D R D R U L U R D R U L L D R R U L D R D D D
#8 15 U R D R R R U L D L D D D R R
#9 28 R U L D R U L L D L L U R R D L D R R R D L L U R D D R
#10 -1
따라서, 대부분의 팀이 굉장히 빠른 시간만에 문제를 풀어냈다. 오히려 어려운 문제가 나오기를 기대했던 팀들에게는 불리하게 작용했다. 개인적인 생각으로는 11번 문제로 빈 칸 이동이 50회 이상인 문제를 냈으면 어땠을까 싶다.
알고리즘
우리 팀은 약 10~40 정도의 빈 칸 최소 이동횟수를 요구하는 10개의 문제가 나올 것으로 예상했는데, 다행히도 거의 맞아떨어졌다. 하지만 높은 최소 이동횟수를 요구하는 문제가 나올 가능성도 있다고 추측했고, 이에 따라 최적의 답만을 구하려는 알고리즘을 약간의 튜닝(?) 했다. 이 알고리즘은 20대 이하의 이동횟수를 요구하는 퍼즐에 대해서는 최적(또는 거의 최적)의 답을 찾아내지만, 그 이상에서는 최적에 가까울 것으로 예상되는 일반적인 답을 찾아낸다. 그리고 아무 답이라도 좋으니 빨리 풀어내는게 중요하다 생각하여, 탐색이 길어질 수록 공격적인 탐색을 하도록 했다. 여기서 공격적인 탐색이란, 탐색의 기준을 빈 칸의 최소 이동횟수가 아니라 퍼즐의 완성도로 두는 것을 의미한다. 이를 통해, 최적의 답은 못 구할지라도 적당한 답을 빠른 시간내에 구할 것이라고 기대할 수 있다. 우리 팀의 코드는 다소 복잡한데, https://github.com/gunhoflash/SlidingPuzzle에서 확인할 수 있다.
우리 팀의 알고리즘은 score 값이 최소인 퍼즐 상태를 먼저 탐색한다. score 값은 다음과 같이 계산된다.
score = different * C + move여기서 move는 초기 상태로부터 현재 상태까지 빈 칸이 이동한 횟수이다. 그리고 different는 퍼즐이 완성된 정도로, 각 퍼즐조각이 목표위치와 떨어진 거리의 총합이다. 예를 들어 아래 퍼즐에서 different의 값은 8이다. 퍼즐조각 9, 10, 14, 15, 20이 목표위치로부터 각 1칸씩 떨어져있고, 25는 3칸 떨어져있기 때문이다.
따라서, score가 최소이려면 빈 칸의 이동이 낮은 상태이면서 높은 완성도를 가지고 있어야 한다. 그런데, C의 값이 클 수록 different가 score에 결정적인 영향을 주게 된다. 이 값이 높을수록 공격적인 탐색이 되는 것이다. 그래서 우리 팀의 알고리즘은, 탐색하는 퍼즐 상태가 많아질수록 C가 높아지도록 함으로써 different와 move의 비율이 처음에는 1:1에서 2:1, 3:1로 변해가도록 했다.
(한편, 빈 칸을 한 번 이동하면 different는 최대 2만큼 감소하므로, C가 0.5일때 score는 퍼즐을 완성하기 위한 빈 칸 이동횟수의 lower bound라고 고려할 수도 있다.)
물론 훨씬 간결하고 빠르고 정확한 알고리즘이 많겠지만, 역량이 부족하여 이 정도만 하게 되었다. 5*5 또는 그 이상으로 큰 퍼즐에 대해서는 그 풀이방법이 다양하고 아직 빈 칸의 이동횟수에 대한 최댓값이 optimal하지 않은 것으로 알고 있다(152이상 205 이하인 것 같다.). 앞으로도 많이 공부해 볼 만한 문제다.