I’m always delighted when I encounter a good puzzle in a game.
Whether it’s finding the right use for a bizarre tool in an adventure game, or figuring out the optimal way to spend cash or resources in a board game, puzzles are a great way to engage players and are central to the work of many game designers.
While I’m a hobbyist, earlier this year, I published a puzzle game for iPhone titled Red Knight Chess Puzzle.
A variant of Solitaire Chess, the objective is to eliminate all chess pieces from the board by capturing one piece per move until only one remains. It’s a simple but fun brain teaser.
Aside from the game engine, this project presented two interesting challenges:
- Creating lots of puzzles.
- Choosing which ones would end up in the game.
Good puzzles should be:
- Not too easy,
- Not repetitive,
- Complex enough, but in a good way
And since all kinds of puzzles share some general characteristics, I decided to write about the process of puzzle creation.
What to Expect
After a very short intro on how my game came to be, and how my puzzles work.
After a very short introduction on how my game came to be and how my puzzles work, this article will cover how to generate puzzles, solve them, and identify what makes a great puzzle to play.
Examples will be taken from my game since I developed tools to analyze them, but this method would work for all kinds of puzzles.
A Little Bit of Backstory: How This Game Came to Be
Amusingly, this started with me playing with chatGPT.
My son wanted to know if it could help create a game, so I tried it out with the simplest game request I could think of: a text adventure in Python. To my surprise, I was quickly able to put together something with very little effort.
Remembering my love of Choose Your Own Adventure books as a kid, this led to the more ambitious project of creating a full text adventure game. I still have a few them, including another edition of this one :
But since text and image generation are not yet exact sciences, I invested quite a bit of time and energy in creating a fun story with some puzzles to solve along the way.
Not surprisingly, even taking into account Hofstader’s law, the whole thing took a bit longer than I anticipated.
It always takes longer than you expect, even when you take into account Hofstadter’s Law.
– Hofstadter’s law
The game (still unfinished) is about a girl investigating a theft at her school chess club. And the first clue you find is… drum roll… A red knight chess piece!
initially included some real chess puzzles to be solved, but I also thought about whimsical ones where the Red Knight would be of some use. This is where my solitaire chess variant came into being.
The full game was far from completion, but my puzzle interface was working, so I decided to extract that part and make a full game out of it. And here we are today.
Now, to the puzzles!
The puzzles
In order to explain how to create them, let’s have a look at puzzles from the game.
The Goal: Capture all the pieces on the board. (Until only one remain)
- Each turn you need to capture a piece.
- Pieces move like chess pieces.
- Pawns capture diagonally (Blue pawns can move up or down the board)
Here is the simplest puzzle ever: One move to win by capturing the pawn with the knight.
No big challenge here… But it gets the point across.
There are also more complex puzzles involving different colour of pieces. This adds interesting constraints and forces you to think differently about the board.
For example, White pieces can capture Black pieces, and vice versa.
There is also a Red piece that capture anything, and combinations of all of the above create interesting dynamics.
But let’s keep things simple and get back to the question of puzzle creation.
How to generate puzzles?
Generating puzzles can seem a bit tricky and time-consuming at first, until you realize that puzzles can easily be created by thinking about them in reverse.
Consider the previously shown puzzle. If we reverse the arrow of time, what do we have?
- A knight, moving out of the way,
- A pawn magically appearing beneath it.
That’s it! This is the secret of easily creating a puzzle!
- Move a piece to a spot it could have moved from.
- Choose a random piece to be put in its place.
- Repeat this process a number of times to achieve the desired puzzle length.
Starting from the end makes puzzle generation fast and ensures that a solution exists.
If you want to add constraints to your puzzle, you can select where the pieces come from and which pieces to add. For example, you could make the moves as distant as possible or only use knights and bishops.
Now the questions are…
- It it a good puzzle?
- Is the puzzle hard or easy?
- Is it fun ?
That is where things get a bit more involved (and interesting!)
Is There a Unique Solution?
Generating puzzles in reverse guarantees that one solution exists, but it does not guarantee that other solutions do not!
Let’s take two introductory puzzles to illustrate this.
In both cases, the number of possible moves is limited, but there is an important difference.
If you consider only legal moves capturing a piece, in puzzle #3, you cannot make a mistake. Either the rook or the bishop captures the pawn; those are the only two choices, and they both lead to a correct solution.
In the puzzle #6, however, if you capture the knight with the top pawn, you are stuck and will need to restart the puzzle.
It is okay to present puzzle #3 to a player learning the game, but if all puzzles were like that, the game would be quite boring.
To make puzzles more interesting and give players a sense of accomplishment, you need to limit the number of possible solutions (ideally to one).
To achieve this, you need to find a way to solve each puzzle in all possible ways.
So before exploring more detailed ways to adjust puzzle fun or difficulty, let me introduce something that will be useful:
Automating and Visualizing Puzzle Solutions
Solving a puzzle from a computer programming point of view is mostly viewed as a search problem.
Think of the problem as a tree. The root is the initial state, and each valid move is a branch from this root. From there, other branches spread until you reach a solution or a dead-end.
By exploring the tree we can:
- Find one solution (stopping as soon as we find it).
- Find all solutions, by systematically exploring all the branches.
In our case, the process is made easier by the nature of our problem. Since we only consider moves that capture other pieces, there is no way to go back to a previous state and no possibility of going in circles.
For the two preceding puzzles, the solution trees are small but illustrate our point beautifully:
We see that the first problem only ends up in green leafs, identifying valid solutions. For the other puzzle, one branch leads to a solution, the other to a dead-end (In red)…
The trees were generated by a program that I wrote, a variation of a search algorithm I was using to find solutions to my puzzles.
I think the visualization helps understand the complexity of simple puzzles in a beautiful way, which is why I’m introducing them from the start.
What Makes a Puzzle More or Less Difficult?
Longer puzzles are more difficult
The simplest difficulty knob you can adjust is the number of moves needed to solve a puzzle. In our solution tree, this translates to increasing the tree’s height. Everything else being equal, it will require the player to plan more moves ahead.
The simplest example I can think of is two very similar puzzles involving a rook and some pawns.
The first has one pawn to capture, while the second has three.
Both puzzles are almost identical, with only one possible move at each step. However, simply because you have more pieces and more steps to consider, it forces you to think about it longer.
This is an oversimplification, as we can see from the linear solution tree, but I think it’s a good illustration nonetheless of the most obvious measure of difficulty in puzzle design.
Number of choices you have
The last example naturally raises a question about the number of move choices.
Besides the depth or the possibility of entering a false path in our solution tree, one aspect of puzzle difficulty is simply the number of branches there are to explore.
The last example was about solution trees with no branching, an extreme case that drives home the point of how simpler puzzles offer fewer moves to choose from. Offering more choices quickly adds complexity and requires more thinking to solve the problem.
Here’s an example of a puzzle with much more branching while still being easy. (Try solving it before looking at the solution.)
Here the pieces are a queen, a bishop, and two knights.
Looking at the graph of the solution, we see that most paths lead to a correct solution, but you still had to think about it more than in the previous case.
The Length of the Branches Leading to Dead-Ends
Do the wrong moves immediately reveal themselves, or do you only discover your error at the end?
If the solution were a maze, this would be the equivalent of:
Making a wrong turn and immediately seeing a wall.
VS
Having to walk around a few corners before encountering the wall.
Up until now, I was careful to present you with puzzles with only short-sighted dead-ends, but this is not always the case!
In the solution trees, I chose to identify the states that can only lead to a dead-end by coloring them pink. In these states, you still have valid moves, but none of them will lead to a valid solution (the green leaf).
Here is an example of a puzzle with few states but a long pink branch. (Once again, try solving the puzzle before looking at the solution!)
In the solution tree, there is only one way toward the solution, but a maze of dead-ends awaits you if you make the wrong move first.
The number of branches in this puzzle is low, so it is easy to spot the trap, but those long branches make for more difficult puzzles because you have to evaluate many more states before realizing you have no good options left.
The Number of Dead-Ends
A final metric we will look at is simply the number of dead-ends in a solution tree.
Even if you have a large branch count, if all the branches converge to valid solutions, this will not make for a difficult puzzle.
A large number of dead-ends means there are lots of bad moves to consider before arriving at the solution.
And because generated longer puzzles have a higher chance of offering a few variations on the final solution (think two pieces in the end that can capture each other), I personally consider the ratio of valid solutions to dead-ends in my puzzles.
Just for fun, here is a small puzzle with a lot of dead-ends.
With the solution graph:
Similarly, a somewhat correlated metric would be the number of pink nodes in the tree (the number of nodes that cannot lead to a solution), since it represents the fraction of the search space where you won’t be able to reach a solution from.
The Exponential Nature of Solution Trees
If you wonder why the puzzles I presented here are all simple (aside from the clearer explanation they provide for each element), consider this: as your puzzle grows in complexity, the solution tree representation quickly explodes in scale.
For a simple problem, the graph stays small:
But even for a medium problem, the graph can grow rapidly:
Or even larger….
I did not graph the most complex problems as the time and space it takes to generate the bigger trees ends up being prohibitive in terms of computer resources.
The exponential nature of such problems is why computer search usually relies on some tricks to avoid exploring everything or to avoid keeping everything in memory. Extremely large trees, such as ones you would use to explore a complex games, can only be explored in parts. If it were not the case, a chess-playing program could simply explore the whole tree and come up with the best possible move every time.
If this were the case, we would say that chess is now considered a ‘solved’ problem. (It’s not!)
The good thing is, for our case, we can explore the whole solution tree without drawing everything up, simply keeping the count of dead-ends, found solutions, and other desired metrics. No need to check the tree yourself; the counts are enough for giving the puzzle a quick difficulty rating.
It’s not the whole picture, but we are getting close!
Puzzle generation with increasing difficulty
In a game, puzzles are usually presented in an order of increasing difficulty. This allows players to get into the logic of the game and find their groove before tackling real brain-twister problems.
This means you need to be able to tweak the difficulty of a puzzle at generation time, so you don’t have to reorder everything afterward.
If we consider the previous points, the knobs to generate more or less difficult puzzles are the following:
- Puzzle Depth: The number of moves required to solve the puzzle.
- Branching Complexity: The number of states in the solution graph.
- Number of Solutions: Fewer solutions typically mean a more challenging puzzle.
- Number of Dead-ends: States that lead to a dead-end add complexity and difficulty.
How I Generated my Puzzles
To generate puzzles for Red Knight Chess Puzzle, I wrote a program that would generate puzzles according to the following parameters:
- Type of puzzle: In my case, specifying the colors for the chess pieces to be used.
- Size of the chessboard: A bigger board allows more variety for the puzzles.
- Depth of the puzzle: Number of moves needed to solve the puzzle.
The program would then solve the puzzle and count the number of solutions, dead-ends, and states on the path to the dead-ends.
For additional difficulty control, I generated a large number of puzzles and kept the puzzles with the fewest solutions but the most nodes on the path to the dead-end. Varying the number of puzzle generated directly impacted their difficulty level.
The best of 10 or 1000 puzzles competing for difficulty will not be the same!
This approach has the downside of taking a bit longer, but I found this allowed for creating a smooth difficulty gradient without manual reordering.
In the end, to generate puzzles with a full gradient of difficulty, I simply generated batch of 20 puzzles, each batch parameters incrementing the board size, the depth of the puzzle and/or the number of puzzles to generate before picking the best one.
Puzzle specific consideration
Aside from the previous general considerations, some aspects of fun and difficulty are puzzle-specific.
For example, I found that solutions involving the same piece capturing all others, one after the other, were boring. This was especially true for such solution involving a rook. The linearity of the moves was often immediately obvious, making the whole thing more tedious than entertaining.
So the nature of the puzzle will impose some constraints on what makes a puzzle fun. But to identify them, you will need to play the puzzles yourself and think about it while playing.
Once you identify those constraints, you can usually monitor for them at generation time and simply ignore the puzzles that don’t make the cut.
The Importance of Trying Your Puzzles
While automated generation can handle much of the heavy lifting, human insight is invaluable for fine-tuning.
Once the generation is good enough, most puzzles should be mostly balanced. But I would feel a bit uneasy at throwing puzzles at others without making sure they are fun first…
After generating puzzles, I played through them, keeping the ones that were enjoyable and challenging, and discarding those that were not.
Further Explorations
One area I am still exploring is the correlation between solution graphs and puzzle enjoyment.
This mean rating generated puzzle by hand for fun and difficulty, and then trying to correlate those rating with solution graph metrics to see if we can refine the generating algorithm.
This however pose some difficulty, since doing this by myself has a huge bias on what is considered easy or hard and fun or boring. And since the more you play a game, the more skilled you get. This makes for a dynamic evaluation problem!
The beauty however is that this approach can be adapted to various types of puzzles. This means that I will have something to play with when I decide to make another puzzle game in the future!
Conclusion
In this overview of puzzle creation I hope to have highlighted the balance between automation and human insight in crafting engaging puzzles. By focusing on key metrics and continuously refining the process, I think we can create puzzles that are both challenging and fun!
I encourage you to think about the types of puzzles you enjoy and try designing a few yourself.
And If you would like to try for yourself the puzzles in this article, don’t hesitate to try Red Knight Chess Puzzle !
The first 360 puzzles are free, so feel free to explore and reflect about puzzle generation while having fun.
Happy puzzling!