HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Java Connect Four "Four in a row" detection algorithms

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
connectfourjavaalgorithmsdetectionrow

Problem

I am making a connect four type game for my end of the year project in my programming class. I am about to start building off of the console based version I have made and add a GUI, but I feel sort of if-y about the win algorithms and am wondering if I could improve them. The code for those is below:

```
public void checkWins(int player) {
int count = 0;

vertical: for(int y = 0; y=4) {
System.out.println("Player "+player+" won!");
win = true;
break vertical;
}
} else {
count = 0;
}
}
}

count = 0;

horizontal: for(int x = 0; x=4) {
System.out.println("Player "+player+" won!");
win = true;
break horizontal;
}
} else {
count = 0;
}
}
}

count = 0;

int y = height-1;
int x;
diagonalDownRightA: for(int loop = 0; y>=0; loop++) {

//System.out.println("diagonalDownRightA test "+loop);
x = 0;
int otherY = y;

while(x=4) {
System.out.println("Player "+player+" won!");
win = true;
break diagonalDownRightA;
}
} else {
count = 0;
}
x++;
otherY++;
y = height-1; // fixes skipping rows bug
}
y-=loop;
// start at (0,height-1)
// go up one row, x++ y++ until reached (width-1||height-1)
// go up one row, add one to x and y until reached a point of no return
// repeat above until reached the top
// when done checking for diagonals starting at (0,0)
// go to the next collumn add one to x and y until reached a point of no return
// go to the next collumn add one to x and y until reached a point of no return
// same thing until done

Solution

Usablity

An issue I see with this algorithm is that it isn't easily transferable to a GUI application. It has System.out.println() embedded in it, and the return type is void, so the output has been restricted to console-only. To improve this algorithm's usefulness, change the return type to that of a player (int), and then change the parameter to be the board and make it a static method, or remove the parameter and keep it as an instance method. This will alter how the method is called and used. Instead of having to call checkWin for each player, you can do it once and have the method tell you who has won (if anyone).

Performance

Nested loops are expensive (however necessary since this is a 2D array), but having 6 of them is overkill. On top of that, the method would probably have to be executed one time for each player, and when it finds four-in-a-row it still continues to look through the rest of the loops. An easier solution is to loop once, and check all around each element. Assuming the loops move along the board bottom to top & left to right, you would only need to check each position for a win by looking up, up+right, up+left, and right.

A Better Solution

I happen to have made this algorithm once before in a programming contest. It won an award for most creative solution, so hopefully it's credible. I've adapted it for "Connect-4", but originally it was for a "Connect-2".

public static int checkWin(int[][] board) {
    final int HEIGHT = board.length;
    final int WIDTH = board[0].length;
    final int EMPTY_SLOT = 0;
    for (int r = 0; r = 0 &&
                    player == board[r+1][c-1] && // look up & left
                    player == board[r+2][c-2] &&
                    player == board[r+3][c-3])
                    return player;
            }
        }
    }
    return EMPTY_SLOT; // no winner found
}

Code Snippets

public static int checkWin(int[][] board) {
    final int HEIGHT = board.length;
    final int WIDTH = board[0].length;
    final int EMPTY_SLOT = 0;
    for (int r = 0; r < HEIGHT; r++) { // iterate rows, bottom to top
        for (int c = 0; c < WIDTH; c++) { // iterate columns, left to right
            int player = board[r][c];
            if (player == EMPTY_SLOT)
                continue; // don't check empty slots

            if (c + 3 < WIDTH &&
                player == board[r][c+1] && // look right
                player == board[r][c+2] &&
                player == board[r][c+3])
                return player;
            if (r + 3 < HEIGHT) {
                if (player == board[r+1][c] && // look up
                    player == board[r+2][c] &&
                    player == board[r+3][c])
                    return player;
                if (c + 3 < WIDTH &&
                    player == board[r+1][c+1] && // look up & right
                    player == board[r+2][c+2] &&
                    player == board[r+3][c+3])
                    return player;
                if (c - 3 >= 0 &&
                    player == board[r+1][c-1] && // look up & left
                    player == board[r+2][c-2] &&
                    player == board[r+3][c-3])
                    return player;
            }
        }
    }
    return EMPTY_SLOT; // no winner found
}

Context

StackExchange Code Review Q#127091, answer score: 6

Revisions (0)

No revisions yet.