Problem

Connect 4 is a game where opponents take turns dropping red or black discs into a 7 x 6 vertically suspended grid. The game ends either when one player creates a line of four consecutive discs of their color (horizontally, vertically, or diagonally), or when there are no more spots left in the grid.

Design and implement Connect 4.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input:
Player 1 (Red, R): Drop disc in column 3
Player 2 (Black, B): Drop disc in column 4
Player 1 (Red, R): Drop disc in column 3
Player 2 (Black, B): Drop disc in column 4
Player 1 (Red, R): Drop disc in column 3
Player 2 (Black, B): Drop disc in column 4
Player 1 (Red, R): Drop disc in column 3

Output: 
Player 1 wins! (with 4 vertical consecutive discs in column 3)

Explanation:
Player 1 created a vertical line (column 3) with their discs.

Solution

Method 1 - Use the grid

Intuition

  1. Game Design:
    • This game requires a grid (array) capable of maintaining the state of disc positions.
    • The input consists of a chosen column, and the disc is dropped at the lowest available cell in the column.
    • The win condition is checked after every move for horizontal, vertical, and diagonal lines.
  2. Core Challenge:
    • Ensuring that discs “fall correctly” to the lowest empty row in a column.
    • Efficiently checking for winning conditions in the grid.

Approach

  1. Initial Setup:
    • Create a 7 x 6 grid initialised with - (empty spaces).
    • Players alternate turns, placing their assigned colour ( R or B ).
  2. Handling Moves:
    • Check if the chosen column is valid and not full. Drop the disc in the lowest available row within the column.
  3. Checking for Win:
    • After each move, check for horizontal, vertical, and diagonal lines formed by the last placed disc.
  4. Ending the Game:
    • Either player wins, the grid is full (draw), or invalid moves.
  5. Optimisation:
    • Iterate through limited cells around the last placed disc when checking for consecutive discs rather than traversing the full grid each time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

class Connect4 {

    private int rows = 6;
    private int cols = 7;
    private char[][] grid;
    private char currentPlayer;

    public Connect4() {
        grid = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = '-';
            }
        }
        currentPlayer = 'R'; // Red starts the game
    }

    public boolean dropDisc(int col) {
        if (col < 0 || col >= cols || grid[0][col] != '-') {
            return false; // Invalid move
        }

        for (int row = rows - 1; row >= 0; row--) {
            if (grid[row][col] == '-') {
                grid[row][col] = currentPlayer;
                return true;
            }
        }
        return false;
    }

    public boolean checkWin(int row, int col) {
        // Check horizontal, vertical, and diagonal lines
        int[][] directions = { { 0, 1 }, { 1, 0 }, { 1, 1 }, { 1, -1 } };
        for (int[] dir : directions) {
            int count =
                countConsecutive(row, col, dir[0], dir[1]) +
                countConsecutive(row, col, -dir[0], -dir[1]) -
                1;
            if (count >= 4) {
                return true;
            }
        }
        return false;
    }

    private int countConsecutive(int x, int y, int dx, int dy) {
        int count = 0;
        char piece = grid[x][y];
        while (
            x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == piece
        ) {
            count++;
            x += dx;
            y += dy;
        }
        return count;
    }

    public String play(int col) {
        if (!dropDisc(col)) {
            return "Invalid move. Try again.";
        }

        int row = 0;
        for (int r = 0; r < rows; r++) {
            if (grid[r][col] == currentPlayer) {
                row = r;
                break;
            }
        }

        if (checkWin(row, col)) {
            return "Player " + currentPlayer + " wins!";
        }

        currentPlayer = currentPlayer == 'R' ? 'B' : 'R'; // Switch player
        return "Continue";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Connect4:
    def __init__(self):
        self.rows = 6
        self.cols = 7
        self.grid = [['-' for _ in range(self.cols)] for _ in range(self.rows)]
        self.current_player = "R"  # Red starts the game

    def drop_disc(self, col):
        # Check if the column is valid
        if col < 0 or col >= self.cols or self.grid[0][col] != '-':
            return False  # Invalid move

        # Drop disc to the lowest empty position in the column
        for row in range(self.rows - 1, -1, -1):
            if self.grid[row][col] == '-':
                self.grid[row][col] = self.current_player
                return (row, col)  # Return the position of the disc

    def check_win(self, row, col):
        # Check horizontal, vertical, and diagonal lines
        def count_consecutive(x, y, dx, dy):
            count = 0
            piece = self.grid[x][y]
            while 0 <= x < self.rows and 0 <= y < self.cols and self.grid[x][y] == piece:
                count += 1
                x += dx
                y += dy
            return count

        for dx, dy in [(0, 1), (1, 0), (1, 1), (1, -1)]:
            # Check both directions
            total = count_consecutive(row, col, dx, dy) + count_consecutive(row, col, -dx, -dy) - 1
            if total >= 4:
                return True
        return False

    def play(self, col):
        position = self.drop_disc(col)
        if not position:
            return "Invalid move. Try again."
        
        row, col = position
        if self.check_win(row, col):
            return f"Player {self.current_player} wins!"

        # Switch player
        self.current_player = "B" if self.current_player == "R" else "R"
        return "Continue"

# Simulation
game = Connect4()
print(game.play(3))  # Drop disc in column 3
print(game.play(3))  # Drop disc in column 3

Complexity

  • ⏰ Time complexity: O(h)
    • Drop disc: O(H) where H = 6 (rows in a column).
    • Check win conditions: O(H * W + Diagonals) ≈ O(42) (constant for this game grid).
  • 🧺 Space complexity: O(h*w) for grid storage