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.

Strategy

Movement Optimization

[Insert Strategy Here]

Strategy Optimization

[Insert Strategy Here]

Code Golf/Programming Optimization

[Insert Strategy Here]

Notable Examples

• Unsafe (GPH2019)
• Research Center (GPH2019)
• Dragon (MIT2020)