Hyper Sudoku AI Solver

A constraint-satisfaction AI that solves Hyper Sudoku puzzles in real time, with a visual trace of forward checking and backtracking.

The AI solves an Expert-level Hyper Sudoku in 2.81 ms with 106 assignments and 48 backtracks. The four overlapping hyper regions are color-coded so you can see all the constraints at once.

---

What is Hyper Sudoku?

Hyper Sudoku is a 9×9 Sudoku variant with four extra 3×3 regions — each cell must satisfy the standard row, column, and box constraints plus the additional hyper region it belongs to:

  W:  rows 1–3,  cols 1–3        Y:  rows 1–3,  cols 5–7
  X:  rows 5–7,  cols 1–3        Z:  rows 5–7,  cols 5–7

The extra constraints make Hyper Sudoku a strictly harder problem than classic Sudoku, and a great showcase for constraint-satisfaction techniques.

Highlights

• ⚡ Fast solver — typically solves a hard puzzle in single-digit milliseconds.
• 🧠 Real CSP techniques — forward checking, MRV (minimum remaining values), and the degree heuristic.
• 🎨 Interactive web demo — watch the AI try, place, and backtrack values cell-by-cell with adjustable speed.
• 🧩 Multiple difficulties — built-in easy, medium, hard, and expert puzzles, plus a blank board.
• ✅ Tested — 19 unit & API tests covering constraints, neighbors, error paths, and end-to-end solves.
• 💻 Clean, documented Python package — drop-in importable from your own code.

Demo

Pick a puzzle, choose a speed, hit Solve.	Watch the AI fill in the board live.

Run it locally and open http://localhost:5000:

pip install flask
python app.py

You'll see the board on the left and a control panel on the right. The AI colors cells as it explores:

Color	Meaning
🟪 Purple flash	Trying a value
🟦 Blue digit	Value placed (forward-checking the neighbors)
🟥 Red flash	Backtracking — last placement led to a dead end
🟩 Green digit	Final solved cell

Tip: The URL accepts shareable params: ?puzzle=expert&autosolve=1.

How the AI works

The solver models Hyper Sudoku as a Constraint Satisfaction Problem (CSP):

1. Variables — every empty cell.
2. Domain — the digits 1–9 still allowed for that cell, given its neighbors.
3. Constraints — no repeated digit in the same row, column, 3×3 box, or hyper region.

It then runs backtracking search augmented with three classic enhancements:

Technique	What it does	Why it matters
Forward Checking	After each placement, remove that value from the domains of all neighboring cells. If a neighbor's domain becomes empty, fail immediately.	Detects dead ends before exploring deeper.
MRV	Pick the next cell with the smallest remaining domain.	Fail fast on the most constrained variable.
Degree heuristic	Tiebreak MRV by the number of unassigned neighbors.	Choose the variable that constrains the rest of the board the most.

These together turn an exponential search into something that solves even the hardest puzzles in milliseconds.

Performance snapshot

Times measured on the bundled puzzles (single thread, Python 3.12):

Puzzle	Assignments	Backtracks	Time
Easy	30	0	~1 ms
Medium	42	0	~1 ms
Hard	52	0	~1 ms
Expert	106	48	~3 ms

Project structure

.
├── app.py                  # Flask web server (API + static)
├── solver/                 # Clean, importable Python package
│   ├── board.py            # HyperSudokuBoard + neighbor precomputation
│   ├── solver.py           # CSP solver with step recording
│   └── puzzles.py          # Sample puzzles
├── static/                 # Vanilla HTML/CSS/JS frontend (no build step)
│   ├── index.html
│   ├── style.css
│   └── app.js
├── tests/                  # 19 unit & API tests
│   ├── test_solver.py
│   └── test_api.py
├── AsfourSourceCode.py     # Original CLI entry point (now wraps the package)
├── input1.txt              # Sample puzzle for the CLI
├── docs/images/            # README screenshots
└── README.md

Using the solver from Python

from solver import HyperSudokuBoard, HyperSudokuSolver

puzzle = [
    [3, 2, 0, 5, 0, 6, 7, 0, 9],
    [0, 0, 0, 2, 8, 3, 1, 0, 5],
    [1, 0, 8, 0, 9, 0, 2, 0, 3],
    [6, 7, 3, 0, 2, 9, 8, 5, 4],
    [0, 8, 0, 7, 0, 5, 0, 1, 0],
    [2, 1, 0, 3, 4, 0, 6, 0, 7],
    [9, 6, 0, 8, 5, 2, 4, 0, 1],
    [8, 4, 2, 9, 0, 0, 0, 0, 6],
    [5, 3, 1, 6, 0, 0, 0, 2, 0],
]

board = HyperSudokuBoard(puzzle)
result = HyperSudokuSolver(board).solve()

print(result.board)
print(f"Solved in {result.stats.elapsed_ms:.2f} ms "
      f"with {result.stats.assignments} assignments "
      f"and {result.stats.backtracks} backtracks.")

The result.steps list also gives you the entire decision trace for visualization or analysis.

API

The Flask backend exposes a tiny JSON API:

Method	Endpoint	Body	Response
GET	/api/puzzles	—	{ key: { name, description, grid } }
POST	/api/solve	{ "grid": 9x9 list, "record_steps": bool }	{ solved, board, stats, steps }
GET	/api/healthz	—	{ "ok": true }

Errors return 400 with a descriptive {"error": ...} payload.

CLI

The original command-line interface still works:

python AsfourSourceCode.py
# > Which file do you want to analyze? 1

It reads input<N>.txt, prints the solved board, and writes output<N>.txt.

Tests

python -m unittest discover tests -v

Covers board construction, neighbor logic, the four hyper regions, step recording, full solves on every difficulty, and the JSON API contract (including malformed-input error paths).

Background

This project started as an AI assignment at NYU exploring constraint-satisfaction techniques on Hyper Sudoku. It has since been rewritten into a clean Python package with a real-time visual demo so the algorithm's behavior is easier to see, not just run.

License

MIT — feel free to use, learn from, and remix.