♞ What is the Knight’s Tour Problem?

The Knight’s Tour is a classic puzzle from combinatorics and graph theory: given an n×n chessboard and a knight placed on any starting square, can the knight visit every square on the board exactly once using only valid knight moves? A knight moves in an L-shape — two squares in one direction and one square perpendicular, giving it up to eight possible moves from any position.

The problem has been studied for over a thousand years. Arab mathematicians documented it as early as the 9th century, and Leonhard Euler conducted a systematic mathematical analysis in 1759. There are two variants: an open tour, where the starting and ending squares differ, and a closed (re-entrant) tour, where the knight can return to its starting square in one move. On the standard 8×8 board, there are over 26 trillion distinct open tours.

From an algorithmic standpoint, the Knight’s Tour is a special case of the Hamiltonian path problem on a graph, where each square is a node and edges connect squares reachable by a knight move. Finding a Hamiltonian path is NP-complete in general, but the regular structure of the chessboard makes efficient heuristics possible.

The most well-known heuristic is Warnsdorff’s rule (H.C. von Warnsdorff, 1823): at each step, move to the unvisited square that has the fewest onward moves. This greedy approach runs in linear time relative to the number of squares and finds a tour almost always on boards of size 5×5 and above — which is exactly what we’ll ask Codex to implement.

🗺️ What We’re Building

By the end of this walkthrough, we’ll have a fully working Python application with three layers built up incrementally through Codex prompts:

⚙️ Prerequisites

Before starting, make sure you have:

• Codex CLI installed (brew install --cask codex or npm i -g @openai/codex)
• Authenticated with a ChatGPT Plus/Pro account or an OpenAI API key
• Python 3.10+ available in your shell
• Git installed on your machine (see Project Setup below if you haven’t configured it yet)

📁 Project Setup

We’ll use Git throughout this guide as a safety net — you can git diff to review what Codex changed, or revert entirely if a phase goes wrong. If this is your first time using Git on this machine, configure your identity first:

git config --global user.name  "Your Name"
git config --global user.email "[email protected]"

This only needs to be done once. To verify your settings at any time:

git config --global --list

Now create the project directory, initialise the repo, and add an empty conftest.py in the root. The conftest.py file signals to pytest that the project root is the base directory, which allows it to resolve imports like from knight_tour import solve correctly from within the tests/ subdirectory:

mkdir knights-tour && cd knights-tour
git init
touch conftest.py
git commit --allow-empty -m "initial commit"

With the repo ready, launch Codex from inside the project directory:

codex

Once the TUI loads, your very first prompt should be to generate an AGENTS.md file. This acts as a standing project-level system prompt — Codex reads it automatically at the start of every future session, so you don’t have to repeat your conventions each time.

Codex will create the file and show you the diff to review. Accept it, then commit before moving to Phase 1. Every subsequent Codex session in this directory will pick up these rules automatically.

Phase 1 — Core Solver

Still in the same Codex session, enter the Phase 1 prompt. Codex already has the project context from AGENTS.md, so you can get straight to the point:

Codex will show you its plan before making any changes. In Auto mode, you’ll see it create each file with a diff preview. Here’s a simplified version of what the generated knight_tour.py looks like:

MOVES = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]

def get_neighbours(x, y, n, visited):
    return [(x+dx, y+dy) for dx,dy in MOVES
            if 0 <= x+dx < n and 0 <= y+dy < n
            and not visited[x+dx][y+dy]]

def solve(n, start_x, start_y):
    visited = [[False]*n for _ in range(n)]
    board   = [[-1]*n   for _ in range(n)]
    x, y = start_x, start_y
    visited[x][y] = True
    board[x][y]   = 0
    for move in range(1, n*n):
        neighbours = get_neighbours(x, y, n, visited)
        if not neighbours:
            return None
        x, y = min(neighbours,
                   key=lambda p: len(get_neighbours(p[0],p[1],n,visited)))
        visited[x][y] = True
        board[x][y]   = move
    return board

Run it in a separate terminal to verify:

python3 main.py --size 8 --row 0 --col 0

You should see a numbered 8×8 grid where each number represents the move order of the knight. Commit the result before moving to Phase 2.

Phase 2 — Tests & Colourised Output

In the same Codex session, enter the next prompt. You don’t need to re-explain the project — Codex still has full context from Phase 1.

Before entering the prompt, install pytest in a separate terminal. Codex will attempt to run the test suite as part of its workflow, so the package must be present beforehand:

pip3 install pytest

Codex will generate the test file and extend knight_tour.py with the colour function. Key tests:

import pytest
from knight_tour import solve

def is_valid_knight_move(x1, y1, x2, y2):
    dx, dy = abs(x2-x1), abs(y2-y1)
    return (dx, dy) in {(1,2),(2,1)}

@pytest.mark.parametrize("n,r,c", [(5,0,0),(6,1,1),(8,0,0),(8,3,4)])
def test_valid_tour(n, r, c):
    board = solve(n, r, c)
    assert board is not None
    flat = sorted(v for row in board for v in row)
    assert flat == list(range(n*n))

def test_no_solution_n2():
    assert solve(2, 0, 0) is None

Run the tests in a separate terminal to verify. If you created conftest.py in the project root during setup, pytest will resolve imports correctly:

pytest tests/ -v

If you see a ModuleNotFoundError: No module named 'knight_tour', use the module invocation instead, which explicitly adds the project root to sys.path:

python3 -m pytest tests/ -v

And try the colour flag:

python3 main.py --size 8 --colour

Phase 3 — Flask Web App with Animated Visualisation

Now we go beyond the terminal. In the same session (or a fresh one — Codex resumes from codex resume --last), enter the Phase 3 prompt:

Codex generates app.py and embeds the full HTML/JS using Flask’s render_template_string. The key backend endpoint:

from flask import Flask, request, jsonify, render_template_string
from knight_tour import solve
app = Flask(__name__)

@app.route("/solve", methods=["POST"])
def solve_tour():
    data = request.get_json()
    n, row, col = int(data.get("size",8)), int(data.get("row",0)), int(data.get("col",0))
    if not (5 <= n <= 10):
        return jsonify({"error": "Board size must be between 5 and 10"}), 400
    board = solve(n, row, col)
    if board is None:
        return jsonify({"error": "No solution found"}), 422
    return jsonify({"board": board, "n": n})

Install Flask and run:

pip3 install flask
python3 app.py

Visit http://localhost:5000, choose your board size and starting square, hit Solve, and watch the knight’s path animate across the canvas.

🔄 Iterating Further — More Prompt Ideas

Once your three-phase app is working, you can keep iterating in the same session. Here are some prompts to take it further:

✅ Effective Prompting Tips for Codex

A few patterns that made a noticeable difference in the quality of output across this walkthrough: