Four in a row logic

algorithm, c

Solution

Best bet is to probably divide the search space into four:

- vertical;

- horizontal;

- right and down;

- right and up.

then limit your starting and ending coordinates based on the direction.

For example, let's say your array is `board[row=0-5][col=0-6]` with `board[0][0]` at the top left.

First vertical (loops are inclusive at both ends in this pseudo-code):

for row = 0 to 2:
    for col = 0 to 6:
        if board[row][col] != 0 and
           board[row][col] == board[row+1][col] and
           board[row][col] == board[row+2][col] and
           board[row][col] == board[row+3][col]:
               return board[row][col]

This limits the possibilities to only those that don't extend off the edge of the board, a problem most solutions have when they simplistically start by checking each cell and going out in all directions from there. By that, I mean there's no point checking a start row of 3, simply because that would involve rows 3, 4, 5 and 6 (the latter which does not exist).

Similarly, for horizontal:

for row = 0 to 5:
    for col = 0 to 3:
        if board[row][col] != 0 and
           board[row][col] == board[row][col+1] and
           board[row][col] == board[row][col+2] and
           board[row][col] == board[row][col+3]:
               return board[row][col]

For right and down, followed by right and up:

for row = 0 to 2:
    for col = 0 to 3:
        if board[row][col] != 0 and
           board[row][col] == board[row+1][col+1] and
           board[row][col] == board[row+2][col+2] and
           board[row][col] == board[row+3][col+3]:
               return board[row][col]

for row = 3 to 5:
    for col = 0 to 3:
        if board[row][col] != 0 and
           board[row][col] == board[row-1][col+1] and
           board[row][col] == board[row-2][col+2] and
           board[row][col] == board[row-3][col+3]:
               return board[row][col]

Now, you could actually combine those two by making `for col = 0 to 3` the outer loop and only doing it once rather than twice but I actually prefer to keep them separate (with suitable comments) so that it's easier to understand. However, if you're addicted to performance, you can try:

for col = 0 to 3:
    for row = 0 to 2:
        if board[row][col] != 0 and
           board[row][col] == board[row+1][col+1] and
           board[row][col] == board[row+2][col+2] and
           board[row][col] == board[row+3][col+3]:
               return board[row][col]
    for row = 3 to 5:
        if board[row][col] != 0 and
           board[row][col] == board[row-1][col+1] and
           board[row][col] == board[row-2][col+2] and
           board[row][col] == board[row-3][col+3]:
               return board[row][col]

Then, if no wins were found in the four possible directions, simply return `0` instead of the winner `1` or `2`.

So, for example, your sample board:

row
 0   [0, 0, 0, 0, 0, 0, 0]
 1   [0, 0, 0, 0, 0, 0, 0]
 2   [0, 0, 0, 1, 1, 0, 0]
 3   [0, 0, 0, 1, 1, 0, 0]
 4   [0, 0, 1, 2, 2, 2, 0]
 5 > [0, 1, 2, 2, 1, 2, 0]
         ^
      0  1  2  3  4  5  6 <- col

would detect a winner in the right and up loop where the starting cell was `{5,1}` because `{5,1}`, `{4,2}`, `{3,3}` and `{2,4}` are all set to `1`.

Problem

I'm currently working on a basic four in a row game for myself, but I'm rather stuck at the logic behind it. Currently I have this multi-dimensional array that represents the board ``` [ [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0] ] ``` `0` would represent an empty slot, while `1` and `2` represent a player. So let's say after a while you get this array: ``` [ [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 1, 1, 0, 0], [0, 0, 1, 2, 2, 2, 0], [0, 1, 2, 2, 1, 2, 0] ] ``` How can I write the logic to check if there are four in a row? Calculating it for horizontal and vertical ones seem rather easy (although still figuring out the best way), but how would I do this for diagonal lines?

Original source