Toads and Frogs
[1] Known for its simplicity and the elegance of its rules, Toads-and-Frogs is useful to illustrate the main concepts of combinatorial game theory.
[1] However, the general case of evaluating an arbitrary position is known to be NP-hard.
A one-player puzzle version of the game has also been considered.
Toads and Frogs is played on a 1 × n strip of squares.
At any time, each square is either empty or occupied by a single toad or frog.
Although the game may start at any configuration, it is customary to begin with toads occupying consecutive squares on the leftmost end and frogs occupying consecutive squares on the rightmost end of the strip.
Analogous rules apply for Right: on a turn, the Right player may move a frog left into a neighboring empty space, or hop a frog over a single toad into an empty square immediately to the toad's left.
Under the normal play rule conventional for combinatorial game theory, the first player to be unable to move on their turn loses.
represents a strip of four squares with a toad on the first one, and a frog on the last one.
In combinatorial game theory, a position can be described recursively in terms of its options, i.e. the positions that the Left player and the Right player can move to.
Winning Ways for your Mathematical Plays showed first numerous possible values.
For example, : In 1996, Jeff Erickson proved that for any dyadic rational number q (which are the only numbers that can arise in finite games), there exists a Toads-and-Frogs positions with value q.
, and formulated six conjectures on the values of other positions and the hardness of the game.
Jesse Hull proved conjecture 6 in 2000,[3] which states that determining the value of an arbitrary Toads-and-Frogs position is NP-hard.
It is possible for a game of Toads and Frogs to end early.
A one-player puzzle version of the Toads and Frogs game, published in 1883 by Édouard Lucas, asks for a sequence of moves beginning in the standard starting position that lasts as long as possible, ending with all of the toads on the right and all of the frogs on the left.
The moves are not required to alternate between toads and frogs.
