Java Connect Four "Four in a row" detection algorithms

Question

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<height; y++) { //System.out.println("Vertical test "+y+" of "+height+"-1"); for(int x=0; x<width; x++) { if(board[x][y] == player) { count++; if(count>=4) { System.out.println("Player "+player+" won!"); win = true; break vertical; } } else { count = 0; } } } count = 0; horizontal: for(int x = 0; x<width; x++) { //System.out.println("Horizontal test "+x+" of "+width+"-1"); for(int y = 0; y<height; y++) { if(board[x][y] == player) { count++; // If there is a break in this code, count will be reset if(count>=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<=width-1 && otherY<=height-1) { // Go diagonally right downwards //System.out.println("dDRA testing at "+x+","+otherY); if (board[x][otherY] == player) { count++; //System.out.println("Found a result, count++"); if(count>=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 } count = 0; x = width-1; diagonalDownRightB: for(int loop = 0; x>=0; loop++) { //System.out.println("diagonalDownRightB test "+loop); y = 0; int otherX = x; // =x while(y<=height-1 && otherX<=width-1) { // Go diagonally right downwards for other half of the board //System.out.println("dDRB testing at "+otherX+","+y); if (board[otherX][y] == player) { count++; if(count>=4) { System.out.println("Player "+player+" won!"); win = true; break diagonalDownRightB; } } else { count = 0; } y++; otherX++; x = width-1; } x-=loop; } y = height-1; diagonalDownLeftA: for(int loop = 0; y>=0; loop++) { //System.out.println("diagonalDownLeftA test "+loop); x = width-1; int otherY = y; while(x>=0 && otherY<=height-1) { //System.out.println("dDLA testing at "+x+","+otherY); if (board[x][otherY] == player) { count++; //System.out.println("Found a result, count++"); if(count>=4) { System.out.println("Player "+player+" won!"); win = true; break diagonalDownLeftA; } } else { count = 0; } x--; otherY++; y = height-1; // fixes skipping rows bug } y-=loop; } count = 0; x = width-1; diagonalDownLeftB: for(int loop = 0; x>=0; loop++) { //System.out.println("diagonalDownLeftB test "+loop); y = 0; int otherX = x; while(y<=height-1 && otherX>=0) { //System.out.println("dDLB testing at "+otherX+","+y); if (board[otherX][y] == player) { count++; if(count>=4) { System.out.println("Player "+player+" won!"); win = true; break diagonalDownLeftB; } } else { count = 0; } y++; otherX--; x = width-1; } x-=loop; } } } 

Answer 1

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 < 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 }