Procedural Level Generation with Guaranteed Solvability
Generate puzzle levels procedurally and prove each one is solvable before it reaches the player, using a solver rather than generate and test. Constraint solving and search applied to a problem with a clear success criterion.
Advanced
Needs a team, real planning, and a supervisor who knows the area.1 semester, 2 to 3 students
5 to ship
3 optional extrasSuggested stack
What you should ship
- A puzzle game with formally specified rules and win conditions
- A generator producing levels with tunable parameters
- A solver that verifies solvability and returns the optimal solution length
- Difficulty estimation from solution length, branching factor and required lookahead
- Player testing with at least 10 participants comparing perceived difficulty against your estimate
If you have time left
- Generating levels that require a specific technique the player has not yet practised
- Difficulty adapting to the individual player's demonstrated skill
- Generation guided by the solver rather than filtered by it
The problem
Procedural generation is easy to make produce content and hard to make produce good content. For puzzle games the minimum bar is solvability, and generate and test becomes hopeless once the proportion of valid levels falls low enough.
What you build
A rule specified puzzle, a generator, a solver that verifies and measures, and a difficulty model validated against real players.
Why the solver is the interesting part
It turns generation from hoping into guaranteeing. It also gives you the optimal solution, which is the input to any honest difficulty estimate. Whether you implement search yourself or use a constraint solver, this component is where the computer science is.
The genuinely hard problem
Difficulty. Solution length correlates weakly with how hard a puzzle feels. Required lookahead, the number of plausible wrong paths and whether the key move is counter-intuitive matter more. Building a model and validating it against actual player performance is the most valuable and least common part of work in this area.
The evaluation
Ten players, real levels, measured solve times and failure rates against your predicted difficulty. Report the correlation, including if it is poor, because a negative result honestly reported is a legitimate finding.
Scope warning
One puzzle type with simple rules. Rule complexity makes solving exponentially harder and will consume the semester.
Ideas and guidance, not finished projects
These are project ideas and scoping guidance, published free for students to use as a starting point. I do not build, write, or sell final-year projects, and I do not complete coursework for anyone. Take an idea, make it yours, and build it.
Not sure this one fits you?
I help students pick an idea that matches their skills and their deadline, then scope it down until it is finishable. Guidance only, never done for you.
Stuck on something specific?
Writing only gets you so far. If you want an answer to your situation rather than the general case, book a session and we will work through it together. Every session is free; a few slots open each week.
Follow along
New writing, resources and project ideas land here first.