Lab 7: Reversi Game Board Configuration and Move Legality Checking

This is the first part of a series of two labs (Lab 7 and Lab 8) that will complete an implementation for a board-type game called Reversi (also called Othello). The goal of this lab is to write code that sets up the input and checks the legality of moves in this game. These two labs make use of two-dimensional arrays, as well as all of the previous material covered before two-dimensional arrays in this course. They require some careful thinking about how to convert human-thinking into working software. Please read through this lab handout carefully.

It is due March 15, 2025 at 11:59 PM.

---

Grades

This lab is worth 13 marks, as follows:

• 6 marks for the public test cases.
• 4 marks for the hidden private test cases.
• 3 marks for in-person lab marking.

You can always see your public test cases automarker grades here APS105 after every submission. They are out of 6.

The in-person lab marking is worth 3 marks, and will be marked by a TA in-person. You should go to your assigned lab section, your assigned TA and sit on your assigned workstation. You will find this information on Quercus under Lab Subsection. You must sit in your assigned seat for the TA to grade you. Otherwise, they will mistakenly think you are absent and give you a 0. The in-lab grading is due March 21, 2025 March 28, 2025 in your practical session. Your assigned TA will ask you questions about your code, and will look at your code to ensure the coding style is neat. For this lab, the coding style involves if you are having at least 3 functions in your program, indenting your code properly, if you are using proper variable names, if you are using proper comments, and if you are using proper spacing.

Instructions

1. Go to your GitHub repo from lab 0 by following this link: https://github.com/compeng-gg/2025-winter-aps105-<UTORID>, where you'll have to replace <UTORID> with your UTORid.

2. Open the same codespace you created for lab0. You should not create any other codespaces. Fig.1 Existing codespace created in your GitHub repository

3. In the terminal, type in the following command to transfer (pull) lab 7 material into your codespace:

   pull

   This will do a "pull" (which gets files from the "student" repository, containing starter code). This helper command will make sure you commit all your changes before you can start Lab 7. You should always commit (and push) your changes!

4. You should see a folder called lab7 in your repository.

   Important! If you're using the Codespace to save the lecture notes, you'll get "You must commit all your changes (check git status)". To resolve this, you may use the following command instead:

   git pull upstream main

   If you get the following error, please press on Ctrl+X for Mac and Windows.

   Fig.2 Merge pull message

   note

   If you are using the Codespace please ignore these steps. For students NOT using the Codespace, first do:

   git remote add upstream git@github.com:compeng-gg/2025-winter-aps105-student.git

   You only need to do this once, then after you'll use:

   git pull

   This command gets the starter code for the lab.

Objective

The goal of this lab is to write a program that will be used (in Lab 8) as part of a Reversi game, as well as a little bit of the "thinking" code that will be used in that lab to have the computer play against a human opponent.

Here is a brief description of the full Reversi game. You may also play the game online here to familiarize yourself with the game rules. Reversi is played on a board (like a chess board or a checkers board) that has dimensions $n \times n$, where $n$ is even. In the picture below $n = 4$. The game uses tiles that are white on one side, and black on the other side (they can be "flipped" over to change their color). One player plays white; the other player plays black. The picture below shows the initial board configuration, which has two white and two black tiles placed in advance at the centre. Observe that rows and columns are labelled with letters.

Fig.3 Starting positions on the Reversi game board.

A "turn" consists of a player laying a tile of his/her own color on a candidate empty board position, subject to the following two rules:

1. There must be a continuous straight line of tile(s) of the opponent's color in at least one of the eight directions from the candidate empty position (North, South, East, West, and diagonals).

2. In the position immediately following the continuous straight line mentioned in #1 above, a tile of the player's color must already be placed.

After playing a tile at a position that meets the above criteria, all of the lines of the opponent's tiles that meet the criteria above are flipped to the player's color.

In the picture below, all of the candidate positions for White's next move are shown shaded.

Fig.4 All of the candidate positions for White's next move.

If the White piece decides to play at row $c$, column $a$, the Black piece at row $c$, column $b$ is flipped and the board looks like this:

Fig.5 White plays at row $c$, column $a$.

The picture below shows the possible move positions for the Black player:

Fig.6 All of the candidate positions for Black's next move after White plays at $(c, a)$.

If the Black player lays a tile at $(b, a)$, the board appears like this:

Fig.7 Black plays at $(b, a)$.

Finally, if the White player lays a tile at $(a, c)$ the board appears like this:

Fig.8 White responds to Black by playing at $(a, c)$.

Note that in White's move, two lines of Black tiles were flipped: the line directly to the South, and the line to the South West.

The turns alternate between the players, unless one player has no available move, in which case the only player with an available move is allowed to continue to make moves until a move becomes available for the opponent. At this point, the opponent is allowed to take a turn and the alternating turns between the players resumes. The game ends when either: 1) the entire board is full, or 2) neither player has an available move.

For this lab, you will implement part of the game-playing functionality. You will complete the game in Lab 8, using the functionality you have built in this lab, so please be mindful to build clean and re-usable code for this lab.

