CODEWITHSUNDEEP
javaalgorithm
Javasaurusrex
Javasaurusrex

Reputation: 123

Detecting diagonal in a row win - tic-tac-toe, gomoku

Within a game on Gomoku a player has to get 5 in a row to win. Detecting diagonal win is a problem.

I have tried the code below which searches a 2d matrix from top right until it finds a player token we are looking for e.g. 1, it then proceeds to search from that point diagonally to find a winning row. This works fine providing the first '1' the algorithm comes across is a part of the winning line. If it is not, and just a random piece, the algorithm returns false as it does not continue searching.

How would Itake the last played move of the game and only search the diagonals relating to that move? Or possibly edit provided code to search the whole board.

public boolean is_diagonal_win_left(int player) {
    int i = 0;
    for (int col = board_size-1; col > (win_length - 2); col--) {
        for (int row = 0; row < board_size-(win_length-1); row++) {
            while (board_matrix[row][col] == player) {
                i++;
                row++;
                col--;
                if (i == win_length) return true;
            }
            i = 0;
        }
    }
    return false;
}

//solved

public boolean is_diagonal_win_right(int player, int r, int c) {

        int count = 0;
        int row = r;
        int col = c;

        while ((row != 0) && (col != 0)) {
            row--;
            col--;
        }

        while ((row <= board_size - 1) && (col <= board_size - 1)) {
            if (board_matrix[row][col] == player) count++;
            row++;
            col++;
        }

        return count == win_length;
    }

Upvotes: 1

Views: 544

Answers (1)

Prune
Prune

Reputation: 77900

You are correct: searching the board for the first counter is invalid; searching the entire board is a waste of time. Start at the most recent move. Let's call that position (r, c); the player's token is still player. Check in each of the eight functional directions to see how long is the string of player. For instance, you check the NW-SE diagonal like this:

count = 1     // We just placed one counter
row = r-1; col = c-1
while ( (row >= 0) and (col >= 0) and 
        (board_matrix[row][col] == player) )
    count += 1

row = r+1; col = c+1
while ( (row < board_size) and (col < board_size) and 
        (board_matrix[row][col] == player) )
    count += 1

// Note: gomoku rules require exactly 5 in a row;
//   if you're playing with a"at least 5", then adjust this to >=
if (count == win_length) {
    // Process the win
}

Upvotes: 2

Related Questions