1
Computer Analysis of the UFO Puzzle
John Rausch
3119 N. Waynesville Rd.
Oregonia, OH 45054 USA
john@johnrausch.com
Introduction
UFO was created by Hiroshi Yamamoto and presented by Nob Yoshigahara in February
1998 at the Third Gathering for Gardner in Atlanta, Georgia. The handout had sample
problems using a 9 × 9 board that turned out to be much larger than necessary for rea-
sonably difficult problems. Nob subsequently reduced the board to 5 × 5. Papers with 40
or more sample problems for the 5 × 5 board have been circulating in the puzzle collect-
ing community since the presentation. Binary Arts will introduce a commercial version
called Lunar Lockout in early 2000.
Description of the UFO Puzzle
The standard UFO puzzle uses a 5 × 5 board, exiting pieces and nonexiting pieces.
Exiting pieces are labeled X, Y and Z and referred to as letter pieces. Nonexiting pieces
are labeled 1 through 6 and referred to as number pieces.
Thousands of problems are possible by placing the pieces on the board in different
configurations. The primary objective is to move all of the letter pieces to the center. A
secondary objective is to do so in a specified minimum number of moves. Letter pieces
never begin in the center and must be removed whenever they stop there. Number pieces
can begin or stop in the center, but are never removed.
A move, which is the same for letter and number pieces, is made in steps. For each step, a
piece travels left, right, up or down towards another piece, stopping in the square next to
the piece moved towards. Travel is stopped only by another piece and must always be
towards another piece. After stopping, there are 3 possible outcomes:
(1) The move ends if a letter piece stops in the center. It must be removed from the board
immediately and if it is the last, or only, letter piece, the problem has been solved.
However, a letter piece may travel through the center.
(2) The move may end and another piece may move.
(3) The move may continue by turning the piece 90° and traveling towards another piece