Procedural Puzzle Level Generation with Guaranteed Solvability

The problem: generated levels are often unsolvable or dull

Procedural generation is easy to get producing content and hard to get producing good content. For puzzle games the minimum bar is solvability: a level that cannot be finished is a bug that destroys trust. The naive approach, generate a random level and test it, works when most random levels are valid. For puzzles with interacting pieces the share of valid, interesting levels drops so low that generate-and-test becomes hopeless.

Even when a level is solvable, it may be trivial or frustrating. Designers hand-craft puzzle campaigns for this reason, which limits how much content small studios can ship.

What already exists and the gap

• Simon Tatham's Portable Puzzle Collection generates logic puzzles such as Net and Solo with a guaranteed unique solution, a good model of solver-backed generation for classic grid puzzles.
• PuzzleScript is an open engine for making tile puzzle games quickly, but its levels are written by hand.
• Academic work on Sokoban generation, including Monte Carlo Tree Search generators from the University of Minnesota and CNN-based solvability predictors, shows the problem is active research.

The gap is between them: a playable game that ships generated levels with a proof of solvability and a difficulty estimate that has actually been checked against people. Research papers often stop at the generator; commercial puzzle apps rarely generate at all.

What you build

• Player: plays a campaign of generated levels ordered by predicted difficulty, plus an endless mode.
• Designer: runs the generator with parameters, sees each level's solution, features and predicted difficulty, and curates a campaign.
• Researcher (you): logs every attempt, move and reset to compare prediction with reality.

The pipeline is: generate candidate, solve, compute features, predict difficulty, accept or reject, save with its seed and solution.

The technically interesting part

Two hard problems make this FYP-worthy.

The solver. State space search on puzzles explodes quickly. You will need a compact state encoding, a good heuristic for A* or IDA*, a transposition table, and deadlock detection (for block pushing, a block in a non-goal corner can never move again). Report how each optimisation reduces nodes expanded. If you try Z3 or another constraint solver, compare it honestly with your search.

Difficulty. Solution length correlates only weakly with how hard a puzzle feels. Better features include the number of plausible wrong moves, how deep the player must look ahead, and whether the key move goes against intuition (pushing a block away from its goal). Build a model from these features and validate it against real play data. This is the least common and most valuable part of work in this area.

How to evaluate it

• Generator: levels generated per minute, share rejected, and the distribution of solution lengths.
• Solver: nodes expanded and time per level with and without each optimisation.
• Difficulty model: at least 10 players, each playing a fixed set of levels; report the rank correlation between predicted difficulty and measured solve time and failure rate. A weak correlation honestly reported is still a legitimate finding.
• Fun check: a short questionnaire on which levels felt clever versus tedious.

Suggested plan

1. Weeks 1 to 3: choose one puzzle type, write the rules formally, build a playable prototype with hand-made levels.
2. Weeks 4 to 9: solver with optimisations, benchmarks.
3. Weeks 10 to 14: generator, feature extraction, first difficulty model.
4. Weeks 15 to 19: game integration, logging, campaign curation.
5. Weeks 20 to 24: player study, model refinement.
6. Weeks 25 to 28: report and demo.

Path to a product

Puzzle games with endless, verified content fit mobile and web well, with a daily puzzle mode as the retention hook and ads or a one-time unlock as the model. The generator and solver can also be packaged as a tool for other puzzle developers. Academically, a well-run player study can become a short paper at a games conference, which helps if you plan postgraduate study.

Scope warning

One puzzle type with simple rules. Every extra rule makes solving exponentially harder and will consume the year. Do not build level sharing, accounts or monetisation. Art can stay minimal.

Learn what you need on Sefism

• DSA roadmap : graphs, BFS, A* and hashing are the core of the solver.
• DSA cheat sheet : quick reference for search and priority queues.
• Red Blob Games : visual explanations of A* and heuristics.
• MIT 6.042J: Mathematics for Computer Science : state machines and invariants for proving properties of your rules.
• OpenIntro Statistics : correlation and significance for the player study.
• Machine learning roadmap : if you fit a regression model for difficulty.

Get help with this idea

The two traps here are rules that are too complex to solve and a difficulty model nobody tests. Tauseef can help you pick a puzzle type that fits the timeline, plan the solver work, and design the player study so the correlation you report is credible. If you are new here, create a free account first.

• Discuss this idea with a mentor
• Send a query to Tauseef
• Book a 1:1 session