You will write a C program that will do the following: (Note that the specific details of input and output will be given in the example runs below this section.)

1. The first input to the program will be $n$, giving the size of the $n \times n$ board. You may assume that $n$ will be an even number and will never be larger than 26, and should declare a static 2-dimensional array. There is no need to allocate memory dynamically or to declare variable-length arrays. Your program should initialize the board as shown above and print it.

2. The next sequence of inputs will describe a board configuration, representing a situation part-way through a game of Reversi. Each line of input will consist of three characters with no spaces in between. The first character will be a color: B or W; the second character will be the row (a through z) location; the third character will be the column (a through z) location. The three characters represent a tile of the specified color placed at the specified row and column. The three-character sequence !!! ends the board configuration entry phase. Character arithmetic can be used to translate the rows/columns into array indices, e.g. 'b' - 'a' equals 1. Note: your program should not check for move legality during this phase. This phase is simply to input an intermediate board configuration.

3. Then, your program should print a list of the available moves for the White player, followed by a list of the available moves for the Black player, given the board configuration input in the previous step. The available moves for each player should be printed in the order of increasing rows, then in the order of increasing columns (for available moves in the same row).

4. Next, your program should ask the user to input a move, represented in the same three-character format. Your program should check if the move is valid, and if so, make the move, flipping the tiles correspondingly. If the move is invalid, your program should indicate so.

5. Your program should print the final board configuration and terminate.

Your program must use the following characters to represent the state of each board position:

U - for unoccupied
B - occupied by black
W - occupied by white

For example, after the entire board above in Fig.8 is entered, it would be printed as follows:

  abcd
a UUWU
b BWWU
c WWWU
d UUUU

To print the board, your program should contain a function with the following prototype:

void printBoard(char board[][26], int n);

where board is the 2D array representing the current board state, and n is the board dimensions.

Sample Output

Here is an example execution of the program:

Enter the board dimension: 4
  abcd
a UUUU
b UWBU
c UBWU
d UUUU
Enter board configuration:
Bba
Wca
Bac
!!!
  abcd
a UUBU
b BWBU
c WBWU
d UUUU
Available moves for W:
aa
bd
db
Available moves for B:
ab
cd
da
dc
Enter a move:
Wdb
Valid move.
  abcd
a UUBU
b BWBU
c WWWU
d UWUU

Here is another example execution of the program where the final move is invalid:

Enter the board dimension: 6
  abcdef
a UUUUUU
b UUUUUU
c UUWBUU
d UUBWUU
e UUUUUU
f UUUUUU
Enter board configuration:
Bbd
Bad
Wde
Wcb
!!!
  abcdef
a UUUBUU
b UUUBUU
c UWWBUU
d UUBWWU
e UUUUUU
f UUUUUU
Available moves for W:
ae
bc
ce
db
ec
ed
Available moves for B:
ba
bc
ca
db
df
ed
ef
Enter a move:
Bbe
Invalid move.
  abcdef
a UUUBUU
b UUUBUU
c UWWBUU
d UUBWWU
e UUUUUU
f UUUUUU

We strongly encourage you to break up your program into separate functions, and to carefully test each function separately, before connecting it into the larger program. To help with this, you are required to create the following helper functions and use them in your implementation:

1. void printBoard(char board[][26], int n);

which prints the game board according to our example output.

2. bool positionInBounds(int n, int row, int col);

which checks whether the specified (row, col) lies within the board dimensions.

It is very error prone to write separate code to check each of the eight possible line directions that begin at a given tile. To simplify this, you are required to write and use the following function:

3. bool checkLegalInDirection(char board[][26], int n, int row, int col, char color, int deltaRow, int deltaCol);

which checks whether (row, col) is a legal position for a tile of color by "looking" in the direction specified by deltaRow and deltaCol. deltaRow and deltaCol take on values of -1, 0, and 1, with the restriction that they cannot both be 0. For example, if deltaRow = 1 and deltaCol = 0, the function searches the South line. If deltaRow = -1 and deltaCol = 1, the function searches the Northeast line. The idea is that, elsewhere in your program, you will call the helper function 8 times to search the lines in the 8 possible directions.

---

Testing and Submission

1. Under lab7 directory, you will see two files under starter-code: lab7.c and reversi.h. Please copy them into lab7 directory. Your directory should look as follows.

   Fig.9 Lab 7 Directory.

2. Edit your code in lab7.c and implement the functions in reversi.h the prototypes of which are written in lab7.c, compile it, and run it to produce the output shown above. You can use the handy buttons shown below.
   

   Fig.10 Handy buttons to compile, run, and debug your C program.

   You also compile and run your program using the terminal, similarly to the previous assignments.

3. Once you have the correct output, go to the terminal and test your program against the test cases by typing the following commands:

cd /workspace/lab7

test

4. If your program passes the test cases, you can submit your code by typing the following commands.

git add lab7.c

git commit -m "Lab 7"

git push

5. If your program does not work, and you want to test the test cases manually, the inputs are under the workspace/lab7/tests/public/inputs directory.

---