TopCoder problem "GomokuBoardChecker" used in SRM 261 (Division II Level Three)

Problem Statement


Gomoku, also called go-moku (Japanese: Gomoku Narabe, "five points") is a tic-tac-toe-like game played on a rectangular board divided into unit squares. There are two players, and each of them has an infinite supply of pieces of his color. They alternately place their pieces on the board in an attempt to place five (or more) of their own pieces in a row (horizontally, vertically, or diagonally). As soon as one of the players has reached this goal, the game ends and he is the winner. If and only if no player has reached the goal and the whole board is full, the game is a draw.

You will be given a String[] board containing a position in the game, with the letter 'X' used to denote pieces of one player, the letter 'O' (not zero!) the pieces of the other player and '.' (period) to denote empty spaces. (Note that you don't know whether the player that started the game used 'O's or 'X's.)

Your task is to write a function that decides:

  • whether this is a valid position (i.e., one that could arise if both players played according to the rules), and
  • whether a player already won.

If the position is not valid, return the string "INVALID". If the position is valid and represents a draw game, return the string "DRAW". If the position is valid and one of the players won, return "X WON" or "O WON" respectively. Otherwise, return the string "IN PROGRESS".



Method signature:String check(String[] board)
(be sure your method is public)


-Either of the players could have started the game.
-Each square of the board may contain at most one piece.


-board will contain between 1 and 15 elements, inclusive.
-Each element of board will contain between 1 and 15 characters, inclusive.
-Each element of board will contain the same number of characters.
-Each element of board will contain only the characters 'X', 'O' and '.' .


Returns: "O WON"
Clearly, player "O" started the game and won.
Returns: "O WON"
This time, player "X" started the game, but player "O" won.
Returns: "INVALID"
This is an invalid position because players have to alternate placing the pieces.
Returns: "IN PROGRESS"
According to the problem statement, this is a game in progress (even though nobody can win on a 4x4 board).
Returns: "O WON"
Returns: "INVALID"
Returns: "DRAW"

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Brute Force, Simple Search, Iteration