Help with algorithm to check if there's a winner in the Connect 4 game

It's easy to check the lines and the columns but I am having a hard time with the diagonals? The board size varies so I can't have any buried numbers. Do you guys have any suggestions? Thanks.

Do the same with rows and columns. For diags you add to both index values. If either is outside your bounds, stop.

This is what I have so far:

Code:

---

#define N  6 /* lines */
#define M  7 /* columns */

int matrix[N][M];

---

Code:

---

int check_win(int matrix[][M], int play)
{
        int i;
        int j;
        int counter;

        /* horizontally */
        for(i = 0, counter = 0; i < N; i++) {
                for(j = 0; j < M; j++) {
                        if(matrix[i][j] == matrix[i][j + 1])
                                counter++;

                        if(counter == 4)
                                return 1;
                }
        }

        /* vertically */
        for(i = 0, counter = 0; i < M; i++) {
                for(j = 0; j < N; j++) {
                        if(matrix[j][i] == matrix[j + 1][i])
                                counter++;

                        if(counter == 4)
                                return 1;
                }
        }

        return 0;
}

---

Can you show me what you mean please? Thanks.

Start at a square. Move diagonally by incrementing or decrementing the needed variables one at a time to check for a match. If you don't find a match, stop counting. Repeat until done. There's nothing to show (aside from writing the whole thing for you).

Seriously, work it out on paper how you'd check for a win yourself in a linear method.

Quzah.

After trying on my own for a lot of time, I was able to come up with this. It works *sometimes*, my head really hurts and I am going crazy over this. Can someone tell me what I am doing wrong? Thank you.

Code:

---

/* N is the number of lines amd M the number of columns */

int check_win(int matrix[][M], int play)
{
        int i;
        int j;
        int counter;
        char player;

        for(i = 0; i < N; i++) {
                if(matrix[i][play] != '.')

                        player = matrix[i][play];
        }

        for(j = 0; j < M - 3; j++) {
                for(i = 0; i < N - 3; i++) {
                        counter = 1;

                        while((counter < 4) && matrix[i + counter][j + counter] == player)
                                counter++;

                        if(counter == 4)
                                return 1;
                }
        }

        for(j = 0; j < M - 3; j++) {
                for(i = 3; i < N; i++) {
                        counter = 1;

                        while((counter < 4) && matrix[i - counter][j + counter] == player)
                                counter++;

                        if(counter == 4)
                                return 1;
                }
        }

        counter = 1;
        for(i = 0; i < N; i++) {
                for(j = 0; j < M; j++) {
                        if(matrix[i][j] == player && matrix[i][j + 1] == player)
                                counter++;

                        else
                                continue;

                        if(counter == 4)
                                return 1;
                }
        }

        counter = 1;
        for(i = 0; i < M; i++) {
                for(j = 0; j < N; j++) {
                        if(matrix[j][i] == player && matrix[j + 1][i] == player)
                                counter++;

                        else
                                continue;

                        if(counter == 4)
                                return 1;
                }
        }

        return 0;
}

---

Code:

---

int isValidCoord ( int x, int y ) {
  return x >= 0 && x < M && y >= 0 && y < M;
}

int checkWinningLine ( int matrix[][M], int play, int x, int y, int dx, int dy ) {
  int count = 0;
  int ix, iy;
  for ( ix = x, iy = y ; count < 4 && isValidCoord(ix,iy) ; ix += dx, iy += dy ) {
    if ( matrix[iy][ix] != play ) break;
  }
  return count == 4;
}

---

Now create two more functions

1. A function "A" to call checkWinningLine() for a given xy position, varying dx and dy to scan in 8 different directions.
2. A function "B" to call function "A" for all possible start positions on the board.

I was going to suggest breaking up your code into more functions, but couldn't be bothered to think about how. Very nice of Salem to show the way.

Quote:

---

2. A function "B" to call function "A" for all possible start positions on the board.

---

You might be able to miss this function, just use the position of the last counter placed during an actual game.

Salem, I thank you for trying to help. The problem is that I have to use some predefined functions and nothing more. I am almost done now. My program detects horizontal and vertical wins perfectly but I am still having problems with the diagonals. I'll post the whole thing so anyone willing to help can have a better idea of what is going on. Thanks a lot.

Code:

---

#include <stdio.h>

#define N 6
#define M 7

void write_board(int board[N][M]);
int is_full(int board[N][M]);
int get_move(int player);
int valid_move(int board[N][M], int column);
void make_move(int board[N][M], int player, int column);
int win(int board[][M], int move);

int main(void)
{
        int i;
        int j;
        int move;
        int player;
        int winner = 0;
        int board[N][M];


        for(i = 0; i < N; i++) {
                for(j = 0; j < M; j++)
                        board[i][j] = '.';
        }

        do {
                player = 1;
            write_board(board);

                do {
                        move = get_move(player);
                }while(valid_move(board, move) == 0);

                move -= 1;
               
                make_move(board, player, move);
               
                if(win(board, move) == 1) {
                        winner = 1;
                        printf("\n");
                        write_board(board);
                        break;
                }

                printf("\n");

                player = 2;
                write_board(board);

                do {
                        move = get_move(player);
                }while(valid_move(board, move) == 0);
               
                move -= 1;

                make_move(board, player, move);
               
                if(win(board, move) == 1) {
                        winner = 2;
                        printf("\n");
                        write_board(board);
                        break;
                }

                printf("\n");

        }while(is_full(board) == 0);

        if(winner == 1)
                printf("\nEnd! 1\n");

        else if(winner == 2)
                printf("\nEnd! 2\n");

        else
                printf("\nDraw!\n");

        return 0;
}

