# The game of Othello solution

This project and the subsequent one will ask you to implement a game called Othello. Othello (also known as Reversi) is a well-known two-player strategy game. The game is played on a rectangular board divided into a grid — usually 8x8, though the size of the grid can vary. Players alternately place discs on the game board; one player's discs are black and the other player's are white. When discs are placed on the game board, other discs already on the board are flipped (i.e., a black disc becomes a white disc or vice versa). The game concludes when every square on the grid contains a disc, or when neither player is able to make a legal move; the winning player is generally the one who has more discs on the board at the end of the game, though there are alternate ways to determine a winner. The rules of the game, along with some notion of strategy, are described in the Wikipedia entry on Reversi. If you haven't played Othello before, or have seen it previously but don't remember how it works, you should at least read the sections of the Wikipedia entry that cover the rules of the game; knowing how the game is played before proceeding with this project is vital. If you want to try playing the game, a web-based version of it is available.
Your program begins by printing a line of output specifying which of the two sets of Othello rules are supported by your program, by printing either FULL or SIMPLE. (See the section titled Simplified Othello rules below for a description of the simplified set of rules, which you can implement for partial credit if you're unable to complete the full rules.)
Your program then reads five lines of input, specifying the options that will be used to determine how the game will be played.
The first line specifies the number of rows on the board, which will be an even integer between 4 and 16 (inclusive).
The second line specifies the number of columns on the board, which will be an even integer between 4 and 16 (inclusive) and does not have to be the same as the number of rows.
The third line specifies which of the players will move first: B for black, W for white.
The fourth line specifies the arrangement of the cells on the board when the game starts. According to the rules, the game begins with four discs on the board: two white and two black, arranged on the four center cells of the grid, with the two white discs separated diagonally and the two black discs separated diagonally. This line selects which color disc will be in the top-left position of these four center cells: B for black, W for white.
The fifth line selects how the game is won: means that the player with the most discs on the board at the end of the game wins, < means the player with the fewest.
After specifying the options, the game begins, proceeding one move a time until it's complete.
Before each turn, the following information is printed to the console:
The character B, followed by a colon and a space, followed by the number of discs on the board that are black. This is followed by two spaces, the character W, a colon and a space, and the number of discs on the board that are white.
The contents of the board, with each row occupying one line of output, and one space separating each pair of cells. Each cell is written either as a B (if a black tile occupies that cell), a W (if a white tile occupies that cell), or a . (if no tile occupies that cell). For example: . . . . . . . . . . . . . . . . . . . . . . . . . . . B W . . . . . . W B . . . . . . . . . . . . . . . . . . . . . . . . . . .
The word TURN (in all-caps), followed by a colon and a space, followed by B if it's the black player's turn, W if it's white's turn.
After printing the information above, the program reads a line of input specifying the current player's move. The move is specified as two integers on a line, separated by a space. The first integer specifies the row number (with 1 being the top row, 2 being the row below that, and so on) and the second integer specifies the column number (with 1 being the leftmost column, 2 being the one to the right of that, and so on).
If the move is valid, print the word VALID alone on a line, apply that move (i.e., make the appropriate changes to the state of the game) and then continue the game..
If the move is invalid (see the rules if you're curious what makes a move invalid), print the word INVALID alone on a line and wait for the user to specify another move.
At the conclusion of the game (i.e., after the last move is made and there are no more legal moves on the board), the final state of the game is printed to the console, quite similarly to how it's printed before each turn:
The character B, followed by a colon and a space, followed by the number of discs on the board that are black. This is followed by two spaces, the character W, a colon and a space, and the number of discs on the board that are white.
The contents of the board, in the same format described above.
The word WINNER (in all-caps), followed by a colon and a space, followed by B if the black player has won, W if the white player has won, and NONE if no player has won (i.e., the final score is tied).
The program ends when the game is over. A complete example of program execution The following is an example of the program's execution, if implemented as it should be, including the full Othello rules. Boldfaced, italicized text indicates input, while normal text indicates output. FULL 4 4 B B B: 2 W: 2 . . . . . B W . . W B . . . . . TURN: B 2 4 VALID B: 4 W: 1 . . . . . B B B . W B . . . . . TURN: W 1 2 VALID B: 3 W: 3 . W . . . W B B . W B . . . . . TURN: B 1 4 INVALID 1 1 VALID B: 5 W: 2 B W . . . B B B . W B . . . . . TURN: W 1 4 VALID B: 4 W: 4 B W . W . B W B . W B . . . . . TURN: B 1 3 VALID B: 7 W: 2 B B B W . B B B . W B . . . . . TURN: W 3 4 VALID B: 5 W: 5 B B B W . B B W . W W W . . . . TURN: B 4 2 VALID B: 7 W: 4 B B B W . B B W . B W W . B . . TURN: W 2 1 VALID B: 5 W: 7 B B B W W W W W . B W W . B . . TURN: B 4 4 VALID B: 8 W: 5 B B B W W B W W . B B W . B . B TURN: W 4 1 VALID B: 7 W: 7 B B B W W B W W . W B W W B . B TURN: B 3 1 VALID B: 10 W: 5 B B B W B B W W B B B W W B . B TURN: W 4 3 VALID B: 8 W: 8 B B B W B B W W B B W W W W W B WINNER: NONE A couple of "gotchas" to be aware of in the game logic For the most part, Othello games proceed with players moving alternately, and continue until all cells on the grid contain a disc. However, there are a couple of wrinkles that you'll need to be sure you handle:
Sometimes, a player will make a move and, as a result, the opposite player will have no valid moves available (i.e., there is no cell in the grid in which the opposite player can move afterward). In that case, the turn reverts back to the player who just moved, and that player moves again.
Occasionally, neither player will have a valid move on the board, even though there are still empty cells in the grid. (One example is when all of the discs on the board belong to one player, though there are others, as well.) In this case, the game immediately ends and the winner is determined based on the number of discs each player has on the board.
Simplified Othello rules Implementing Othello can be a challenge, so we're providing you with the option of implementing a simplified set of Othello rules instead of the full rules described in the Wikipedia entry on Reversi. Implementing the simplified rules will leave you ineligible for full credit on the project, by capping your Correctness and robustness score at 12 points out of a possible 20, but a finished version of the simplified rules will almost certainly score higher than an incomplete version of the full rules, since we'll at least be able to test it successfully. Note, too, that your score on Project #5 will not be affected; either set of rules is allowed on that project, with no penalty for the simplified version, since the focus of that project is building a graphical user interface atop your existing game logic from this one. The simplified Othello rules are as follows:
The same configuration options need to be specified in the same order (i.e., number of rows and columns, who moves first, how the tiles are arranged at the start of the game, and whether more or fewer tiles wins the game) and they have the same meanings as in the full rules.
A player can make a valid move anywhere on the board that is adjacent to a tile (i.e., one cell away in any of the eight directions) occupied by a tile belonging to the other player.
When a player makes a move, any adjacent cell on the board (i.e., one cell away in any of the eight directions from where the move was made) containing a tile of the opponent's color is flipped.
The game ends when neither player can make a legal move — when the board is completely filled with tiles, or when no open cells on the board are legal for either player.
The format of the input and output are also identical to what's described in the section titled A detailed look at how your program should behave above; the only difference is the first line of the output (SIMPLEinstead of FULL) and the logic for determining whether a move is legal and which tiles are flipped. Be aware that you do have to specify the first line of the output correctly, so we'll know which tests to run against your program. You can implement either the full Othello rules or the simplified ones, and you'll need to begin by outputting either FULL or SIMPLE so we'll know which one you've chosen, and make sure that your first line of output matches what you actually intended to submit.