Fifteen Puzzle
The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3×3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4×4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces. The object of the puzzle is to place the tiles in order (see diagram) by making sliding moves that use the empty space.
The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.
Read more about Fifteen Puzzle: Solvability, History, Miscellaneous
Famous quotes containing the words fifteen and/or puzzle:
“You watched and you saw what happened and in the accumulation of episodes you saw the pattern: Daddy ruled the roost, called the shots, made the money, made the decisions, so you signed up on his side, and fifteen years later when the women’s movement came along with its incendiary manifestos telling you to avoid marriage and motherhood, it was as if somebody put a match to a pile of dry kindling.”
—Anne Taylor Fleming (20th century)
“What are you now? If we could touch one another,
if these our separate entities could come to grips,
clenched like a Chinese puzzle . . . yesterday
I stood in a crowded street that was live with people,
and no one spoke a word, and the morning shone.
Everyone silent, moving. . . . Take my hand. Speak to me.”
—Muriel Rukeyser (1913–1980)