Connect 4 - Part 2

2. Part: The Logic

Ok, here we go with Part 2. For now, forget everything you did in Part 1, you won't need it for this part. Well, some of the ideas you had in Part 1 might still be helpful. So, don't forget EVERYTHING. And no, I did not say that you should erase your source code of part 1...

The goal of Part 2 is to implement the class Connect4Logic. This module has two main functions:

1. keep track of the state of the game and

2. determine if there is a winner, and if so, who is the winner.

The logic module needs to keep track of all discs that have been inserted by the players up to a certain point. This is necessary so it can eventually determine the winner.

Keeping track of the state of the game

In order to keep track of all discs that have been inserted already, we have to find an appropriate data model. In real life it is the stand-up board that helps us remember where the inserted discs end up. With this help our brain is then able to constantly scan for "winning sequences" of four equally-colored discs. However, the board is only a convenience. You can also play this game without a board, for example by drawing a chart on a piece of paper and then painting in colored circles (or just drawing circles and crosses, which is typically done when playing tic-tac-toe). Taking this a step further, you could even play Connect Four without any utensils. You can just announce your column choice to your opponent and then you both remember the current disc setting. I'm pretty sure that this is the way how MENSA members play it: "Seven", "Three", "Six", "Oh man, I lose again?!"

So, how should we represent the board in our logic module? We basically need a matrix with the appropriate number of rows and columns. This matrix could contain integer values which indicate whether a disc has been placed in a certain location and, if so, which player the disc belongs to. Having two players, the matrix entries would be 0 (no disc), 1 (disc of player 1) or 2 (disc of player 2). (What would be the values at the beginning of a game?)

A very efficient data structure for representing a matrix in Java is a 2-dimensional array. Such a 2-dimensional array is very similar to our standard array, only that it offers two index dimensions.

Following statement declares a 2-dimensional integer array with name matrix:

int [] [] matrix;

The appropriate command to create the array would be:

matrix = new int[row][col];

where row and col are integer values specifying the number of desired rows and columns of this matrix.

In order to put for example a value 7 into the second row and third column you would use

matrix[1][2] = 7;

1. Task

If you haven't created class Connect4Logic, yet, it is now time to do so. After creating the class, we need to set up the disc matrix appropriately.

• Think about whether the matrix should be a field or not.

• Declare the matrix at an appropriate place within the class. It's best to make it a 2-dimensional array.

• Write a default constructor, which initializes the number of rows to 6 and the number of columns to 7.

• The constructor should also create and initialize the matrix array.

• Write another constructor, which takes two parameters specifying the number of rows and columns. Again, the constructor should create and initialize the matrix array.

2. Task

Now we need to add a method that let's us insert a disc into a column. This method determines the appropriate row and makes a note in the disc matrix. The header of this method should be exactly as follows:

public void insertDisc(int column, int player)

where column is the column (enumerated from left to right, starting with 1) in which the disc should be placed. Furthermore, player specifies one of two players (either 1 or 2). At this point, we don't care about disc colors. We are not concerned with the display at all!

3. Task

Having created the insertDisc() method, we would like to test it out. However, we have one big problem here. Although we insert a few discs, we don't see anything! It's not like in Part 1 where we added a disc and had the confirmation (in form of a colored circle) right away on the screen. Now, it's only an entry in a matrix, which is stored somewhere deep down in a computer's memory.

How can we visualize this matrix? Well, one way to do it is to use BlueJ's "Inspect" functionality. We can inspect the matrix and see its current setting. Do this! Create an object of type Connect4Logic and insert a few discs. Then, inspect the object and look for the matrix entries. Do you find the numbers in there? You should! But this is tedious, very tedious!

Therefore, create a helper method public void printMatrix(), which prints the contents of the matrix to the terminal window. It should print the matrix contents row by row, with one row per line. This way we can nicely visualize the matrix contents whenever we want to check it.

