Recursive Four in a Line

This week I had scheduled some tasks regarding my programming subject at the university. This time, we had to recode the so famous “Four in a Line”, implementing the called “linear structures” in Java, which I still don’t fully understand why they were needed at all, since we had to use simple auxiliary arrays to check on the results of the overall game.

I am not going to discuss here whether those structures and extra classes were needed, as I assume they were only trying to make us use them in a more didactical way. Or something. However, I found interesting how to detect if someone had a Four in a Line in a recursive way. Although it was not exactly asked to use recursive algorithms, I thought it would be great to implement something I learnt this year and I found to be useless at first.

After designing the UI, which came as a simple task as I had previously coded a table-based Swing interface in Java, I set out the problem for detecting a winner in paper.

It pretty much meant that, solving whether someone had “Four in a Line” or not, was all about checking possible diagonals which contained tiles of a very same player.

Those four diagonals can be expressed as the increment or decrement of an X and Y position at the same time.

The recursive method which will be called for every possible diagonal would then contain these following arguments:

private static boolean is4inALine(int x, int y, int sx, int sy, int n, int turn)

int x, y: the X and Y the algorithm will be looking at in the auxiliary array containing how the game board is arranged.

int sx, sy: The modular increment of X and Y which will remain constant per diagonal to advance recursively.

int n: the number of positions we have already checked.

int turn: the player number we started checking, constant too.

Finally, designing the base case and taking into account some out of bounds odds when it comes to checking inexistent positions in array, I came up with this method:

At first we might think we had four possible cases, but they can be simplified into two diagonals if we apply this method to every tile on board.