I built it to learn minimax, the classic algorithm for game-playing computers, and noughts and crosses is the classic small case to try it on. This is the write-up for Noughts and Crosses v1, one of the Python and Flask projects on my portfolio page. The full source isn’t published, but I can show the interesting part.
You can play it here. Fair warning: play fairly and you can’t win.
Noughts and Crosses v1 part-way through a game. The scores carry over between rounds.
What the app does
You type a name, press Start Game and get a three-by-three board. You are O, you click a cell, and the computer answers with an X straight away. The page keeps a running score for you and for the computer, and a Restart button starts another round without losing the scores.
The page is a handful of Jinja templates, a stylesheet and a little jQuery on the game page. Each click sends one POST to Flask, which returns the new board and whether anyone has won, drawn or neither. The browser only draws what it is told. All of the game logic is on the server.
My portfolio page invites you to “pretend you are in the 80’s and do a little bit of Wargaming”. The reference is WarGames (1983), where the computer works out from endless games of noughts and crosses that the only winning move is not to play. The joke fits, because that is more or less what happens here.
How the computer chooses its move
The opponent uses minimax, the textbook algorithm for two-player games with perfect information. It tries every legal move, then every reply to that move, and so on until the game ends, and it scores each finished game: ten for an X win, minus ten for an O win, zero for a draw. X picks the move that leads to the highest score, assuming O will always pick the reply that leads to the lowest. Here is the function:
def minimax(board, depth, is_maximizing):
score = evaluate(board)
if score == 10:
return score - depth
if score == -10:
return score + depth
if not any('_' in row for row in board):
return 0
if is_maximizing:
best_score = -1000
for i in range(3):
for j in range(3):
if board[i][j] == '_':
board[i][j] = 'X'
best_score = max(best_score, minimax(board, depth+1, not is_maximizing))
board[i][j] = '_'
return best_score
else:
# …the same loop for O, using min() and starting from 1000
Two details are worth explaining.
Depth-adjusted scoring. A win scores ten minus the number of moves it took to get there, and a loss scores minus ten plus the depth. Without that, a win in two moves and a win in six are both worth ten, and the computer might wander about for no reason. With it, the computer takes the quickest win on offer and, if it is losing, drags the game out for as long as it can. It makes the opponent look purposeful, which costs one line each way.
Why you can’t win. The board is small enough for the search to look at every possible game, so there is no heuristic and no guessing: the computer never misjudges a position. Noughts and crosses is a solved game, and with perfect play from both sides it ends in a draw. Against a perfect opponent the best you can do is draw, and any slip hands the computer the win.
The search is cheap here. Even the computer’s first reply looks at no more than about 40,000 move sequences, which Python gets through quickly, so there is no pruning and no caching. Alpha-beta pruning would matter on a bigger board; on this one it would be extra code for no visible gain.
The “user system” is a name in a cookie
The portfolio page says the app has “the starts of a user system”. To be exact, it is a name field. What you type is stored in Flask’s session, along with the board and both scores. The session is a signed cookie held in your browser, so the server keeps no state of its own: no accounts, no passwords, no database.
That has a few consequences:
Clear your cookies and the scores go with them.
Two browsers, two separate players, even if they use the same name.
Nothing is shared, so there is no leaderboard.
The data lives on the client. It is signed, but anyone can read it.
The plan was proper logins with a history of your games. Two unused files in the project are the start of it: a dashboard template that welcomes you by username, lists your game history and has a Logout button, and a script that posts each move to a numbered game. Neither is wired up. Version 1 stopped at a name in the session.
What is rough or missing
No check that a square is empty. The server never checks that the square you click is empty, and the page lets you click any square. Click one of the computer’s Xs and it becomes an O, so you can cheat your way to a win. “Unbeatable” therefore means unbeatable in a fair game. Clicks after a game has ended carry on being scored: after a win, each further click re-evaluates the same winning line and adds another point.
Restart doesn’t redraw the board. The server resets the board, but its reply doesn’t include the new one, and the page tries to redraw from that reply. The script stops with an error, so the old game stays on screen until your next click (or a reload) draws the fresh board.
Development server. The container, built on python:3.9 with Flask unpinned, runs python app.py: Flask’s built-in Werkzeug server, behind a reverse proxy. That is fine for a demo and wrong for anything with real traffic.
No tests, no README, no history. The code was only put under version control in October 2026, so I can’t show you how it evolved.
What I would do differently
Minimax was the easy part. The function is under 30 lines. The bugs all ended up in the plumbing around it: whose turn it is, which squares are free, when a game is over, what Restart sends back and how the score is kept. Both of the flaws at the top of that list live there, not in the algorithm. If I were starting again, I would give that game-state code as much care as the clever bit.
Have a go
If you can get a draw, you’ve played as well as anyone can against it. Try it at the live demo, and if you want the other projects, they’re all on the portfolio page. Good luck!
My first Sudoku solver is quick on easy puzzles and hopeless on hard ones. This post puts measured numbers on how far the later versions moved on from it. It covers the four versions on my portfolio page, from the first plain backtracking solver to the January 2024 update. The full source isn’t published, but the interesting parts are quoted below.
It started as an algorithm challenge: I wanted to write a solver and then keep making it faster. The Flask page was a way to show each version working.
What the project is
Each version is a small Flask app with a nine-by-nine grid of number inputs. You fill in the givens, press the button and the server either shows the solved grid or says the puzzle can’t be solved. The apps run in Docker (python:3.8-slim-buster images, Flask unpinned, the Werkzeug development server), one container per version, behind a reverse proxy on cosmo.ihelm.org.uk. All four are still live:
Sudoku Solver v2 (January 2024 update) after solving a puzzle. The iteration counter on each version counts something different, which matters later.
Versions 1 and 1.1 date from 22 and 23 January 2023, and version 2 followed on 29 January 2023. The January 2024 update came almost a year later, on 21 January 2024.
Version 1: plain backtracking
Version 1 is the textbook approach. Find the first empty cell, reading row by row. Try each digit from 1 to 9. If a digit doesn’t clash with anything, place it and recurse. If the recursion fails, take the digit back out and try the next one. When no digit fits, return and let the previous cell try something else.
def solve(grid):
global iterations
empty = find_empty(grid)
if not empty:
return True
row, col = empty
for num in range(1, 10):
if is_valid(grid, (row, col), num):
iterations += 1
grid[row][col] = num
if solve(grid):
return render_template("solution.html", grid=grid, iterations=iterations)
grid[row][col] = 0
return False
def find_empty(grid):
for row in range(9):
for col in range(9):
if grid[row][col] == 0:
return (row, col)
return None
def is_valid(grid, pos, num):
# Check row
for i in range(9):
if grid[pos[0]][i] == num:
return False
# Check col
# …
It works, but it is crude, and it has rough edges I’d rather admit to than hide:
is_valid rescans the row, the column and the box for every digit tried.
There is no check on the input. Give it a grid with a repeated given and it searches the whole tree before saying “Puzzle cannot be solved”.
solve returns render_template(...) from inside the recursion. On success, the solution page is rendered at every level on the way back up. It is wasteful.
The iteration counter is never reset. On the live server it accumulates across visitors until the container restarts.
Version 1.1: a better page, the same algorithm
Version 1.1 is the same solver with a better page: a styled grid with the three-by-three boxes marked, a proper title and a meta description, the first bit of SEO. Nothing changed in the search. I include it because the portfolio lists it, and because it makes a useful control: any difference between 1 and 1.1 is not about the algorithm.
Version 2: validate first, then try only what fits
Version 2 made two changes. First, is_input_valid checks the givens up front and rejects a grid with repeated digits (“Puzzle cannot be solved as the input is invalid”) instead of searching for a solution that can’t exist.
Second, solve stopped trying every digit. Trying digits that couldn’t possibly fit looked wasteful, so cutting them out was the next obvious speed-up. It builds the set of candidates for the cell from its row, column and box, and tries only those:
possibilities = {1, 2, 3, 4, 5, 6, 7, 8, 9}
for i in range(9):
if grid[row][i] in possibilities:
possibilities.remove(grid[row][i])
if grid[i][col] in possibilities:
possibilities.remove(grid[i][col])
box_x = col // 3
box_y = row // 3
for i in range(box_y*3, box_y*3 + 3):
iterations += 1
for j in range(box_x * 3, box_x*3 + 3):
if grid[i][j] in possibilities:
possibilities.remove(grid[i][j])
for num in possibilities:
if is_valid(grid, (row, col), num):
# …
I described this on the portfolio page as drastically reducing solving time. The measurements below don’t bear that out, and the reason is worth understanding. Version 2 still picks the first empty cell in row order, and its candidates come out in ascending order. Removing the digits that is_valid would have rejected anyway doesn’t change which digits get tried, in which order, so it explores exactly the same search tree as version 1. It does less work per step, because it doesn’t call is_valid for digits already ruled out. But it takes exactly as many steps.
Version 2, January 2024 update: fewest candidates first
This is the version where the search itself changed. (Its own page calls it “Version 4”; I’ve kept the portfolio’s name for it here.) There are two ideas.
Pick the most constrained cell, not the first one.find_least_possibilities looks at every empty cell, works out its candidates and returns the cell with the fewest. This is the minimum remaining values heuristic (MRV), sometimes called “fail first”. A cell with one candidate is forced, so you place it immediately. A cell with zero candidates means you have already gone wrong, and you find out at once instead of after filling in a dozen cells that never mattered.
def find_least_possibilities(grid):
min_count = 10 # More than the maximum possible count (9)
best_cell = None
for row in range(9):
for col in range(9):
if grid[row][col] == 0:
possibilities = find_possibilities(grid, row, col)
if len(possibilities) < min_count:
min_count = len(possibilities)
best_cell = (row, col)
return best_cell
Check the consequences of each move straight away. After placing a digit, forward_check looks at every empty cell, and if any of them has been left with no candidates, the move is rejected without recursing at all:
def forward_check(grid, row, col, num):
original_num = grid[row][col]
grid[row][col] = num # Temporarily place the number
for i in range(9):
for j in range(9):
if grid[i][j] == 0: # Check only empty cells
if not find_possibilities(grid, i, j):
grid[row][col] = original_num # Restore the original number
return False
grid[row][col] = original_num # Restore the original number
return True
The cost is that each call now does much more work. Choosing a cell scans every empty cell, and forward checking scans them all again for every digit tried. Fewer calls only pays off if the saving outweighs that, and as the results show, on easy puzzles it makes no visible difference. This version keeps is_input_valid from version 2.
Both ideas were my own, worked out the way a person tackles a Sudoku by hand: start with the cell that has the fewest options, and notice straight away when a move leaves another cell with none.
How I measured it
The apps’ own iteration counters can’t be compared. Version 1 counts only the digits that pass is_valid, and never resets. Version 1.1 counts every digit it tries. Version 2 adds three on each call to solve, because the increment sits inside the loop over the box’s rows. The January 2024 version counts only the digits it places. So the “approximately 1/100th” on my portfolio page, comparing the January 2024 version with version 2, was never a like-for-like figure. The rest of this post is the like-for-like version.
For this post I wrote a small test harness that sends the same puzzles to all four apps through Flask’s test client and counts one common unit: the number of calls to solve, recursive calls included. Every run has a 60 s limit, and a run that hits it is stopped and reported as not finished. The harness checks every answer independently against the puzzle’s givens, rather than trusting the app, and it repeats each finished run and takes the median time. The times come from my PC, not the server, and the demos run on a different Python version, so treat them as relative to one another rather than as server figures. Timings of a few milliseconds vary noticeably from run to run, so I make no claims about differences between them.
Built against backtracking (17 clues): the puzzle illustrating Wikipedia’s Sudoku solving algorithms article, described there as designed to work against the brute-force algorithm. I read the digits from the image.
Valid givens, no solution (33 clues): I built this from the Easy puzzle by adding a 5 in the first cell, where the real solution has a 4. The 5 repeats nothing already given in its row, column or box, so only a search can find the problem.
Duplicate givens (33 clues): I built this from the Easy puzzle by adding a second 3 to the first row.
Results
Solve calls and outcome per version. Times are shown only where the run was long enough for them to mean anything. Every other run on Easy, no solution and duplicate givens finished in a few milliseconds.
Puzzle
v1
v1.1
v2
v2 (January 2024)
Easy
201, solved
201, solved
201, solved
50, solved
Hard
335,638, solved, 1.58 s
335,638, solved, 1.64 s
335,638, solved, 1.32 s
3,670, solved, 0.406 s
Minimal (17 clues)
did not finish in 60 s (13,463,698 reached)
did not finish in 60 s (12,996,226 reached)
did not finish in 60 s (15,440,586 reached)
4,113, solved, 0.530 s
Built against backtracking
did not finish in 60 s (13,369,072 reached)
did not finish in 60 s (12,981,751 reached)
did not finish in 60 s (10,908,674 reached)
39,223, solved, 4.72 s
Valid givens, no solution
349, unsolvable
349, unsolvable
349, unsolvable
4, unsolvable
Duplicate givens
308, unsolvable
308, unsolvable
0, rejected as invalid
0, rejected as invalid
What the table shows
Versions 1, 1.1 and 2 search exactly the same tree. Wherever they finish, they make the identical number of calls: 201 on Easy and 335,638 on Hard. Version 2 only makes each call cheaper. On Hard that gets it from 1.58 s to 1.32 s, but it is the same search.
On easy puzzles, the January 2024 version makes fewer calls but is no faster. On Easy it needs 50 calls against 201, yet all four versions finish in a few milliseconds and I wouldn’t claim a winner. This is the trade-off from earlier: a smarter call is a more expensive call.
On a hard puzzle, the call count wins. On Hard, the January 2024 version makes 3,670 calls against 335,638. Version 2 makes 91.5 times as many calls, and takes 3.24 times as long. Version 1 takes 3.88 times as long. The time ratio is smaller than the call ratio because each of the January 2024 version’s calls does far more work. It is still a large gain.
On the hardest puzzles, it is the difference between solving and not solving. The 17-clue puzzles give a plain first-empty-cell search very little to work with. With so few givens, the early cells have many candidates and the contradiction may only appear many levels deeper, so the search spends its time in huge subtrees that contain no solution. Versions 1, 1.1 and 2 didn’t finish either one within 60 s. The January 2024 version solved the first in 0.530 s and the Wikipedia puzzle, built specifically to defeat brute force, in 4.72 s.
Early rejection pays off on impossible puzzles. With the valid-looking but unsolvable puzzle, the first three versions make 349 calls to discover there is no solution, while the January 2024 version needs 4. Duplicate givens cost version 1 and 1.1 308 calls, and cost versions 2 and later none at all, because the input check rejects them first.
Where the old 1/100th claim stands
The portfolio page says the January 2024 version “reduces solution attempts to approximately 1/100th of the v2 algorithm”. Measured as solve calls, on Hard, version 2 makes 91.5 times as many, so the claim is close there. On Easy it is 4.02 times. On the two hardest puzzles version 2 doesn’t finish at all, so there is no ratio to quote. “Approximately 1/100th” is a fair description of one puzzle and an overstatement for easy ones.
I’ve corrected the portfolio page to quote the measured figure.
Lessons
Three things I’d pass on from this:
Measure before you claim, and measure like for like. My own “approximately 1/100th” was read off counters that counted different things.
Doing less work per step and taking fewer steps are different improvements. Version 2 did the first and the January 2024 version did the second.
A cleverer search is not always faster. Where the puzzle is easy, the extra work per call cancels the saving.
Wrapping up
That is the whole story of the four versions, from a solver that falls over on a 17-clue puzzle to one that solved every puzzle I gave it. If you want to compare them yourself, the four demos are all still live. Try the same hard puzzle on version 2 and the January 2024 update and watch which one comes back. Good luck, and let me know if you find a puzzle that stumps the last one.
