Problem Statement |
| | Connect Four is a two-player board game played on a grid with 6 rows and 7 columns. The game starts with an empty board, and players take alternate turns dropping stones down non-full columns. At each turn, a player drops a single stone down a single column. The stone then occupies the bottom-most unoccupied square on that column.
a b c d e f g
6 . . . O . . .
5 . . . X . . .
4 . . . O . . .
3 . . . X . . .
2 . . . O . X .
1 . . X X O O X
Here a '.' denotes an unoccupied square; the first player's stones and the second player's are represented by 'X' and 'O' respectively. In the example above, it's the second player's turn to drop a stone in one of the six valid positions: a1, b1, c2, e2, f3, and g2.
The game ends when a player wins by placing at least four of his/her stones consecutively in at least one line, either horizontally, vertically, or diagonally. In the following example, the first player has successfully placed four stones in a line (d5-e4-f3-g2) thus winning the game.
a b c d e f g
6 . . . O . . .
5 . . . X . O .
4 . . O O X X O
3 . . O X O X X
2 O . X O X X X
1 O . X X O O X
The game may also end in a draw if the board is completely filled without anyone winning. After a game ends, the players are not allowed to drop more stones onto the board.
You will be given a String[], board, representing the 6 rows in a top-down manner. Each element of board will have exactly 7 characters representing the squares in a row from left to right: '.' denotes an empty square; 'X' denotes a stone of the first player; and 'O' denotes a stone of the second player. Write a class ConnectFour with a method judge which takes a board configuration represented by a String[] and returns a String of one of the six possible values:
- "first player moves" - return this when it's the first player's turn to drop a stone.
- "second player moves" - return this when it's the second player's turn to drop a stone.
- "first player wins" - return this when the first player has won the game.
- "second player wins" - return this when the second player has won the game.
- "draw game" - return this when the board is full and neither player wins the game.
- "invalid" - return this when it's impossible to produce the given board without violating the rules (e.g. dropping stones in bad positions, playing out of turn, or dropping stones when the game has ended.)
|
| |
Definition |
| | | Class: | ConnectFour | | Method: | judge | | Parameters: | String[] | | Returns: | String | | Method signature: | String judge(String[] board) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Connect Four on a 6x7 board has been solved independently by Victor Allis and James D. Allen. The first player can force a win with perfect play. |
| |
Constraints |
| - | board will contain exactly 6 elements. |
| - | Each element of board will have exactly 7 characters. |
| - | Each character will be one of the 3 possible characters: '.', 'X', or 'O'. |
| |
Examples |
| 0) | |
| | {
".......",
".......",
".......",
".......",
".......",
"......."
} |
| Returns: "first player moves" | | Every game starts with an empty board where the first player may drop a stone ('X') in one of the seven columns. |
|
|
| 1) | |
| | {
".......",
".......",
".......",
"...X...",
"...O...",
"...X..."
} |
| Returns: "second player moves" | | After three turns, the second player should make a move again. |
|
|
| 2) | |
| | {
".......",
".......",
"X......",
"OX.....",
"XOXO...",
"OXOX..."
} |
| Returns: "first player wins" | | The first player wins by connecting four stones in a diagonal line. There are many valid moving sequences that may lead to this end configuration. |
|
|
| 3) | |
| | {
".......",
".......",
".X.....",
".X.....",
".X..XX.",
"XOOOOOO"
} |
| Returns: "second player wins" | | The second player concludes the game by connecting a long line at the bottom. |
|
|
| 4) | |
| | {
"OOXOXOX",
"XXXOXOO",
"OXXOOXO",
"XOOXXOO",
"XXXOOXX",
"XOOXXOO"
} |
| Returns: "draw game" | | The board is full, and neither player has managed to connect at least four stones in a line. The game therefore ends in a tie. |
|
|
| 5) | |
| | {
"...X...",
".......",
".......",
".......",
"...X...",
"...O..."
} |
| Returns: "invalid" | | No "floating" stone is allowed in a valid game, so there would never be an empty square beneath any stone. |
|
|
| 6) | |
| | {
".......",
".......",
".......",
".......",
"OOOO...",
"XXXX..."
} |
| Returns: "invalid" | | The game ends when the first player wins. Neither player should continue thereafter. |
|
|
| 7) | |
| | {
"XXO.XOX",
"OOX.OXX",
"XXO.XXO",
"OOXXOOO",
"XXOOXOO",
"OOXOOXX"
} |
| Returns: "invalid" | | At a glance the first player seems to have won the game when in fact there does not exist a valid sequence of moves. |
|
|