삼목 게임 timer 1s memory 256MB

삼목 게임은 우리가 흔히 알고 있는 사목과 같은 게임이나, 더 작은 판에서 할 수 있도록 간단화된 게임이다. 

(참고로, 사목은 우리가 더 흔히 알고있는 오목의 다른 버전이다. 사목은 곧 설명할 삼목 게임을 바둑판에서 하면 된다.) 

삼목은 4x4 격자판에서 하는 게임이다. 흑의 시작으로, 흑돌과 백돌을 번갈아가면서 놓는다. 

돌을 놓는 방식은, 한 세로줄을 선택한 후, 그 세로줄에서 돌이 없는 가장 낮은 곳에 돌을 놓으면 된다. 

예를 들어 (3,1)에 돌을 놓기 위해서는, (2,1)과 (1,1)에 돌이 있어야 한다. 

“테트리스” 처럼, 돌이 위에서 떨어져 착지한다고 생각하면 된다.

흑과 백이 번갈아가면서 착수하다가, 가로, 세로 또는 대각선의 연속된 세 칸 이상에 자기 돌을 놓는 사람이 이기는 게임이다. 

모든 칸에 착수해서 게임이 끝나지 않는다면, 무승부이다.

게임은 흑이 (1, x)에 착수하면서 시작하여, 백이 (a, b)에 착수해서 백이 이기는 것으로 

끝났을 때 보드판의 각기 다른 상태를 모두 구하는 프로그램을 작성하라. 

착수한 순서는 중요치 않으며, 오직 끝났을 때, 보드판의 상태만 생각한다.​