Connect 4 Check for a Win Algorithm

Connect 4 check for a win algorithm

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).

Connect 4, check for winner algorithm

No matter what, in order to check for victory condition, you'll need to do some sort of looping or recursion on the whole board. As long as your loop stops checking in any direction as soon as it stops being a winning condition (e.g. if you check left to right and after 2 iterations you find a different color) then it should be fine.

A way of optimizing this would be to only check for victory conditions when new moves are played, then you only need to check those around that move and not the whole board.
If you need to check a complete board and not turn-by-turn then a further step would be to keep a list of moves played and do your checking from the first move forward, then you can stop as soon as the winning move was played.

Python connect 4 check win function

You've just mixed up your dimensions, you should set them this way:

def checkOWin(board):
    boardHeight = len(board[0])
    boardWidth = len(board)

Because when you refer to board[x], that's counting the number of lists in the board, and when you refer to board[x][y] that's just referring to the length of one specific row in the board.

if board[x][y] == tile and board[x+1][y] == tile and board[x+2][y] == tile and board[x+3][y] == tile:

When I flipped those values the function ran without errors.

Checking Winner in connect 4 C++ Algorithm

The brute force approach is to test every cell to see if it's connected to connectedPiecesToWin pieces in any of the valid directions so first write a routine that will return true if the cell at 0,0 is a winning cell:

• pick an offset to search, say -1,-1 to search diagonally
• for that offset:
  
  
  • check to see if the cell at that offset from the target cell is the same colour.
  • if yes, increment a counter and perform the same test again
    at that offset from the offset cell (little bit of recursion here)
  • stop when you hit a wall or the number of same-colour cells is greater than or equal to connectedPiecesToWin. \edit
• pick the next offset (-1,0), (0,-1), (1,1), etc.
• if you search all eight directions and don't get a win return false.

That routine is then the key to either searching the whole board for a winning cell, or just checking whether the move just made has created a win.

Or am I missing something?

Connect 4: Check for winner

Checking for a winner in very much the same way as you do, only with a little less code.
I think you wouldn't need to check all fields to determine if the game is done. Just increase a counter when you drop a piece in the game. The game is a draw if the counter reaches 42 and there is no winner yet.

function CheckRow(x, y, xd, yd: Integer): Boolean;
var
  c: Integer;

  function RowLength(x, y, xd, yd: Integer): Integer;
  begin
    Result := 0;
    repeat
      Inc(Result);
      Inc(x, xd);
      Inc(y, yd);
    until not ((x in [1..7]) and (y in [1..6]) and (Board[x, y] = c));
  end;

begin
  c := Board[x, y];

  Result := 4 <= RowLength(x, y, xd, yd) + RowLength(x, y, xd*-1, yd*-1) - 1;
end;

function CheckForWinner(x, y: Integer): Integer;
begin
  Result := 0;
  if CheckRow(x, y, 0, 1) or CheckRow(x, y, 1, 1) or
     CheckRow(x, y, 1, 0) or CheckRow(x, y, 1, -1) then
    Result := Board[x,y];
end;

Diagonal win checks in Connect 4

For one you want to move down and right at the same time every time, you also only need to go to 3, 3 as a diagonal cannot occur any farther than that without it leaving the bounds of the array.

This should work for your top left to bottom rights if I'm right in assuming that your top left is your 0,0.
Doing top right to bottom left is a matter of changing the column and row loops and changing how the offset works.

// Top-Left -> Bottom-Right
for (int column = 0; column < 4; column++) {
    for (int row = 0; row < 4; row++) {
        player = 0;
        if (field[row][column] != 0){
            player=field[row][column];
            offset = 1;
        }
        while (player != 0){
            if (field[row + offset][column + offset] == player){
                offset += 1;
            }else{
                player = 0;
            }
        }                   
        if(offset >= 4){
            return field[row][column];
        }
    }
}

---

Related Topics