루빅스 큐브 솔버

문제

루빅스 큐브는 1974년 Ernő Rubik이 발명한 입체 퍼즐로, 작은 정육면체 26개로 이루어져 있다. 작은 정육면체마다 겉으로 드러난 면이 1개에서 3개까지 있고, 드러난 면은 모두 54개다. 드러난 면에는 여섯 가지 색 중 하나가 칠해져 있으며, 한 색이 정확히 아홉 면을 덮는다. 큐브는 아무 면이나 90도 돌려서 조작한다. 여섯 면이 각각 한 가지 색으로만 덮이면 큐브가 맞춰진 것이다.

당신은 루빅 대학교의 연구원이고, 어떤 초기 상태에서든 가장 적은 횟수로 큐브를 맞추는 알고리즘을 연구한다. 이 연구에는 큐브 배치를 읽어 조작을 수행하고 그 결과가 맞춰진 상태인지 판정하는 프로그램이 필요하다.

입력

입력은 큐브의 시작 배치 하나와 그 배치에 수행할 조작 하나 이상으로 이루어진다.

배치는 다음과 같은 아홉 줄이다.

      G W O
      G R R
      G B R
B R B R G Y W W W Y G O
G W B O G B Y B O W Y O
W R Y O Y B R Y R G O O
      B R Y
      B O W
      G Y W

이 아홉 줄은 아래 전개도를 따른다.

격자의 각 문자는 겉으로 드러난 면 하나의 색이다. 같은 줄의 문자 사이에는 공백이 하나씩 있고, 줄의 첫 문자 앞에는 공백이 여러 개 올 수 있다. 격자는 큐브를 펼쳐 평면에 늘어놓은 모습이고, 문자 9개(3 × 3 배열)가 큐브의 한 면이다. 처음 세 줄은 큐브의 윗면이다. 다음 세 줄은 왼쪽면, 앞면, 오른쪽면, 뒷면을 이 순서로 담는다. 마지막 세 줄은 아랫면이다.

배치 다음에는 조작이 한 줄에 하나씩, 하나 이상 주어진다. 조작은 모두 12가지이고, 각각 작은 정육면체 9개로 이루어진 면 하나를 90도 돌린다. 한 번 돌릴 때마다 색이 칠해진 정사각형 20개가 움직인다. 돌아가는 면의 8개와 그 면을 이루는 작은 정육면체의 옆면 12개다. 12가지 조작과 수행 방법은 아래 표에 있다.

입력은 데이터 집합 1개 이상 100개 이하로 이루어지고, 데이터 집합 사이에 빈 줄은 없다. 데이터 집합 하나는 다음 네 부분으로 이루어진다.

시작 줄. START 한 줄이다.
큐브의 시작 배치. 모두 9줄이다.
조작. 한 줄에 하나씩 하나 이상 주어진다.
끝 줄. END 한 줄이다.

마지막 데이터 집합 다음에는 ENDOFINPUT 한 줄이 온다.

조작	수행 방법
`front left`	앞에서 볼 때 앞면을 반시계 방향으로 돌린다
`front right`	앞에서 볼 때 앞면을 시계 방향으로 돌린다
`left left`	왼쪽에서 볼 때 왼쪽면을 반시계 방향으로 돌린다
`left right`	왼쪽에서 볼 때 왼쪽면을 시계 방향으로 돌린다
`right left`	오른쪽에서 볼 때 오른쪽면을 반시계 방향으로 돌린다
`right right`	오른쪽에서 볼 때 오른쪽면을 시계 방향으로 돌린다
`back left`	뒤에서 볼 때 뒷면을 반시계 방향으로 돌린다
`back right`	뒤에서 볼 때 뒷면을 시계 방향으로 돌린다
`top left`	위에서 볼 때 윗면을 반시계 방향으로 돌린다
`top right`	위에서 볼 때 윗면을 시계 방향으로 돌린다
`bottom left`	아래에서 볼 때 아랫면을 반시계 방향으로 돌린다
`bottom right`	아래에서 볼 때 아랫면을 시계 방향으로 돌린다

출력

데이터 집합마다 정확히 한 줄을 출력한다. 큐브가 맞춰졌으면 Yes를, 맞춰지지 않았으면 No를 출력한다.