TopCoder Statistics - Problem Statement

Problem Statement

Tic-Tac-Toe is a game played on a 3x3 board. The players alternate claiming spots on the board until one player has 3 spots in a row (horizontally, vertically, or diagonally), or there are no spots left to claim. The first player to move will always use 'O's to claim his spots whereas the second player will use 'X's. Claiming 3 spots in a row means you win and play stops. If no spots are left and nobody has won, the game is a draw.

By examing a Tic-Tac-Toe board it is often possible to determine whether a particular player should win. More precisely, a player should win if there exists a sequence of moves such that, regardless of his opponent's moves, he will always win. Another way of saying this is, a player should win a given position if playing the right moves will always produce a win regardless of the opposition's efforts to thwart his victory.

You will be a given a String[] board describing the current state of the game. board will contain 3 elements representing the rows of the board. Each element will contain 3 characters representing the spots in that row. For example:

board = {"XO."
         "..."
         ".OX"}

As seen above, the 'X's and 'O's represent each player's respective moves and the '.'s represent unclaimed spots. Your method will return a String according to the following rules:
1) If the board position is invalid (could not be achieved through a succession of valid moves) return "INVALID"
2) If the first player (player using 'O's) should win or has already won return "FIRST"
3) If the second player (player using 'X's) should win or has already won return "SECOND"
4) Otherwise return "DRAW"
In the example above the board position is valid and the first player should win so you would return "FIRST". Note, rule 1 has precedence over the other rules.

Definition

Class:: TicSolver
Method:: whoWins
Parameters:: String[]
Returns:: String
Method signature:: String whoWins(String[] board)
(be sure your method is public)

Constraints

board will contain exactly 3 elements
Each element of board will contain exactly 3 characters
Each character in board will be one of 'X', 'O', or '.' (quotes for clarity)

Examples

{"OX.", "...", "..."}

Returns: "FIRST"

If the first player plays the center spot, the second player is forced to block him in the lower right spot: OX. .O. ..X The first player can then play the lower left spot thus giving him two ways to get three in a row. Since this line of play is unstoppable by the second player, the first player should win.
{"O..", ".X.", "..."}

Returns: "DRAW"

Nobody has a line of play that will assure victory.
{"OXO", "OOX", "X.X"}

Returns: "DRAW"

The first player has only one choice leading to a draw.
{"OOO", "XX.", "..."}

Returns: "FIRST"
{"OOO", "XXX", "..."}

Returns: "INVALID"
{"...", "...", "..."}

Returns: "DRAW"
{"O..", "XX.", "..."}

Returns: "INVALID"

The second player has gone twice, but the first player has only gone once.
{"O..", ".X.", "..O"}

Returns: "DRAW"
{"O.X", "...", "..."}

Returns: "FIRST"
{"O..", "...", "..X"}

Returns: "FIRST"
{"O..", "...", "..X"}

Returns: "FIRST"
{"XXX", "OO.", "OO."}

Returns: "INVALID"

Looking at the number of spots occupied it is clear that the first player has just moved. It is impossible then, that the second player has already won.
{"O.O", "XX.", "O.X"}

Returns: "FIRST"
{"OOO", "X..", "XX."}

Returns: "INVALID"
{"OXO", "X.X", "OXO"}

Returns: "FIRST"
{"OOO", "XOX", "XXO"}

Returns: "FIRST"
{"OOO", "XOX", "XXO"}

Returns: "FIRST"
{"OOO", "XOX", "XOX"}

Returns: "FIRST"
{"OXO", "XOX", "OXO"}

Returns: "FIRST"
{"OOO", "XXO", "XXO"}

Returns: "FIRST"
{"OOO","O.X",".XX"}

Returns: "FIRST"
{".X.","OOO","OXX"}

Returns: "FIRST"
{"OX.",".XO","O.X"}

Returns: "FIRST"
{"XO.","X.O","O.X"}

Returns: "FIRST"
{"O.X","..O","XOX"}

Returns: "FIRST"
{"OX.","..O","XOX"}

Returns: "DRAW"
{"O.O","XX.",".OX"}

Returns: "FIRST"
{"OOX","X..",".OX"}

Returns: "FIRST"
{"OXX",".O.",".OX"}

Returns: "DRAW"
{"OO.","...","XX."}

Returns: "FIRST"
{"X..","OOO",".X."}

Returns: "FIRST"
{".OX","X.O","OX."}

Returns: "DRAW"
{"X..","XOO","OX."}

Returns: "FIRST"
{"O.X","..O","X.."}

Returns: "FIRST"
{"...","..O","..."}

Returns: "DRAW"
{"X..","...","O.."}

Returns: "FIRST"
{"X.O","...","O.."}

Returns: "FIRST"
{"OO.","XOX","XO."}

Returns: "FIRST"
{"OXX","OOX","XO."}

Returns: "FIRST"
{"...","O..","XO."}

Returns: "DRAW"
{"OX.","XO.","XO."}

Returns: "FIRST"
{"OXX","...",".O."}

Returns: "FIRST"
{"OOX","X.O","XXO"}

Returns: "FIRST"
{"O..","X..",".XO"}

Returns: "FIRST"
{".O.","OXX","X.O"}

Returns: "DRAW"
{"O.X","OXX","..O"}

Returns: "FIRST"
{"OOX","X..","..O"}

Returns: "SECOND"
{".XX","OX.","O.O"}

Returns: "FIRST"
{"OX.","O.X","XOO"}

Returns: "DRAW"
{"O.X",".OX","XOO"}

Returns: "FIRST"
{"XOX","..X","OOO"}

Returns: "FIRST"
{"..X","OOX","XXX"}

Returns: "INVALID"
{"X.O","XXO","OXX"}

Returns: "INVALID"
{"XX.","XOX","O.X"}

Returns: "INVALID"
{"X..",".XO","O.X"}

Returns: "INVALID"
{"..X","XOO","XOX"}

Returns: "INVALID"
{"..X","XOX","OOX"}

Returns: "INVALID"
{".OX","XO.","X.."}

Returns: "INVALID"
{".OX","X..","..."}

Returns: "INVALID"
{"XXX","...","XO."}

Returns: "INVALID"
{"O.X","OOO","XXO"}

Returns: "INVALID"
{"O..","OXO",".XO"}

Returns: "INVALID"
{"O.O",".O.","X.O"}

Returns: "INVALID"
{"OX.","O.O","X.O"}

Returns: "INVALID"
{"OOO","O.O",".OO"}

Returns: "INVALID"

Statistics

Problem Statement for "TicSolver"

Problem Statement

Definition

Constraints

Examples