void write_board(int board[][M])
{
        int i;
        int j;

        for(i = 0; i < M; i++)
                printf("%d ", i + 1);

        printf("\n");
        for(i = 0; i < N; i++) {
                for(j = 0; j < M; j++)
                        printf("%c ", board[i][j]);
                printf("\n");
        }
}

int is_full(int board[N][M])
{
        int i;
        int j;

        for(i = 0; i < N; i++) {
                for(j = 0; j < M; j++)
                        if(board[i][j] == '.')
                                return 0;
        }

        return 1;
}

int get_move(int player)
{
        int column;

        printf("%d> ", player);
        scanf("%d", &column);

        return column;
}

int valid_move(int board[N][M], int column)
{
        int i;
        int ocupado = 0;

        if(column > M) {

                printf("\nInvalid move\n");
                return 0;
        }

        for(i = 0; i < N; i++) {
                if(board[i][column - 1] != '.')
                        ocupado++;
        }

        if(ocupado == N) {
                printf("\nJogada inv%clida\n", 160);
                return 0;
        }

        else
                return 1;
}

void make_move(int board[N][M], int player, int column)
{
        int i;
        char ch;

        if(player == 1)
                ch = 'O';
        else
                ch = 'X';

        for(i = N; i >= 0; i--) {
                if(board[i][column] == '.') {
                        board[i][column] = ch;
                        break;
                }
        }
}

int win(int board[][M], int move)
{
        int i;
        int line;
        int column;
        int counter;
        char player = '\0';

        for(i = 0; i < N; i++) {
                if(board[i][move] != '.') {
                        player = board[i][move];
                        break;
                }
        }

        counter = 0;
        line = i;
 
        column = move;
        while((counter < 5) && (board[line][column] == player)) {
                counter++;
                column--;

                if(counter == 5)
                        return 1;
        }

        column = move;
        while((counter < 5) && (board[line][column] == player)) {
                counter++;
                column++;

                if(counter == 5)
                        return 1;
        }

        counter = 0;
        column = move;

        while((counter < 5) && (board[line][column] == player)) {
                counter++;
                line--;

                if(counter == 5)
                        return 1;
        }

        line = i;

        while((counter < 5) && (board[line][column] == player)) {
                counter++;
                line++;

                if(counter == 5)
                        return 1;
        }

        counter = 0;

        line = i;
        column = move;

        while((counter < 4) && (board[line][column] == player)) {
                counter++;
                line++;
                column--;

                if(counter == 4)
                        return 1;
        }

        line = i;
        column = move;

        while((counter < 5) && (board[line][column] == player)) {
                counter++;
                line--;
                column++;

                if(counter == 5)
                        return 1;
        }

        counter = 0;

        line = i;
        column = move;

        while((counter < 4) && (board[line][column] == player)) {
                counter++;
                line++;
                column++;

                if(counter == 4)
                        return 1;
        }

        line = i;
        column = move;

        while((counter == 5) && (board[line][column] == player)) {
                counter++;
                line--;
                column--;

                if(counter == 5)
                        return 1;
        }

        return 0;
}

---

To move diagonally from upper left to lower right, increment both X and Y, where X is the column, and Y is the row. (Typically these are reversed when you're looping through an entire grid. The outer loop being Y.)

To move diagonally from lower left to upper right, decrement Y and increment X.
To move diagonally from lower right to upper left, decrement both Y and X.
To move diagonally from upper right to lower left, decrement X and increment Y.

It's not hard. You just have to stop and think it out. Didn't you ever learn anything about plotting coordinates in [insert some somewhat basic math course here]?

Quzah.

> just use the position of the last counter placed during an actual game.
Except you can place a piece in the middle of a row of 4, and still generate a winning line.

> The problem is that I have to use some predefined functions and nothing more.
Well if you don't say up front "I have to use these bizarre function names and other weird tutor imposed rules", what can you expect?
Just unroll my code into your already massively long "win" function and let your ill-informed tutor sort it out.

Quote:

---

Except you can place a piece in the middle of a row of 4, and still generate a winning line.

---

Good point. I guess it's been a while since I played connect 4.

Take a look at this piece of code please:

Code:

---

counter = 0;
line = i;
 
column = move;
while((column >= 0) && (board[line][column] == player)) {
        counter++;
        column--;

        if(counter == 5)
                return 1;
}

---

This will test a line going to the left. Did you guys notice that inside the while loop I am comparing variable counter with number 5? But hey, this is a connect FOUR game so wasn't I supposed to exit the loop when counter equals 4? Well, if I do that, my game gives a win to whoever have three pieces in a row. I don't understand why that is happening. Can someone enlighten me? Thanks.

Take a look at the code for the connect four contest a while ago. It has been tested thoroughly.

If you perform the check every round, you only have to check around the last placed marker.