L 게임

L 게임은 에드워드 드 보노(Edward de Bono)가 고안한, 4x4 판에서 진행하는 순수 실력 게임이다. 두 플레이어는 각각 정사각형 네 칸을 덮는 L자 모양 조각인 L 조각을 하나씩 가진다. 또한 각각 한 칸을 덮는 중립 조각이 두 개 있다. 목표는 상대가 자신의 L 조각을 더 이상 움직일 수 없는 위치로 몰아넣는 것이다.

각 차례에 둘 플레이어는 반드시 다음 순서를 지킨다.

1. L 조각 이동(필수). 자신의 L 조각을 들어 올려, 판 위 어디에나 어떤 방향으로든(밀거나, 돌리거나, 뒤집어서) 다시 놓는다. 새로 놓는 자리는 빈 네 칸을 덮어야 하며, 이번 차례 직전에 놓여 있던 자리와 달라야 한다.
2. 중립 조각 이동(선택). L 조각을 놓은 뒤, 중립 조각을 최대 한 개만 아무 빈 칸으로 옮길 수 있다. 중립 조각을 반드시 옮겨야 하는 것은 아니다.

상대가 자기 차례에 L 조각을 합법적으로 움직일 방법이 하나도 없으면, 그 즉시 현재 플레이어가 승리한다. 판은 작지만 게임은 깊다. 비좁은 위치에서는 L 조각이 갈 수 있는 곳이 몇 곳뿐이어서 예를 들어 2 x (6 + 6 + 1) = 26가지 수가 나오기도 하고, 가장 복잡한 위치에서는 서로 다른 수가 195가지에 이르기도 한다. 합법적인 위치는 모두 합쳐 18,000가지가 넘는다.

두 플레이어 모두 최선을 다해 둔다고 가정한다.

• 이기는 수란, 그 수를 둔 뒤에는 상대가 어떻게 응수하더라도 패배를 피할 수 없는 수이다.
• 어떤 수를 두더라도 여전히 패배로 이어진다면, 그 플레이어는 지는 상태이다.
• 어느 쪽도 승리를 강제할 수 없다면, 그 위치는 무승부이다(최선을 다하면 게임이 영원히 계속된다).

A가 둘 차례인 위치가 주어진다. A에게 이기는 수가 있는지 판단하라. 있다면 그러한 수 하나를 출력하고, 없다면 게임이 무승부인지 아니면 A가 지는지 판단하라.

입력은 진행 중인 게임을 나타내는, 각 줄에 네 글자가 있는 네 줄로 이루어진다.

• . — 빈 칸,
• x — 중립 조각,
• # — 플레이어 A의 L 조각,
• * — 플레이어 B의 L 조각.

플레이어 A가 둘 차례이다. 주어지는 위치는 항상 합법적이며, A에게는 합법적인 수가 최소한 하나 있다.

A에게 이기는 수가 있으면, 그 수를 둔 뒤(필수인 L 조각 이동과 선택적인 중립 조각 이동을 마친 뒤)의 위치를 입력과 같은 네 줄 형식으로 출력한다.

이기는 수는 여러 개일 수 있다. 답을 유일하게 만들기 위해, 결과 판이 사전순으로 가장 작은 이기는 수를 출력한다. 이때 판은 출력되는 네 줄을 줄바꿈 문자로 이어 붙인 문자열로 비교한다.

A에게 이기는 수가 없으면, 정확히 No winning move가 적힌 줄을 출력하고, 그 다음 줄에 최선을 다했을 때 게임이 무승부이면 Draw, A가 지면 Losing을 출력한다.