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

• 05-26-2005
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.
• 05-26-2005
WaltP
Do the same with rows and columns. For diags you add to both index values. If either is outside your bounds, stop.
• 06-02-2005
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.
• 06-02-2005
quzah
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.
• 06-03-2005
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; }```
• 06-04-2005
Salem
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.
• 06-04-2005
Jez
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.
• 06-04-2005
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; }```
• 06-04-2005
quzah
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.
• 06-05-2005
Salem
> 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.
• 06-05-2005
Jez
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.
• 06-06-2005
```counter = 0; line = i;   column = move; while((column >= 0) && (board[line][column] == player)) {         counter++;         column--;         if(counter == 5)                 return 1; }```