Problem Breakdown
Connect Four
Published ·
hard
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
Problem recap
Connect Four is the classic 7-column by 6-row board game where RED and YELLOW take turns dropping discs into columns. Discs fall to the lowest empty cell of whichever column they're dropped into. The first player to line up four of their own discs horizontally, vertically, or along either diagonal wins.
Connect Four board showing four red discs in a row across the bottom
Your job is to write a function that picks the best move from any board position. Given a board mid-game and whose turn it is, return the column that side should play. The grader feeds you a series of starting positions, calls your function on each, and checks the column you returned against the right answer. There's no second bot to play against; the "opponent" only exists inside your own thinking.
The catch is what best means. To pick the best move, you have to think ahead — and the further ahead you can think, the better moves you'll find. The grader covers two phases. Phase 2 has three warm-up positions:
- One move ahead. RED has three in a row across the bottom of cols 0, 1, 2. RED drops col 3 → win. You only need to look at your own immediate options.
- Two moves ahead. YELLOW has three in a row and threatens to win next turn at col 3. RED has to imagine YELLOW's reply if RED ignores the threat, see the loss coming, and play col 3 to block it. That's two moves of foresight: RED's move plus YELLOW's response.
- Five moves ahead. The hard one in Phase 2. RED is to move on the position below. The right move is col 3. It looks quiet, but the response forces YELLOW into a chain of blocks that lets RED build a double threat YELLOW can only partially answer. The win takes five plies to verify — three of RED's moves and two of YELLOW's replies — and at any shallower depth every legal move just scores 0.
Forced-win position used by the Phase 2 grader. RED to move; the win is five plies deep.
Phase 3 reuses the same find_best_move against four more positions whose forced wins land at varying depths — three plies, five plies, seven plies, and nine plies. The deepest two also have non-center winning columns, so a solver that defaults to col 3 when it can't see far enough doesn't accidentally pass. Phase 3 times each call externally and gives you a 2-second wall-clock cap per test. You don't get a budget parameter, and you don't know in advance how deep the win is — same function, harder inputs.
Each extra move of foresight roughly multiplies the work by 7 (one branch per column you might play). One move ahead means scoring 7 positions. Two moves is 49. Five moves is 7⁵ = 16,807. Nine moves is 7⁹ ≈ 40 million. And the grader times each call at 2 seconds.
The amount of foresight you need on the hard tests doesn't fit in the budget at any fixed depth. The four solutions below are four different ways of making a deeper search fit in less time.
Pattern: Backtracking
Minimax is backtracking with a scoreboard. You play a move, recurse into the opponent's replies, then undo it and try the next column. Alpha-beta pruning is the same move-skipping idea you'll see across backtracking problems.
Solution 1: naive minimax
Imagine you're RED. You want to leave the game in a state where you've won, and YELLOW wants the opposite. Minimax is one recursive idea. At every level of the tree, alternate between what RED would pick and what YELLOW would pick. RED is the maximizer and picks the move with the highest score. YELLOW is the minimizer and picks the lowest. The two roles strictly alternate down the tree, because turns alternate.
The leaf-scoring rule
Walking the tree
Complexity
Where it breaks
Solution 2: alpha-beta with center-first ordering
Complexity
Where it leaves you
Solution 3: iterative deepening
Solution 4: transposition table
Benchmarks
Takeaways
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium