Design Tic Tac Toe
A vending machine has three knobs and a coin slot, and once you understand the three knobs you know the whole machine. Design problems work the same way. Before you write the first line of game code, you pick the knobs — the handful of types and functions everything else has to go through. The board is a knob. The status of the game is a knob. The act of playing one move is a knob. Get the knob shapes right and the rest of the code falls out almost by itself. Get them wrong and you spend the next week reaching past the front panel to wire things together by hand.
The interview style of this problem comes from the late 1990s, when Microsoft and Amazon started asking candidates to design small systems on a whiteboard instead of solving puzzles. The point was never the game. The point was watching the candidate pick the types. A weak answer reaches straight for a 2D array of strings and a flag called gameOver and starts pushing logic into the function that reads moves. A stronger answer pauses, names the three states the game can be in, names the three things a square can hold, then writes the function signatures before the function bodies. Rust rewards this style harder than any other language because the compiler will check that the types you named actually fit together before it lets the program build.
Start with the smallest type the game has — what fits inside one square.
#[derive(Copy, Clone, PartialEq, Eq)]
enum Cell {
Empty,
X,
O,
}
#[derive(Copy, Clone, PartialEq, Eq)]
enum Status {
InProgress,
Won(Cell),
Draw,
}
struct Board {
cells: [[Cell; 3]; 3],
turn: Cell,
}A Cell is exactly one of three things — empty, X, or O — and enum is the keyword that says exactly one. Using an enum here instead of a char or a String is the first design choice and it pays back twice. The compiler will refuse to compile a match arm that forgets one of the three cases, so the day someone adds a fourth piece type the rest of the code points to every spot that needs to think about it. And a Cell is one byte under the hood — smaller than a String, faster to copy, no allocations.
Status is the same trick at the level of the whole game. The game is in progress, or it has been won by a specific player, or it is a draw. Three states, one type. The Won variant carries a Cell payload because "won" is not complete information on its own — somebody won, and the type makes you say who. This is the move that distinguishes a designer who knows the language from one who is still translating from another. A C answer would use two flags — is_over and winner — and then nothing stops a caller from reading winner while is_over is false. A Rust enum welds the two facts into one value so the illegal combination cannot exist.
The Board itself is the smallest container that holds the state. Three rows of three cells, plus whose turn it is. The turn field lives on the board for the same reason Status::Won carries a Cell — the board owns every fact about itself. A move function does not need to ask the caller "whose turn is it now?" because the board already knows.
The next knob is the API. Three methods do all the work the outside world cares about — play, status, render — and the signatures matter more than the bodies.
impl Board {
fn new() -> Self {
Self {
cells: [[Cell::Empty; 3]; 3],
turn: Cell::X,
}
}
fn play(&mut self, row: usize, col: usize) -> Result<(), &'static str> {
if row > 2 || col > 2 {
return Err("off the board");
}
if self.cells[row][col] != Cell::Empty {
return Err("cell taken");
}
if !matches!(self.status(), Status::InProgress) {
return Err("game over");
}
self.cells[row][col] = self.turn;
self.turn = match self.turn {
Cell::X => Cell::O,
Cell::O => Cell::X,
Cell::Empty => Cell::X,
};
Ok(())
}
fn status(&self) -> Status {
let lines: [[(usize, usize); 3]; 8] = [
[(0, 0), (0, 1), (0, 2)],
[(1, 0), (1, 1), (1, 2)],
[(2, 0), (2, 1), (2, 2)],
[(0, 0), (1, 0), (2, 0)],
[(0, 1), (1, 1), (2, 1)],
[(0, 2), (1, 2), (2, 2)],
[(0, 0), (1, 1), (2, 2)],
[(0, 2), (1, 1), (2, 0)],
];
for line in &lines {
let a = self.cells[line[0].0][line[0].1];
let b = self.cells[line[1].0][line[1].1];
let c = self.cells[line[2].0][line[2].1];
if a != Cell::Empty && a == b && b == c {
return Status::Won(a);
}
}
for row in &self.cells {
for cell in row {
if *cell == Cell::Empty {
return Status::InProgress;
}
}
}
Status::Draw
}
fn render(&self) -> String {
let mut out = String::new();
for (i, row) in self.cells.iter().enumerate() {
out.push(' ');
for (j, cell) in row.iter().enumerate() {
out.push(glyph(*cell));
if j < 2 {
out.push_str(" | ");
}
}
out.push('\n');
if i < 2 {
out.push_str(" ---+---+---\n");
}
}
out
}
}
fn glyph(c: Cell) -> char {
match c {
Cell::Empty => '.',
Cell::X => 'X',
Cell::O => 'O',
}
}
fn label(s: Status) -> String {
match s {
Status::InProgress => "in progress".to_string(),
Status::Won(Cell::X) => "won by X".to_string(),
Status::Won(Cell::O) => "won by O".to_string(),
Status::Won(Cell::Empty) => "won by nobody".to_string(),
Status::Draw => "draw".to_string(),
}
}Read play first. It takes &mut self because it changes the board. It takes a row and a column. It returns Result<(), &'static str> because a move can fail for three reasons the caller has to handle — off the board, cell already taken, game already over — and the type forces the caller to look at the answer. A version that returned a bool would let half the calling code forget the failure case. A version that panicked on bad input would crash the program when a UI sent a stray click. Result is the only honest answer, and the &'static str payload is the cheapest way to name the reason without allocating a heap string.
The body of play is a checklist. Check the coordinates, check the cell, check the status, then commit the change and flip the turn. The order matters — every guard runs before the board is touched, so a rejected move leaves the board exactly as the caller found it. This is the same idea a database transaction uses. Either the whole move happens or none of it does.
status takes &self because reading the board does not change it. It walks the eight lines a player can win on — three rows, three columns, two diagonals — and asks each line the same question. Are all three cells the same player, and not empty? If any line says yes, the game is won. If no line says yes and no empty cells remain, it is a draw. Otherwise the game is still in progress. The list of lines lives inside the function as a plain array because there are exactly eight of them and they never change.
render takes &self and hands back a String because rendering should never print directly. A method that prints can only be used one way. A method that returns the string can be printed, written to a log, fed to a test, or sent over a socket. The cost is one allocation per call. The payoff is that every part of the program that wants to look at the board uses the same renderer and they all agree on what the board looks like.
Now drive the design through a real scripted game and watch every output.
fn show_types() {
let board = Board::new();
println!("--- fresh board ---");
print!("{}", board.render());
println!("turn: {}", glyph(board.turn));
println!("status: {}", label(board.status()));
println!();
}
fn show_game() {
let moves = [(0, 0), (1, 1), (0, 1), (2, 2), (0, 2)];
let mut board = Board::new();
println!("--- scripted game ---");
for (i, (row, col)) in moves.iter().enumerate() {
let mover = glyph(board.turn);
match board.play(*row, *col) {
Ok(()) => println!("move {}: {} -> ({},{})", i + 1, mover, row, col),
Err(why) => println!("move {}: rejected ({})", i + 1, why),
}
print!("{}", board.render());
println!("status: {}", label(board.status()));
println!();
}
let bad = board.play(0, 0);
println!("replay (0,0): {:?}", bad);
let off = board.play(5, 5);
println!("off-board (5,5): {:?}", off);
}The move list is hardcoded so the binary is deterministic, but the shape of the loop is the shape a real driver would have — read a move, call play, handle the Result, print the board, ask for the status. Swap the hardcoded list for a function that reads from a socket or a UI and nothing else has to change. The board does not know or care where the moves come from.
--- fresh board ---
. | . | .
---+---+---
. | . | .
---+---+---
. | . | .
turn: X
status: in progress
--- scripted game ---
move 1: X -> (0,0)
X | . | .
---+---+---
. | . | .
---+---+---
. | . | .
status: in progress
move 2: O -> (1,1)
X | . | .
---+---+---
. | O | .
---+---+---
. | . | .
status: in progress
move 3: X -> (0,1)
X | X | .
---+---+---
. | O | .
---+---+---
. | . | .
status: in progress
move 4: O -> (2,2)
X | X | .
---+---+---
. | O | .
---+---+---
. | . | O
status: in progress
move 5: X -> (0,2)
X | X | X
---+---+---
. | O | .
---+---+---
. | . | O
status: won by X
replay (0,0): Err("cell taken")
off-board (5,5): Err("off the board")Read the output top to bottom. The fresh board prints empty cells with X to move and status in progress. Move 1 places X at (0,0) and the turn flips. Moves 2 through 4 fill in the middle and a corner with the status staying in progress because no line is full yet. Move 5 completes the top row with three X's and the status flips to won by X. Then two failures land at the bottom — the replay at (0,0) returns Err("cell taken") and the off-board move at (5,5) returns Err("off the board"). Both errors come back as values the caller could handle without the program ever crashing.
One question worth asking — why does play return Err("game over") instead of just refusing silently after the game is won? The reason is the same as the enum check on Status. A silent refusal is a bug waiting to ship. A loud Err makes the caller decide what to do — close the connection, show a dialog, score the match — and the compiler will not let them ignore the answer because Result has to be matched or explicitly discarded. Every failure mode the game has is now a value the rest of the program can see.
The thing this design cannot do on its own is grow past one game type. A Connect Four board is six rows of seven cells with a "drop" instead of a "place," and a Chess board has a much richer move type than (row, col). The next bottleneck is sharing the API shape across game families so a tournament runner can host any of them without caring which one — which is what traits exist to solve.