Connect 4 check for a win algorithm
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;
}
Looks like your code is correct for the horizontal and vertical cases. The tricky part is the diagonal case.
Let's try a picture:
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).
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 ;)
I did my own version in the C language and I think that it's quite easy to reinterpret in another language.
//Return values: 1 for Player 1, 2 for Player 2 and 0 for a tie.
// '-' represents an empty tile, 'X' Player 1, 'O' Player 2
#include <stddef.h>
int connect4(char *game[], size_t columns, size_t lines)
{
int winner = -1;
for (size_t l = 0; l < lines; l++)
{
for (size_t c = 0; c < columns; c++)
{
char player = game[l][c];
if (player == '-')
continue;
if (c + 3 < columns && player == game[l][c + 1]
&& player == game[l][c + 2] && player == game[l][c + 3])
winner = winner < 0 ? player : 0;
if (l + 3 < lines && player == game[l + 1][c]
&& player == game[l + 2][c] && player == game[l + 3][c])
winner = winner < 0 ? player : 0;
if (c + 3 < columns && l + 3 < lines && player == game[l + 1][c + 1]
&& player == game[l + 2][c + 2] && player == game[l + 3][c + 3])
winner = winner < 0 ? player : 0;
if (c >= 3 && l + 3 < lines && player == game[l + 1][c - 1]
&& player == game[l + 2][c - 2] && player == game[l + 3][c - 3])
winner = winner < 0 ? player : 0;
}
}
if (winner < 1)
return 0;
else
return winner == 88 ? 1 : 2;
}