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.
This is a discussion on Help with algorithm to check if there's a winner in the Connect 4 game within the C Programming forums, part of the General Programming Boards category; It's easy to check the lines and the columns but I am having a hard time with the diagonals? The ...
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.
Definition: Politics -- Latin, from
poly meaning many and
tics meaning blood sucking parasites
-- Tom Smothers
This is what I have so far:
Code:#define N 6 /* lines */ #define M 7 /* columns */ int matrix[N][M];Can you show me what you mean please? Thanks.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; }
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.
Hope is the first step on the road to disappointment.
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; }
Now create two more functionsCode: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; }
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I support http://www.ukip.org/ as the first necessary step to a free Europe.
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.
You might be able to miss this function, just use the position of the last counter placed during an actual game.2. A function "B" to call function "A" for all possible start positions on the board.
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.
Hope is the first step on the road to disappointment.
> 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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I support http://www.ukip.org/ as the first necessary step to a free Europe.
Good point. I guess it's been a while since I played connect 4.Except you can place a piece in the middle of a row of 4, and still generate a winning line.
Take a look at this piece of code please:
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.Code:counter = 0; line = i; column = move; while((column >= 0) && (board[line][column] == player)) { counter++; column--; if(counter == 5) return 1; }
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.
Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling