Tic-Tac-Toe

Everyone is familiar with the children's game of Tic-Tac-Toe. One player is X, the other player is O. The players in turn (X goes first) place their mark in a previously unoccupied square of a 3 × 3 grid. A player who gets three of his marks in a row, across, down, or diagonally, wins the game. There are 8 ways to win. If the board is filled without either player getting 3 in a row, the game “goes to the cat,” and there is no winner.

Given a valid configuration of the board at some point during a game, you are to determine, assuming both players make their best possible moves for the remainder of the game, which player will win or whether the game will go to the cat.

Input Specification

The first line of the input will consist of a decimal integer N between 1 and 100 inclusive, representing the number of test cases to follow. What will then follow are N lines, each 9 characters long. These 9 characters will be from {X, O, B}, representing whether X or O occupies the square or whether the square is blank. The squares are listed in this order: the top row (left to right) followed by the middle row (left to right) followed by the bottom row (left to right). You may assume the board is a valid configuration of an incomplete game of Tic-Tac-Toe. There will be no extra spaces or newline characters in the input.

Output Specification

The test cases in the output should appear in the order in which they appear in the input. For each test case, you are to print one of the following strings: “X wins the game.”, “O wins the game.”, or “The game goes to the cat.”, depending on the output of the game. Each line should appear EXACTLY as specified and should be terminated by a newline character. No extra newline characters should appear in the output.

Sample Input

1. 2
2. XOBBBBBBB
3. BBBBBBBBB

download as text file

Output for Sample Input

1. X wins the game.
2. The game goes to the cat.

download as text file

Original Problem

NMU Invitational Programming Contest, 2000