Optimization
Optimization puzzles are a type of logic puzzle involving the identification of a "most correct" solution among multiple correct solutions. While many optimization puzzles involve using the fewest number of "moves" to achieve a physical goal, some use other metrics, like time, number of inputs, or character count.
Background
While there is no defined origin for these types of puzzles, there are some well-known puzzles that date back as far as the 9th century. However, many optimization puzzles that we use today were invented much later, particularly those involving computer games and computer programming.
The River Crossing Puzzle
The first recorded instance of a river-crossing-based optimization puzzle comes from the 9th century Latin manuscript known as Propositiones ad Acuendos Juvenes, attributed to Alcuin of York. It details three different river crossings, two of which carry an amount of historical significance (due to their repeated use in puzzle books and culture).
The first is the "Wolf, Goat, and Cabbage" problem, wherein a farmer needs to transport one of each of the three things across a river one at a time, with the caveat that the wolf will eat the goat if left together, and the goat will eat the cabbage if left together. The goal is to get all three across in the fewest number of trips.
The second is the "Jealous Husbands" problem, wherein three married couples need to travel across a river via a boat that can only carry two people. However, the husbands will not allow their wives to be to be alone in the presence of another man without being present himself. As with the previous problem, the goal is to get all six across in the fewest number of trips.
Other river-crossing puzzles have been created since then, including the also-popular "Bridge and Torch" problem (first recorded in 1981 in the book Super Strategies For Puzzles and Games) where four people who walk at different paces need to cross a bridge with a weight limit of two people, while also making sure their one torch is present for every crossing.
Kolmogorov Complexity and Code Golf
[Insert History Here]
Puzzle Application
Optimization puzzles can take many forms within puzzle hunts, but are most often used either as subdivisions of larger puzzles, or as more involved, interactive elements. Even outside of hunts, however, they mostly fall into the categories of Movement Optimization or Strategy Optimization, with one prominent outlier in the form of Code Golf.
Movement Optimization
Examples: Sokoban, River Crossing, Text Adventures, Bacon Numbers
Puzzles requiring movement optimization obviously must require movement within a set space, but that set space can take many forms, including text-based adventure games and rooms full of boxes. However, one of the key parts of a movement optimization puzzle is the emphasis on using as few moves as possible. While the distinct moves used may sometimes come into play, or simply be constrained to one "perfect" solution, the most commonly used part in extraction is the number of moves necessary to achieve one's goal.
Strategy Optimization
Examples: Chess Puzzles, RPGs
Strategy optimization, unlike movement optimization, usually involves achieving a goal using the right moves, even if it's not the fastest solution. Suppose one's goal is to win a game of chess with as few piece losses as possible, or win a boss battle in a video game with minimal health loss. These cases are prime strategy optimization puzzles, and extraction for them is usually based either on the moves taken or simply rewarded upon completion of the task. While there is still significant overlap between strategy and movement optimization (particularly in puzzles where the fastest solution is also the best, strategically), those outside said overlap should be easily identifiable.
Code Golf
Code golf is unique within this type of puzzle, as rather than requiring a low number of moves or good strategy, it requires solver to write extremely short programs to perform relatively complicated task, instead measuring success based on the size of the program (either in character or bytes). While one could argue that this is functionally similar to movement optimization, but with an alternate metric, it should also be noted that code golf puzzles are not necessarily created with a "true solution" of the smallest possible program in mind. This is reflected in "official" code golf sites offering the use of many different programming languages and keeping leaderboards on all of them.
Strategy
Movement Optimization
[Insert Strategy Here]
Strategy Optimization
[Insert Strategy Here]
Code Golf
[Insert Strategy Here]
Notable Examples
- Unsafe (GPH2019)
- Research Center (GPH2019)
- Dragon (MIT2020)
