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 (the Wolf, Goat, and Cabbage problem and the Jealous Husbands problem) carry an amount of historical significance (due to their repeated use in puzzle books and culture).

Puzzle Contests

Periodicals and magazines often ran competitions where the goal was to optimize for some particular metric. For example, in 1910, the New York Herald ran a contest asking readers to come up with as many words as possible from a Bible passage. They also featured as games in early NPL Conventions, contests in dedicated puzzle magazines such as Games Magazine, and some puzzle hunts and events. For instance, early iterations of Eric's Puzzle Party included many optimization puzzles, and logic puzzle optimization contests also exist.

Kolmogorov Complexity and Code Golf

TO DO

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, The Kevin Bacon Game

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

TO DO

Strategy Optimization

TO DO

Code Golf

TO DO

Notable Examples

• Unsafe (GPH 2019) (web)
• Research Center (GPH 2019) (web)
• Dragon (MITMH 2020) (web)

See Also

• Code Golf
• Propositiones ad Acuendos Juvenes (PDF)
• Optimization logic puzzles