시계

|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|  (그림 1)
    G            H            I

3×3 격자에 아홉 개의 시계가 놓여 있다(그림 1). 목표는 되도록 적은 횟수의 조작으로 모든 바늘을 12시 방향으로 되돌리는 것이다. 바늘을 돌리는 방법은 아홉 가지가 있으며, 각 방법을 조작(move)이라 부르고 1부터 9까지 번호를 매긴다. 어떤 조작을 한 번 수행하면, 아래 그림 2에 따라 해당 조작의 영향을 받는 시계들의 바늘이 시계 방향으로 90도 회전한다.

조작   영향을 받는 시계

 1         ABDE
 2         ABC
 3         BCEF
 4         ADG
 5         BDEFH
 6         CFI
 7         DEGH
 8         GHI
 9         EFHI    (그림 2)

아홉 개의 정수가 주어지며, 각 시계의 초기 바늘 위치를 그림 1의 순서대로 A부터 I까지(첫째 줄 A B C, 둘째 줄 D E F, 셋째 줄 G H I) 나타낸다. 각 값의 의미는 0 = 12시 방향, 1 = 3시 방향, 2 = 6시 방향, 3 = 9시 방향이다. 아홉 개의 수는 여러 줄에 나뉘어 있거나 임의의 공백으로 구분될 수 있다.

모든 바늘을 12시 방향으로 되돌리는 가장 짧은 조작 순서를, 조작 번호를 오름차순으로 정렬하여 공백 하나로 구분해 출력한다. 같은 조작을 여러 번 사용한다면 그 번호를 사용한 횟수만큼 반복해서 적는다. 이 퍼즐의 최단 해는 항상 유일하므로 출력 순서도 하나로 정해진다. 이미 모든 바늘이 12시 방향이면 빈 줄을 출력한다.

각 값이 나타내는 바늘 위치는 다음과 같다.

0 = 12시 방향
1 = 3시 방향
2 = 6시 방향
3 = 9시 방향

그림 1의 배치에서는 조작 5, 8, 4, 9를 수행하면 모든 바늘이 12시 방향으로 돌아온다(순서는 상관없다).

3 3 0         3 0 0         3 0 0          0 0 0         0 0 0
2 2 2   5->   3 3 3   8->   3 3 3   4 ->   0 3 3   9->   0 0 0
2 1 2         2 2 2         3 3 3          0 3 3         0 0 0