History of Puzzles: Six Classic Puzzles and Where They Came From

Many of the puzzles people still solve today have a traceable history: the eight queens puzzle was first proposed in 1848 ^[1], the sliding 15-puzzle is said to date back to the 1870s ^[4], and the classic coin weighing puzzle first appeared in 1945 ^[6]. This article follows six classic puzzle types from their first appearance to the questions mathematicians are still answering about them, using only what peer-reviewed papers report.

Each type started as a small, clear question. What makes them worth a history is what happened next: people generalised them, argued about the best solutions, and eventually handed some of them to computers.

Where does the eight queens puzzle come from?

The eight queens puzzle asks you to place eight queens on a chessboard so that no two of them share a row, a column or a diagonal ^[1]. It was first proposed by M. Bezzel in 1848, and in 1869 it was generalised to the n queens problem, which asks for n queens on a board of n rows and n columns ^[1].

The general version has a clean answer to the first question anyone asks. A solution exists for a board of side 1 and for every board of side 4 or more ^[1]. That simple statement hides a large body of work: hundreds of papers have been written on the problem and its variations, including versions on boards of other shapes ^[1].

One kind of variation adds pawns, which block a queen's line of movement ^{[1] [2]}. In the n + k queens problem, k pawns and n + k queens go on a board of side n, and any two queens on the same line must have at least one pawn between them ^[2]. For 1, 2 or 3 pawns, a solution exists on every board whose side is at least 5 more than the number of pawns ^[2]. A 2016 paper showed that with enough pawns, roughly a quarter of the board can be filled with queens, and asked how few pawns that takes ^[1].

The same idea has been carried to other pieces. A 2018 paper replaced the queens with the dragon king, a piece from the board game shogi, which moves any distance along a row or column or one square diagonally ^[2]. That paper showed that the n + k dragon kings problem has a solution whenever the board's side is at least 5 more than the number of pawns ^[2].

Board puzzles also turned into questions about distance. On an otherwise empty board, a single rook or queen can reach any square in two moves ^[3]. A 2021 paper asked how many pawns are needed so that some trips across the board take more moves than that, and it described the board as a network of squares joined by legal moves ^[3].

How did the 15-puzzle become a computing problem?

The 15-puzzle is a square tray of 15 numbered tiles and one empty space, and you slide tiles into the space until they are in order ^[4]. Its history is said to date back to the 1870s ^[4]. The same puzzle exists in other sizes: the 8-puzzle uses a 3 by 3 tray, and the general version on a board of side n is called the (n² − 1)-puzzle ^[4].

For small trays, the move counts are known. Using brute force, every start of the 3-puzzle can be solved in 6 moves or fewer, the 8-puzzle in 31, and the 15-puzzle in 80 ^[4]. For trays of any size, though, finding the fewest moves was proved to be NP-hard ^[4].

For a tray in a random order, the average number of moves matters more to a player than the rare worst case ^[4]. A 2015 paper analysed the greedy method, which puts the tiles in place one at a time, row by row and column by column ^[4]. It showed that the method needs about 8/3 n³ moves on average for a board of side n, and it checked that figure on 10,000 random puzzles for each board size from 4 to 200 ^[4].

What did a 1918 number fact start?

Some puzzles begin with a surprising sum. Add up the squares of the whole numbers from 1 to 24 and you get exactly 70 squared, and since the work of Watson in 1918 it has been known that this is the only case apart from the trivial one, 1 = 1 ^[5].

The sum suggests a puzzle: can the squares of side 1 to 24 be fitted together to tile a 70 by 70 square exactly ^[5]? The puzzle was popularised by Martin Gardner in magazine articles, and readers sent in their best attempts to cover as much of the big square as possible ^[5]. Twenty-seven readers fitted every square except the 7 by 7 one ^[5].

The final answer took computers. Extensive computer searches have proved that no packing of the 24 squares can waste less space than that best attempt ^[5]. That search modelled the packing as a constraint-satisfaction problem ^[5].

Where did weighing puzzles come from?

The simplest coin puzzle goes like this: you have a pile of identical-looking coins, one of which is an odd coin lighter than the rest, and a balance scale ^[6]. The question is the smallest number of weighings that is sure to find the odd coin ^[6]. This puzzle first appeared in 1945, and many generalisations have followed ^[6].

Later versions let the odd coin change its behaviour. In 2015 a chameleon coin was introduced, which can choose at each weighing whether to act like a real coin or a light odd coin ^[6]. A chameleon can never be found among real coins, because it can always pretend to be real ^[6]. Later work introduced the alternator coin, which switches its behaviour by a fixed rule each time it is put on the scale, and unlike the chameleon it can always be found ^[6].

A 2025 paper took the idea further, with coins that switch between being lighter and heavier than a real coin ^[6]. For the coin that switches between light and heavy, when its starting state is known, the paper showed that w weighings can handle up to 3 to the power w coins ^[6].

Who turned truth and lies into puzzles?

In puzzles of truth-tellers and liars, every person always tells the truth or always lies, and you must work out who is who from what they say ^[7]. Puzzles of this kind, in their classic form, were introduced by Smullyan, and many books and papers have since popularised them under other names ^[7].

Later papers sorted the speakers more finely. Strong truth-tellers say only true statements and strong liars say only false ones, and it has been proved that when every statement simply says that someone is a truth-teller or a liar, a puzzle with only these two types never has a unique solution without extra information, such as the number of truth-tellers ^[7]. Other papers added further types of speaker, such as people who can say both true and false statements ^[7].

A 2020 paper added a third type whose statements always contradict themselves ^[7]. With the same simple kind of statement, it showed that puzzles with this third type can have a unique solution with no extra information at all ^[7].

How did colour cubes join the story?

Paint each face of a cube a different colour, using six colours, and ask how many different cubes you can make ^[8]. Turning a cube does not count as a new one, and the answer is 30 ^[8]. One way to see it: fix the bottom colour, choose one of 5 colours for the top, fix one side to stop rotations, and the last 3 sides can be ordered in 6 ways, giving 5 × 6 = 30 ^[8].

John Conway arranged the 30 cubes in a 6 by 6 table with the main diagonal left empty, and he placed cubes that are mirror images of one another in chosen positions ^[8]. A 2018 paper by Siegrist used that table to show that each of the 30 cubes can be copied at double size from 8 of the others ^[8]. The copy must obey the domino condition, meaning that faces touching inside the big cube share a colour, and the 8 cubes can be arranged in two different ways ^[8].

What do these puzzle histories have in common?

Each type began with a question small enough to state in one sentence, from eight queens in 1848 to a light coin in 1945 ^{[1] [6]}. Each grew by generalising: from 8 queens to n queens with pawns ^{[1] [2]}, from the 15-puzzle to trays of any size ^[4], and from truth-tellers and liars to new types of speaker ^[7]. Some were finally settled by computer search, such as the best packing of the 70 by 70 square ^[5], and brute force gives the move counts for small sliding trays ^[4].

For a solver, the lesson is encouraging: state the rule exactly, test every case, and check whether a second answer is hiding.

Want to try puzzles in the same spirit?

The three riddles below draw on the same ideas: weighing with a balance, picturing a cube in your head, and testing every case until only one answer is left.