Later on, at the end of the project, we just declare this method as "private". This way it won't show up in the documentation and no one will be able to call it. For now, though, you want to leave it as "public" so you can call it from the BlueJ workbench.

Determining the winner

At this point you should be able to insert discs into the matrix, keep track of the discs, and visualize the matrix for testing purposes. This means your logic module is now able to keep track of the state of the game and the next step is to determine when we have a winner.

This functionality can be implemented in many different ways. The steps that we outline below point out one possible solution. It's one approach that we think is easily understandable. However, we don't claim that it is the best way to implement this logic module, nor do we even know whether it's really so easily understandable. But this is what programming is often about. It's all about choices. Since there is typically no "right" way, you just have to make a decision and then follow through with it. At the end, you often find out that there might have been a better (faster, more efficient, more elegant, or whatever) way. Well, if you have enough time, you throw away your source code and do it again. This time, being more experienced and knowing better what the outcome should be.

For now let us just try to create a working solution, without worrying too much about the elegance of the code. What we want to have at the end of this step is a method that determines whether a certain player has a winning sequence. Specifically, you should have a method like this:

public boolean checkForWinner(int player)

This method takes as a parameter the number of the player and returns true if this player has a winning sequence of discs. If not, it returns false.

The following steps are only a suggestion. If you want to come up with your own solution, that's perfectly fine with me. As long as the checkForWinner() method is working!

4. Task

The questions to ask here are, what is a "winning sequence" for a certain player and how can it be determined? While the first question is quite easy to answer, the second question appears to be rather tricky. We need an algorithm that can find any sequence of four discs with the same color inside our matrix.

To make it easier, let's consider following different types of "winning sequences" and treat them independently:

• horizontal sequence

• vertical sequence

• diagonal sequence upwards (i.e., row number increases from left to right)

• diagonal sequence downwards (i.e., row number decreases from left to right)

Let's first only look at a horizontal sequence. To do this we can write a helper method, e.g., checkHorizontal(int p), which takes as a parameter the number of the player and returns whether this player has a horizontal winning sequence.

Inside this method we could apply following search strategy:

1. start at the lower left corner (row 1, column 1)

2. check whether this disc and the three discs to the right of it all belong to player p;

3. if they belong to player p return true, otherwise goto 3.

4. if we are not at the top of the matrix, yet, increase the row number and goto step 2, otherwise goto 4.

5. if there are more columns to check, set the row number back to 1 and increment the column number,

6. otherwise return false (because we didn't find any winning sequence and there are no further possibilities)

If you draw a little picture, you should be able to understand this search algorithm. It's really not difficulty! The only tricky part is to make sure that you don't get OutOfBounds exceptions. To avoid these, you need to think about how far you have to go to the right so your check still looks at valid columns...

Once you have the horizonal check working, write a method for the vertical sequence check. It is very similar! The same is true for both of the diagonal sequence checks. Write a method for each of them and always make sure that the four checks that you do in order to detect a sequence are in valid index ranges for the matrix array. Please, see me if you have problems with these methods.

5. Task

After you have writting the individual check methods, it should be quite easy to finish up thecheckForWinner() method. All that this method now needs to do is call the individual check methods one after the other and return true if one of them returns true. If all the individual checks are false,checkForWinner() also returns false.

Milestone for 2. Part

You should now have a working Connect4Logic class. You should be able to deal with boards of various sizes and you should be able to insert a disc into a certain column calling the appropriate method. The interface of your class Connect4Logic should look exactly like this. You can check this in BlueJ by selecting the "Interface" view from the drop down menu on the top right corner (by default it shows "Implementation").

Note that the Interface Documentation doesn't show any helper methods that were written. In order to hide your helper methods, which are only used inside your class and should never be called by another object from outside the class, you can declare them as "private" instead of "public".

Deliverables:

• Submit the file Connect4Logic.java which contains your Connect4Logic class.

• Only one version per team needs to be submitted.

MOVE ON TO PART 3