Connect Four

Connect Four is a good game-design warm-up. Two players drop discs into a 6×7 grid; the first to line up four in a row (horizontally, vertically or diagonally) wins. The interesting parts are separating board rules from game flow, and checking for a win efficiently after each move.

Requirements#

Pin down the rules before you design anything:

1. The board is 6 rows × 7 columns.
2. Two players take turns choosing a column; the disc drops to the lowest empty row in that column.
3. After each move, check for a winner.
4. If the board fills with no winner, the game is a draw and further moves are rejected.
5. Choosing a full column is an invalid move.

Actors: two players (and the game system that referees).

Clarifications: exactly two players; no undo/redo.

Out of scope: UI, concurrency.

Core entities#

Four classes cover the whole game:

Relationships#

Keep the board and the game loop ignorant of each other's details:

• Game → Board (composition: the game owns its board).
• Game → Player × 2 (association: players exist independently).
• Board knows nothing about turns; Game knows nothing about grid geometry.

Key flows#

Two flows matter: making a move and checking for a win.

Move:

1. Reject the move if the game is over.
2. Ask the board to drop the disc. It returns the landing cell, or None if the column is full.
3. Check for a win from that cell.
4. Otherwise, check for a full board (draw).
5. Otherwise, switch player.

Win check: you only need to look at lines through the cell just placed. For each of the four axes (horizontal, vertical, two diagonals), count matching discs in both directions and add one for the new disc. If any total reaches 4, it's a win. That's $O(1)$ per move instead of rescanning the board.

Code#

A compact Python implementation of the design above:

from enum import Enum
from typing import Optional, Tuple


class GameStatus(Enum):
    IN_PROGRESS = "IN_PROGRESS"
    DRAW = "DRAW"
    WIN = "WIN"


class Player:
    def __init__(self, player_id: str, name: str, mark: str):
        self.id = player_id
        self.name = name
        self.mark = mark


class Board:
    EMPTY = "."
    CONNECT = 4

    def __init__(self, rows: int = 6, cols: int = 7):
        self.rows = rows
        self.cols = cols
        self.grid = [[self.EMPTY] * cols for _ in range(rows)]
        self.moves = 0  # track fills so is_full() is O(1)

    def is_full(self) -> bool:
        return self.moves == self.rows * self.cols

    def can_place(self, col: int) -> bool:
        # The top row is the last to fill, so it alone tells you
        # whether the column is full
        return 0 <= col < self.cols and self.grid[0][col] == self.EMPTY

    def drop(self, col: int, mark: str) -> Optional[Tuple[int, int]]:
        if not self.can_place(col):
            return None
        for row in range(self.rows - 1, -1, -1):  # gravity: bottom up
            if self.grid[row][col] == self.EMPTY:
                self.grid[row][col] = mark
                self.moves += 1
                return row, col
        return None

    def _count(self, row: int, col: int, dr: int, dc: int,
               mark: str) -> int:
        """Count consecutive `mark` cells stepping by (dr, dc),
        starting one step away."""
        count = 0
        r, c = row + dr, col + dc
        while (0 <= r < self.rows and 0 <= c < self.cols
               and self.grid[r][c] == mark):
            count += 1
            r, c = r + dr, c + dc
        return count

    def is_winning_move(self, row: int, col: int, mark: str) -> bool:
        # Four axes; each is walked in both directions
        for dr, dc in [(0, 1), (1, 0), (1, 1), (1, -1)]:
            total = (1 + self._count(row, col, dr, dc, mark)
                     + self._count(row, col, -dr, -dc, mark))
            if total >= self.CONNECT:
                return True
        return False


class Game:
    def __init__(self, board: Board, players: Tuple[Player, Player]):
        self.board = board
        self.players = players
        self.current = 0                 # index into players
        self.status = GameStatus.IN_PROGRESS
        self.winner: Optional[Player] = None

    @property
    def current_player(self) -> Player:
        return self.players[self.current]

    def move(self, col: int) -> Optional[Tuple[int, int]]:
        if self.status != GameStatus.IN_PROGRESS:
            return None                  # game already over

        landing = self.board.drop(col, self.current_player.mark)
        if landing is None:
            return None  # invalid move: full or out-of-range column

        row, c = landing
        if self.board.is_winning_move(row, c, self.current_player.mark):
            self.status = GameStatus.WIN
            self.winner = self.current_player
        elif self.board.is_full():
            self.status = GameStatus.DRAW
        else:
            self.current = 1 - self.current  # switch turns
        return landing


if __name__ == "__main__":
    game = Game(Board(), (Player("1", "Ana", "X"), Player("2", "Ben", "O")))
    for col in [0, 1, 0, 1, 0, 1, 0]:   # X stacks four in column 0
        game.move(col)
    print(game.status.name, game.winner.name)  # WIN Ana
    print(game.move(3))                        # None: game is over

Extensions and trade-offs#

The design stretches to common follow-up questions:

• Configurable size and connect length: already parameterized via rows, cols and CONNECT.
• More players: store players in a list and rotate with (current + 1) % len(players).
• Undo: keep a stack of moves (row, col); pop to clear the cell, decrement moves, and switch back.
• AI opponent: add a MoveStrategy interface (human input, random, minimax) that Game calls for the current player.
• Separation: Board stays reusable for other grid games because it doesn't know about turns.

Key takeaways#

• Split board rules (placement, win detection) from game flow (turns, status).
• Check only the lines through the last move: four axes, both directions.
• Track a move counter so "is the board full?" is $O(1)$.
• Reject moves after the game ends and on full columns.