Connect 4 check for a win algorithm

So, having dug through your code, it would seem that the diagonal check can only win in a single direction (what happens if I add a token to the lowest row and lowest column?)

Instead, the basic check algorithm is always the same process, regardless of which direction you're checking in.

You need a start point (x/y) and x/y delta (direction of movement). You can summarise this down into a single method...

public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) {

    boolean win = true;
    for (int count = 0; count < 4; count++) {
        if (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) {
            int test = grid[row][col];
            if (test != check) {
                win = false;
                break;
            }
        }
        row += rowDelta;
        col += colDelta;
    }
    return win;

}

This will basically allow you to check in four directions, but also do them backwards

So, if we were to use something like...

int[][] gridTable = new int[ROWS][COLUMNS];

gridTable[ROWS - 1][3] = 1;
gridTable[ROWS - 2][3] = 1;
gridTable[ROWS - 3][3] = 1;
gridTable[ROWS - 4][3] = 1;

System.out.println("Vertical");

System.out.println(didWin(gridTable, 1, ROWS - 4, 3, 1, 0) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, ROWS - 1, 3, -1, 0) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 0, 3, 1, 0) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];
gridTable[3][1] = 1;
gridTable[3][2] = 1;
gridTable[3][3] = 1;
gridTable[3][4] = 1;

System.out.println("");
System.out.println("Horizontal");
System.out.println(didWin(gridTable, 1, 3, 1, 0, 1) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 3, 4, 0, -1) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 3, 0, 0, 1) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];
gridTable[0][1] = 1;
gridTable[1][2] = 1;
gridTable[2][3] = 1;
gridTable[3][4] = 1;

System.out.println("");
System.out.println("Diag");
System.out.println(didWin(gridTable, 1, 0, 1, 1, 1) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 3, 4, -1, -1) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 1, 2, 1, 1) ? "Win" : "Lose");

Which outputs...

Vertical
Win
Win
Lose

Horizontal
Win
Win
Lose

Diag
Win
Win
Lose

Now, you could just summarise it down to...

public boolean didWin(int[][] grid, int check, int row, int col) {
    return didWin(grid, check, row, col, 1, 0) ||
                    didWin(grid, check, row, col, -1, 0) ||
                    didWin(grid, check, row, col, 0, 1) ||
                    didWin(grid, check, row, col, 0, -1) ||
                    didWin(grid, check, row, col, 1, 1) ||
                    didWin(grid, check, row, col, -1, -1) ||
                    didWin(grid, check, row, col, -1, 1) ||
                    didWin(grid, check, row, col, 1, -1);
}

So, using something like...

int[][] gridTable = new int[ROWS][COLUMNS];

gridTable[ROWS - 1][3] = 1;
gridTable[ROWS - 2][3] = 1;
gridTable[ROWS - 3][3] = 1;
gridTable[ROWS - 4][3] = 1;

System.out.println("Vertical");

System.out.println(didWin(gridTable, 1, ROWS - 1, 3) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, ROWS - 4, 3) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];
gridTable[3][1] = 1;
gridTable[3][2] = 1;
gridTable[3][3] = 1;
gridTable[3][4] = 1;

System.out.println("");
System.out.println("Horizontal");
System.out.println(didWin(gridTable, 1, 3, 1) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose");

gridTable = new int[ROWS][COLUMNS];
gridTable[0][1] = 1;
gridTable[1][2] = 1;
gridTable[2][3] = 1;
gridTable[3][4] = 1;

System.out.println("");
System.out.println("Diag");
System.out.println(didWin(gridTable, 1, 0, 1) ? "Win" : "Lose");
System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose");

Which prints out something like...

Vertical
Win
Win

Horizontal
Win
Win

Diag
Win
Win

I would add that this approach does only work if you provide the correct start of the 4 chips on a row. For example didWin(gridTable, 1, 3, 3) will provide false instead of true for your horizontal check, because the loop can only check one direction.

The intention wasn't to provide a "full fledged, out of the box" solution, but a concept from which a broader solution could be developed (I mean, I'd hate for people to actually have to think ;)). I also designed the solution based on the idea that the OP would know where the last piece was placed, ie, the starting point ;)

By modifying the didWin method ever so slightly, it's possible to check a n by n grid from any point...

public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) {
    boolean match = false;
    int matches = 0;
    while (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) {
        int test = grid[row][col];
        if (test != check && match) {
            break;
        } else if (test == check) {
            match = true;
            matches++;
        }
        row += rowDelta;
        col += colDelta;
    }
    return matches == 4;
}

So, I used...

public static final int ROWS = 8;
public static final int COLUMNS = 8;
//...
int[][] gridTable = new int[ROWS][COLUMNS];

gridTable[ROWS - 1][3] = 1;
gridTable[ROWS - 2][3] = 1;
gridTable[ROWS - 3][3] = 1;
gridTable[ROWS - 4][3] = 1;
for (int[] row : gridTable) {
    StringJoiner sj = new StringJoiner("|", "|", "|");
    for (int col : row) {
        sj.add(Integer.toString(col));
    }
    System.out.println(sj);
}
System.out.println(didWin(gridTable, 1, 3, 3));

and was able to get it to work. Sometimes an answer isn't a complete solution, but a seed for an idea which takes someone to a new place ;)

A further enhancement would include providing the number of expected conjoined pieces, but I'm pretty sure that's an enhancement I really don't need to demonstrate ;)


Looks like your code is correct for the horizontal and vertical cases. The tricky part is the diagonal case.

Let's try a picture:

red and green diagonal lines from left to right across the board

For the green lines, your starting row position is 0 ... maxRow - 4. The column would be 0 ... startingRow -

Pseudocode:

// top-left to bottom-right - green diagonals
for( rowStart = 0; rowStart < rowMax - 4; rowStart++){
    count = 0;
    int row, col;
    for( row = rowStart, col = 0; row < rowMax && col < colMax; row++, col++ ){
        if(gridTable[row][col] == player){
            count++;
            if(count >= 4) return 1;
        }
        else {
            count = 0;
        }
    }
}

// top-left to bottom-right - red diagonals
for( colStart = 1; colStart < colMax - 4; colStart++){
    count = 0;
    int row, col;
    for( row = 0, col = colStart; row < rowMax && col < colMax; row++, col++ ){
        if(gridTable[row][col] == player){
            count++;
            if(count >= 4) return 1;
        }
        else {
            count = 0;
        }
    }
}

You could do something similar for diagonals going the other way (from bottom-left to top-right).


For some reason I am not so fond of counters, so I did it this way (It works for boards with different sizes).

public boolean areFourConnected(int player){

    // horizontalCheck 
    for (int j = 0; j<getHeight()-3 ; j++ ){
        for (int i = 0; i<getWidth(); i++){
            if (this.board[i][j] == player && this.board[i][j+1] == player && this.board[i][j+2] == player && this.board[i][j+3] == player){
                return true;
            }           
        }
    }
    // verticalCheck
    for (int i = 0; i<getWidth()-3 ; i++ ){
        for (int j = 0; j<this.getHeight(); j++){
            if (this.board[i][j] == player && this.board[i+1][j] == player && this.board[i+2][j] == player && this.board[i+3][j] == player){
                return true;
            }           
        }
    }
    // ascendingDiagonalCheck 
    for (int i=3; i<getWidth(); i++){
        for (int j=0; j<getHeight()-3; j++){
            if (this.board[i][j] == player && this.board[i-1][j+1] == player && this.board[i-2][j+2] == player && this.board[i-3][j+3] == player)
                return true;
        }
    }
    // descendingDiagonalCheck
    for (int i=3; i<getWidth(); i++){
        for (int j=3; j<getHeight(); j++){
            if (this.board[i][j] == player && this.board[i-1][j-1] == player && this.board[i-2][j-2] == player && this.board[i-3][j-3] == player)
                return true;
        }
    }
    return false;
}