Connect 4 check for winning algorithm

Question

I know that there are many questions regarding checking connection 4 for victory. The problem is that most other algorithms make my program execute runtime errors because they try to access an index outside of my array. My algorithm is as follows:

private int checkWin(int[][] gridTable,int rowNum,int colNum, int maxRow, int maxCol) { // For checking whether any win or lose condition is reached. Returns 1 if win or lose is reached. else returns 0 // gridTable[][] is the game matrix(can be any number of rows and columns between 4 and 40) // colNum is the column number where the last token was placed // rowNum is the row number where the last token was placed // maxRow is the number of rows in my grid // maxCol is the number of columns in my grid int player = gridTable[rowNum][colNum]; //player ID int count=0; // Horizontal check for (int i=0;i<maxCol;i++) { if (gridTable[rowNum][i]==player) count++; else count=0; if (count>=4) return 1; } //Vertical check for (int i=0;i<maxRow;i++) { if (gridTable[i][colNum]==player) count++; else count=0; if (count>=4) return 1; } count=0; // 4 in a row diagonally for(int i=colNum+1,j=rowNum+1;i<maxRow && j<maxCol;i++,j++) { if(gridTable[j][i]!=player) { count=1; break; } count++; } // 4 in a row diagonally for(int i=colNum-1,j=rowNum-1;i>=0 && j>=0;i--,j--) { if(gridTable[j][i]!=player) { count=1; break; } count++; } // 4 in a row diagonally for(int i=colNum+1,j=rowNum-1;i<maxRow && j>=0;i++,j--) { if(gridTable[j][i]!=player) { count=1; break; } count++; } for(int i=colNum-1,j=rowNum+1;i>=0 && j<maxCol;i--,j++) { // 4 in a row diagonally if(gridTable[j][i]!=player) { count=1; break; } count++; } if(count>=4) return 1; return 0; } 

count is a variable that checks winnings if an account is equal to or greater than 4 means that they must be 4 or more consecutive tokens of the same player.

PROBLEM: sometimes the method checks the winnings without having 4 tokens in order, and in other cases it does not check the winnings when 4 tokens are in order.

Answer 1

It looks like your code is correct for horizontal and vertical cases. The hard part is the diagonal case.

Try image:

For green lines, the position of the initial position is 0 ... maxRow - 4. The column will be 0 ... StartingRow -

pseudo code:

 // 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; rowStart++){ 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 can do something similar for diagonals going the other way (from bottom left to top right).

Answer 2

For some reason, I don’t really like 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; } 

Answer 3

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

Instead, the basic verification algorithm is always the same process, regardless of which direction you are checking.

You need the starting point (x / y) and x / y delta (direction of travel). You can summarize this in one 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 allow you to check in four directions, as well as make them back

So, if we used 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"); 

What are the exits ...

 Vertical Win Win Lose Horizontal Win Win Lose Diag Win Win Lose 

Now you can just sum it up 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"); 

What prints something like ...

 Vertical Win Win Horizontal Win Win Diag Win Win 

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

The goal was not to provide a “complete, out of the box” solution, but a concept from which a broader solution could be developed (I mean, I would not want people to really think;)). I also developed a solution based on the idea that the OP will know where the last part was placed, i.e. Starting point;)

didWin modifying the didWin method so easily, you can check the grid n by n from anywhere ...

 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 make it work. Sometimes the answer is not a complete solution, but is the seed of an idea that takes someone to a new place;)

I would further increase the number of expected merged fragments, but I'm sure there is an improvement that I really don't need to show;)

Answer 4

this is what worked for me, it also did not enter as long as it seems:
These are methods with row, column, diagonal, and anti-diagonal for x and o;

 public static void checkVertO(){ if (board[0][0] == 'O' && board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O' || board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O' && board[4][0] == 'O' || board[2][0] == 'O' && board[3][0] == 'O' && board[4][0] == 'O' && board[5][0] == 'O' || board[0][1] == 'O' && board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O' || board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O' && board[4][1] == 'O' || board[2][1] == 'O' && board[3][1] == 'O' && board[4][1] == 'O' && board[5][1] == 'O' || board[0][2] == 'O' && board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O' || board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O' && board[4][2] == 'O' || board[2][2] == 'O' && board[3][2] == 'O' && board[4][2] == 'O' && board[5][2] == 'O' || board[0][3] == 'O' && board[1][3] == 'O' && board[2][3] == 'O' && board[3][3] == 'O' || board[1][3] == 'O' && board[2][3] == 'O' && board[3][3] == 'O' && board[4][3] == 'O' || board[2][3] == 'O' && board[3][3] == 'O' && board[4][3] == 'O' && board[5][3] == 'O' || board[0][4] == 'O' && board[1][4] == 'O' && board[2][4] == 'O' && board[3][4] == 'O' || board[1][4] == 'O' && board[2][4] == 'O' && board[3][4] == 'O' && board[4][4] == 'O' || board[2][4] == 'O' && board[3][4] == 'O' && board[4][4] == 'O' && board[5][4] == 'O' || board[0][5] == 'O' && board[1][5] == 'O' && board[2][5] == 'O' && board[3][5] == 'O' || board[1][5] == 'O' && board[2][5] == 'O' && board[3][5] == 'O' && board[4][5] == 'O' || board[2][5] == 'O' && board[3][5] == 'O' && board[4][5] == 'O' && board[5][5] == 'O' || board[0][6] == 'O' && board[1][6] == 'O' && board[2][6] == 'O' && board[3][6] == 'O' || board[1][6] == 'O' && board[2][6] == 'O' && board[3][6] == 'O' && board[4][6] == 'O'|| board[2][6] == 'O' && board[3][6] == 'O' && board[4][6] == 'O' && board[5][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkHorzO(){ if (board[0][0] == 'O' && board[0][1] == 'O' && board[0][2] == 'O' && board[0][3] == 'O' || board[0][1] == 'O' && board[0][2] == 'O' && board[0][3] == 'O' && board[0][4] == 'O' || board[0][2] == 'O' && board[0][3] == 'O' && board[0][4] == 'O' && board[0][5] == 'O' || board[0][3] == 'O' && board[0][4] == 'O' && board[0][5] == 'O' && board[0][6] == 'O' || board[1][0] == 'O' && board[1][1] == 'O' && board[1][2] == 'O' && board[1][3] == 'O' || board[1][1] == 'O' && board[1][2] == 'O' && board[1][3] == 'O' && board[1][4] == 'O' || board[1][2] == 'O' && board[1][3] == 'O' && board[1][4] == 'O' && board[1][5] == 'O' || board[1][3] == 'O' && board[1][4] == 'O' && board[1][5] == 'O' && board[1][6] == 'O' || board[2][0] == 'O' && board[2][1] == 'O' && board[2][2] == 'O' && board[2][3] == 'O' || board[2][1] == 'O' && board[2][2] == 'O' && board[2][3] == 'O' && board[2][4] == 'O' || board[2][2] == 'O' && board[2][3] == 'O' && board[2][4] == 'O' && board[2][5] == 'O' || board[2][3] == 'O' && board[2][4] == 'O' && board[2][5] == 'O' && board[2][6] == 'O' || board[3][0] == 'O' && board[3][1] == 'O' && board[3][2] == 'O' && board[3][3] == 'O' || board[3][1] == 'O' && board[3][2] == 'O' && board[3][3] == 'O' && board[3][4] == 'O' || board[3][2] == 'O' && board[3][3] == 'O' && board[3][4] == 'O' && board[3][5] == 'O' || board[3][3] == 'O' && board[3][4] == 'O' && board[3][5] == 'O' && board[3][6] == 'O' || board[4][0] == 'O' && board[4][1] == 'O' && board[4][2] == 'O' && board[4][3] == 'O' || board[4][1] == 'O' && board[4][2] == 'O' && board[4][3] == 'O' && board[4][4] == 'O' || board[4][2] == 'O' && board[4][3] == 'O' && board[4][4] == 'O' && board[4][5] == 'O' || board[4][3] == 'O' && board[4][4] == 'O' && board[4][5] == 'O' && board[4][6] == 'O' || board[5][0] == 'O' && board[5][1] == 'O' && board[5][2] == 'O' && board[5][3] == 'O' || board[5][1] == 'O' && board[5][2] == 'O' && board[5][3] == 'O' && board[5][4] == 'O' || board[5][2] == 'O' && board[5][3] == 'O' && board[5][4] == 'O' && board[5][5] == 'O' || board[5][3] == 'O' && board[5][4] == 'O' && board[5][5] == 'O' && board[5][6] == 'O' ){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkHorzX(){ if (board[0][0] == 'X' && board[0][1] == 'X' && board[0][2] == 'X' && board[0][3] == 'X' || board[0][1] == 'X' && board[0][2] == 'X' && board[0][3] == 'X' && board[0][4] == 'X' || board[0][2] == 'X' && board[0][3] == 'X' && board[0][4] == 'X' && board[0][5] == 'X' || board[0][3] == 'X' && board[0][4] == 'X' && board[0][5] == 'X' && board[0][6] == 'X' || board[1][0] == 'X' && board[1][1] == 'X' && board[1][2] == 'X' && board[1][3] == 'X' || board[1][1] == 'X' && board[1][2] == 'X' && board[1][3] == 'X' && board[1][4] == 'X' || board[1][2] == 'X' && board[1][3] == 'X' && board[1][4] == 'X' && board[1][5] == 'X' || board[1][3] == 'X' && board[1][4] == 'X' && board[1][5] == 'X' && board[1][6] == 'X' || board[2][0] == 'X' && board[2][3] == 'X' && board[2][4] == 'X' && board[2][5] == 'X' || board[2][3] == 'X' && board[2][4] == 'X' && board[2][5] == 'X' && board[2][6] == 'X' || board[3][0] == 'X' && board[3][1] == 'X' && board[3][2] == 'X' && board[3][3] == 'X' || board[3][1] == 'X' && board[3][2] == 'X' && board[3][3] == 'X' && board[3][4] == 'X' || board[3][2] == 'X' && board[3][3] == 'X' && board[3][4] == 'X' && board[3][5] == 'X' || board[3][3] == 'X' && board[3][4] == 'X' && board[3][5] == 'X' && board[3][6] == 'X' || board[4][0] == 'X' && board[4][3] == 'X' && board[4][4] == 'X' && board[4][5] == 'X' || board[4][3] == 'X' && board[4][4] == 'X' && board[4][5] == 'X' && board[4][6] == 'X' || board[5][0] == 'X' && board[5][1] == 'X' && board[5][2] == 'X' && board[5][3] == 'X' || board[5][1] == 'X' && board[5][2] == 'X' && board[5][3] == 'X' && board[5][4] == 'X' || board[5][2] == 'X' && board[5][3] == 'X' && board[5][4] == 'X' && board[5][5] == 'X' || board[5][3] == 'X' && board[5][4] == 'X' && board[5][5] == 'X' && board[5][6] == 'X' ){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkDiagX(){ if (board[2][0] == 'X' && board[3][1] == 'X' && board[4][2] == 'X' && board[5][3] == 'X'|| board[1][0] == 'X' && board[2][1] == 'X' && board[3][2] == 'X' && board[4][3] == 'X'|| board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X' && board[3][3] == 'X'|| board[0][1] == 'X' && board[1][2] == 'X' && board[2][3] == 'X' && board[3][4] == 'X'|| board[1][1] == 'X' && board[2][2] == 'X' && board[3][3] == 'X' && board[4][4] == 'X'|| board[2][1] == 'X' && board[3][2] == 'X' && board[4][3] == 'X' && board[5][4] == 'X'|| board[0][2] == 'X' && board[1][3] == 'X' && board[2][4] == 'X' && board[3][5] == 'X'|| board[1][2] == 'X' && board[2][3] == 'X' && board[3][4] == 'X' && board[4][5] == 'X'|| board[2][2] == 'X' && board[3][3] == 'X' && board[4][4] == 'X' && board[5][5] == 'X'|| board[0][3] == 'X' && board[1][4] == 'X' && board[2][5] == 'X' && board[3][6] == 'X'|| board[1][3] == 'X' && board[2][4] == 'X' && board[3][5] == 'X' && board[4][6] == 'X'|| board[2][3] == 'X' && board[3][4] == 'X' && board[4][5] == 'X' && board[5][6] == 'X'){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkDiagO(){ if (board[2][0] == 'O' && board[3][1] == 'O' && board[4][2] == 'O' && board[5][3] == 'O'|| board[1][0] == 'O' && board[2][1] == 'O' && board[3][2] == 'O' && board[4][3] == 'O'|| board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O' && board[3][3] == 'O'|| board[0][1] == 'O' && board[1][2] == 'O' && board[2][3] == 'O' && board[3][4] == 'O'|| board[1][1] == 'O' && board[2][2] == 'O' && board[3][3] == 'O' && board[4][4] == 'O'|| board[2][1] == 'O' && board[3][2] == 'O' && board[4][3] == 'O' && board[5][4] == 'O'|| board[0][2] == 'O' && board[1][3] == 'O' && board[2][4] == 'O' && board[3][5] == 'O'|| board[1][2] == 'O' && board[2][3] == 'O' && board[3][4] == 'O' && board[4][5] == 'O'|| board[2][2] == 'O' && board[3][3] == 'O' && board[4][4] == 'O' && board[5][5] == 'O'|| board[0][3] == 'O' && board[1][4] == 'O' && board[2][5] == 'O' && board[3][6] == 'O'|| board[1][3] == 'O' && board[2][4] == 'O' && board[3][5] == 'O' && board[4][6] == 'O'|| board[2][3] == 'O' && board[3][4] == 'O' && board[4][5] == 'O' && board[5][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkAntiDiagX(){ if (board[3][0] == 'X' && board[2][1] == 'X' && board[1][2] == 'X' && board[0][3] == 'X'|| board[4][0] == 'X' && board[3][1] == 'X' && board[2][2] == 'X' && board[1][3] == 'X'|| board[3][1] == 'X' && board[2][2] == 'X' && board[1][3] == 'X' && board[0][4] == 'X'|| board[5][0] == 'X' && board[4][1] == 'X' && board[3][2] == 'X' && board[2][3] == 'X'|| board[4][1] == 'X' && board[3][2] == 'X' && board[2][3] == 'X' && board[1][4] == 'X'|| board[3][2] == 'X' && board[2][2] == 'X' && board[1][4] == 'X' && board[0][5] == 'X'|| board[5][1] == 'X' && board[4][2] == 'X' && board[3][3] == 'X' && board[2][4] == 'X'|| board[4][2] == 'X' && board[3][3] == 'X' && board[2][4] == 'X' && board[1][5] == 'X'|| board[3][3] == 'X' && board[2][4] == 'X' && board[1][5] == 'X' && board[0][6] == 'X'|| board[5][2] == 'X' && board[4][3] == 'X' && board[3][4] == 'X' && board[2][5] == 'X'|| board[4][3] == 'X' && board[3][4] == 'X' && board[2][5] == 'X' && board[1][6] == 'X'|| board[5][3] == 'X' && board[4][4] == 'X' && board[3][5] == 'X' && board[2][6] == 'X'){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkAntiDiagO(){ if (board[3][0] == 'O' && board[2][1] == 'O' && board[1][2] == 'O' && board[0][3] == 'O'|| board[4][0] == 'O' && board[3][1] == 'O' && board[2][2] == 'O' && board[1][3] == 'O'|| board[3][1] == 'O' && board[2][2] == 'O' && board[1][3] == 'O' && board[0][4] == 'O'|| board[5][0] == 'O' && board[4][1] == 'O' && board[3][2] == 'O' && board[2][3] == 'O'|| board[4][1] == 'O' && board[3][2] == 'O' && board[2][3] == 'O' && board[1][4] == 'O'|| board[3][2] == 'O' && board[2][2] == 'O' && board[1][4] == 'O' && board[0][5] == 'O'|| board[5][1] == 'O' && board[4][2] == 'O' && board[3][3] == 'O' && board[2][4] == 'O'|| board[4][2] == 'O' && board[3][3] == 'O' && board[2][4] == 'O' && board[1][5] == 'O'|| board[3][3] == 'O' && board[2][4] == 'O' && board[1][5] == 'O' && board[0][6] == 'O'|| board[5][2] == 'O' && board[4][3] == 'O' && board[3][4] == 'O' && board[2][5] == 'O'|| board[4][3] == 'O' && board[3][4] == 'O' && board[2][5] == 'O' && board[1][6] == 'O'|| board[5][3] == 'O' && board[4][4] == 'O' && board[3][5] == 'O' && board[2][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } }