Computer Analysis of the UFO Puzzle

John Rausch
3119 N. Waynesville Rd.
Oregonia, OH 45054 USA

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 x 9 board that turned out to be much larger than necessary for reasonably difficult problems. Nob subsequently reduced the board to 5 x 5. Papers with 40 or more sample problems for the 5 x 5 board have been circulating in the puzzle collecting 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 x 5 board, exiting pieces and nonexiting pieces. Here, exiting pieces are labeled X, Y and Z and will be referred to as letter pieces. Nonexiting pieces are labeled 1 through 6 and will be 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 are 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 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 on 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 degrees and traveling towards another piece.

In the sample problem in figure 1, there are 3 possible moves for piece X. It can move down to 42 [1 step], down to 42 and right to 43 [2 steps] or down to 42, right to 43 and up to 23 [3 steps]. Piece 4 can move up to 32. These are the only possible first moves. Note that piece X passes through the center in move 1 of the solution, but is not removed until move 3 when it stops there.

Solution (3 Moves – 6 Steps)
  1. Move X down, right and up
  2. Move 1 down and right
  3. Move X down.

Start

First Move

Fig. 1. Sample Problem.

Problem Analysis

Analysis was done for all problems on the 5 x 5 board having 1 letter piece with 1 to 6 number pieces, 2 letter pieces with 1 to 5 number pieces and 3 letter pieces with 1 to 4 number pieces. Experiments with other board shapes and sizes were also done. One of the best was the 7 x 7 English Cross style peg solitaire board. Analysis was done for all problems on this solitaire board having 1 letter piece with 1 to 5 number pieces, 2 letter pieces with 1 to 4 number pieces and 3 letter pieces with 1 to 3 number pieces. Limited analysis was done for more complex problems on both boards.

The analysis programs are written in the PL/I programming language using the professional version of IBM’s PL/I compiler for the Windows operating system. This compiler generates very efficient machine language making it a good choice for compute intensive programs. The analysis was run on an IBM PC compatible with a 333mhz Pentium II processor. The longest running problem group (i.e., combinations of letter and number pieces) was group 3-3 for the solitaire board, taking 6 hours.

With problem groups having more letter or number pieces than those completely analyzed, the number of problems increases greatly. Individual problems become so complex (thousands of problems with more than 500 million positions!) that many take several minutes to analyze. For example, it takes several days to solve the problems for a single placement of pieces X, Y and Z in problem group 3-5 for either board. A faster processor would make a difference, but not enough. Furthermore, the problems in these groups tend to be so difficult that most humans would never solve them, and it seems a bit odd to use a computer to create problems that only a computer can solve. Some have been included in the sample problems shown in figures 10 and 11.

The basic analysis is done in two steps. The first step creates all of the problems for a problem group. To reduce the number of problems analyzed, rotations and reflections are eliminated. Additional measures further reduce the number of problems. All problems where no move is possible are omitted. Next some simple checks determine if any letter piece is stranded. A letter piece is stranded when it is impossible to maneuver it and another piece into squares opposite the center.

The second step attempts to solve all problems for a problem group. The solver program uses a modified depth-first search. It finds all minimum-move, minimum-step solutions.

For many problems, solutions exist where one or more of the number pieces are insignificant. That is, they do not move and do not stop other pieces from moving. In figure 2, problem 1a from problem group 1-2 is solved by simply moving piece X down. Piece 1, is insignificant. Excluding rotations and reflections, in this problem there are 12 insignificant placements for piece 1. If the insignificant piece in problem 1a is ignored, problem 1b from problem group 1-1 is identical.

Problem 2a has 2 solutions with 4 moves and 6 steps. One (2-D 1-R 4-LU X-RD) uses all of the number pieces. The other (3-L 2-D 4-LU X-RD) does not use piece 1. Therefore, if the insignificant piece in the second solution for problem 2a is ignored, problem 2b from problem group 1-4 is identical.

For the human solver, insignificant pieces generally make it easier to meet the primary objective of moving all of the letter pieces to the center, while making it harder to meet the secondary objective to do so in a specified minimum number of moves. A good collection of problems will always include some with insignificant pieces to enhance the human solver’s experience. However, because this analysis is dealing with optimum solutions, problems with insignificant pieces are not included in the solution counts in tables 1 and 2.

1a

1b

2a

2b

Fig. 2. Problems with insignificant number pieces

For all problems with solutions, the solver program writes text files of the solutions for visual browsing and a compact binary solution file for further analysis. Tables 1 and 2 show a summary of the solver program results.

Group1

Problems
Possible2

Problems
Analyzed3

Problems
With Solutions4

Max
Moves5

Max
Steps5
 

1-1

576

4

2

1

1

1-2

13,248

86

11

2

2

1-3

291,456

1,657

115

5

5

1-4

6,120,576

15,535

1,597

10

12

1-5

122,411,520

85,156

8,045

10

15

1-6

2,325,818,880

321,703

9,185

14

22
 

2-1

12,696

74

1

2

2

2-2

279,312

2,138

36

5

5

2-3

5,865,552

27,329

1,303

10

13

2-4

117,311,040

192,258

43,101

16

23

2-5

2,228,909,760

889,208

182,107

15

25
 

3-1

267,168

1,217

0

0

0

3-2

5,610,528

24,190

45

7

8

3-3

112,210,560

232,562

14,836

16

23

Table 1. 5 x 5 board.

1Letter and number piece count.
2Including rotations and reflections.
3Excluding rotations, reflections, problems with stranded letter pieces and problems with no moves.
4For all problems analyzed excluding solutions with insignificant pieces.
5For the best (minimum-move, minimum step) solutions in the problem group.

Group1

Problems
Possible2

Problems
Analyzed3

Problems
With Solutions4

Max
Moves5

Max
Steps5
 

1-1

1,024

9

3

0

0

1-2

31,744

254

20

2

2

1-3

952,320

6,128

274

4

5

1-4

27,617,280

76,171

4,194

11

12

1-5

773,283,840

570,210

43,915

16

20
 

2-1

30,752

233

3

2

2

2-2

922,560

8,483

97

6

6

2-3

26,754,240

142,847

4,206

10

12

2-4

749,118,720

1,355,196

138,297

17

24
 

3-1

892,800

5,225

1

3

3

3-2

25,891,200

134,247

253

9

10

3-3

724,953,600

1,718,986

66,784

18

26

Table 2. Solitaire board.

1Letter and number piece count.
2Including rotations and reflections.
3Excluding rotations, reflections, problems with stranded letter pieces and problems with no moves.
4For all problems analyzed excluding solutions with insignificant pieces.
5For the best (minimum-move, minimum step) solutions in the problem group.

Solution Analysis

Two additional programs were used to analyze the solutions. One is used to select and sort solutions meeting different criteria. For example, all problems having solutions with a minimum or maximum number of moves or steps can be selected. In addition to moves, steps and position of the pieces, it can use, as selection criteria, the sum of moves and steps, the difference between moves and steps, and moves as a percentage of steps.

The other program is used to analyze number-piece configurations. It processes all of the solutions from the solver program, ignoring letter piece placement. Rotations and reflections of the number-piece configurations are normalized into a single form and looked up a table where an occurrence count is kept. After all solutions have been processed, the table is sorted in ascending or descending sequence to determine the number-piece configurations with the least or most occurrences. The results of the analysis suggest some challenging new problems presented in the following sections.

Configurations with the Most Solvable Problems

When solutions with insignificant number pieces are included, there are several number-piece configurations where piece X can be placed in any vacant square except the center and all of the resulting problems are solvable. For the 5 x 5 board, there are 215 from problem group 1-5 and 3,239 from problem group 1-6. For the solitaire board, there is 1 from problem group 1-4 and 6 from problem group 1-5. These are the only analyzed problems groups, for either board, with number-piece configurations where all problems are solvable.

A few of the number-piece configurations with the most solvable problems where all number pieces are significant are shown in figures 3, 4 and 5. Remember that letter pieces never begin in the center. Answers are at the end of the article.

Configuration 1 in figure 3, from problem group 1-4, has 16 solvable problems where all number pieces are significant. This is the most of any analyzed problem group for the 5 x 5 board. Can you find the 4 problems where no solution is possible?

Configurations 2 and 3 in figure 3, from problem group 1-5, each have 15 solvable problems where all number pieces are significant. The other 4 problems for each configuration are solvable, but have insignificant number pieces. Can you find them?

Configuration 4 in figure 3, from problem group 1-6, has 13 solvable problems where all number pieces are significant. This is the most for this problem group. The other 6 problems are solvable, but have insignificant number pieces. Can you find them?

No. 1

No. 2

No. 3

No. 4

Fig. 3. Place X in any vacant square and solve the resulting problem.

Configurations 1, 2 and 3 in figure 4, from problem group 1-5, all have 23 solvable problems where all number pieces are significant. Each configuration also has 3 unsolvable problems and 2 solvable with insignificant number pieces. Can you find them?

No. 1

No. 2

No. 3

Fig. 4. Place X in any vacant square and solve the resulting problem.

Configuration 1 in figure 5, from problem group 2-5, has 146 solvable problems where all number pieces are significant. The other 25 problems are solvable, but have insignificant number pieces. Can you find them?

Configuration 2 in figure 5, from problem group 2-4, has 155 solvable problems where all number pieces are significant This is the most of any analyzed problem group for the 5 x 5 board. Only one of the remaining 35 problems is solvable, but has insignificant number pieces. Can you find it? Can you find the 34 unsolvable problems?

No. 1

No. 2

Fig. 5. Place pieces X and Y in any vacant squares and solve the resulting problem.

Configurations with One Solvable Problem

There are numerous number-piece configurations where only one letter piece placement is solvable. Finding the placement is challenging for the simplest problems. For more complex problems, it can be very difficult.

Figure 6 shows 4 of the 59 number-piece configurations from problem group 1-5 where only one placement of piece X is solvable and all number pieces are significant. Can you find it?

No. 1
3 Moves - 4 steps

No. 2
4 Moves - 5 steps

No. 3
8 Moves - 8 steps

No. 4
7 Moves - 13 steps

Fig. 6. Find the only placement for piece X with a solution.

Figure 7 shows 3 of the 458 number-piece configurations from problem group 1-5 where only one placement of piece X is solvable and all number pieces are significant. Can you find it?

No. 1
3 Moves - 6 Steps

No. 2
4 Moves - 5 Steps

No. 3
13 Moves - 18 Steps

Fig. 7. Find the only placement for piece X with a solution.

Figure 8 shows 4 of the 11 number-piece configurations from problem group 2-5 where only one possible placement for pieces X and Y is solvable and all number pieces are significant. Can you find it?

No. 1
4 Moves - 7 Steps

No. 2
5 Moves - 9 Steps

No. 3
8 Moves - 12 Steps

No. 4
9 Moves - 13 Steps

Fig. 8. Find the only placement for pieces X and Y with a solution.

Figure 9 shows 3 of the 55 number-piece configurations from problem group 2-4 where only one possible placement for pieces X and Y is solvable and all number pieces are significant. Can you find it?

No. 1
3 Moves – 5 Steps

No. 2
9 Moves – 9 Steps

No. 3
9 Moves – 16 Steps

Fig. 9. Find the only placement for pieces X and Y with a solution.

Conclusions

The UFO puzzle is one of the most interesting new puzzles of its type. While this article has shown that problems exist for the 5 ´ 5 and solitaire boards that are, perhaps, too difficult to be fun, the problems with around 5 to 7 moves seem to be fun and challenging for most people.

When released by Binary Arts, Lunar Lockout will have 40 problem cards, 1 exiting piece and 5 nonexiting pieces. Only 3 of the problems require 6 or more moves. Hiroshi Yamamoto selected the 40 problems from computer-produced solutions by Nob Yoshigahara. Harry Nelson served as problem tester and critic. Other members of the NOBrain Corps and the Har-e-brain Corps also tested problems. If Lunar Lockout is successful, at least one additional card set, including an additional exiting piece will follow.

Sample Problems

These sample problems vary from simple to extremely difficult. They are not all necessarily representative of those that are fun for most human solvers. Problems 5 to 8 in figure 11 are from problem groups with incomplete analysis.

No. 1 - 2 Moves No. 2 - 2 Moves No. 3 - 4 Moves No. 4 - 6 Moves

No. 5 - 10 Moves

No. 6 - 4 Moves

No. 7 - 16 Moves

No. 8 - 11 Moves

Fig. 10. Sample 5 x 5 problems.


No. 1 - 2 Moves No. 2 - 3 Moves No. 3 - 4 Moves

No. 4 - 5 Moves No. 5 - 7 Moves No. 6 - 18 Moves

No. 7 - 11 Moves No. 8 - 22 Moves

Fig. 11. Sample solitaire problems.

Answers

When a solution is followed by "(1 of n)", this indicates the solution is 1 of n similar solutions with the same number of moves and steps. Otherwise, it is the only solution with its number of moves and steps.
   
Fig. 3
  1. With X in 24, 25, 34 or 35, no solution exists
  2. With X in 13, 2 is insignificant - 3-LD 1-DR X-D
    With X in 31, 4 is insignificant - 2-RD 1-RD X-R
    With X in 32, 4 is insignificant - 2-RD 1-RD X-R
    With X in 34, 3 is insignificant - 1-D 5-UL 2-D X-L (1 of 2)
  3. With X in 12, 2 is insignificant - 1-DR 3-DL X-DR (1 of 3)
    With X in 22, 2 is insignificant - 1-DR 3-DL X-DR (1 of 3)
    With X in 25, 2 is insignificant - 1-D 5-U 3-L X-DL (1 of 2)
    With X in 43, 1 is insignificant - 3-DL X-U 4-R X-D (1 of 4)
  4. With X in 22, 2 is insignificant - 1-D 3-R 4-DL X-DR (1 of 5)
    With X in 23, 2 is insignificant - 1-D 3-R 5-RU 1-R X-D (1 of 3)
  5. With X in 41, 1 is insignificant - 3-R 4-DL 5-RUL 4-U X-RUR (1 of 3)
    With X in 53, 6 is insignificant - 1-D 4-L 3-DLU X-LUR (1 of 8)
    With X in 31, 1, 2, 5 and 6 are insignificant - 3-R X-R
    With X in 32, 1, 2, 5 and 6 are insignificant - 3-R X-R
   
Fig. 4
  1. With X in 31, 64 or 74, no solution exists
    With X in 23, 1 is insignificant - X-R 4-UL X-D
    With X in 24, pieces 1 and 2 are insignificant - 4-UL X-D
  2. With X in 31, 54 or 64, no solution exists
    With X in 23, 1 is insignificant - X-R 5-U 4-UL X-D (1 of 2)
    With X in 24, pieces 1 and 2 are insignificant - 5-U 4-UL X-D
  3. With X in 23, 24 or 34, no solution exists
    With X in 54, 5 is insignificant - 1-DR 4-U X-U (1 of 2)
    With X in 64, 5 is insignificant - 1-DR 4-U X-U (1 of 2)
   
Fig. 5
  1. With X and Y in 13-21, 13-22, 13-23, 13-41, 13-43, 13-51, 14-43, 15-43,
    21-22, 21-23, 21-43, 22-23, 22-43, 23-25, 23-43, 32-43, 34-43, 35-43,
    41-43, 41-51, 42-43, 43-44, 43-45, 43-52 and 43-54, one piece is insignificant.
  2. With X and Y in 32-34, 3 is insignificant - 1-RD X-R 4-U Y-L (1 of 4)
    With X and Y in 21-34, 21-35, 21-45, 23-24, 23-25, 23-34, 23-35, 24-25,
    24-34, 24-35, 24-43, 24-45, 24-53, 24-55, 25-34, 25-35, 25-43, 25-45,
    25-53, 31-45, 34-35, 34-41, 34-43, 34-45, 34-51, 34-53, 34-55, 35-41,
    35-43, 35-45, 35-51, 35-53, 35-54 and 45-51 no solution exists.
   
Fig. 6
  1. X in 31 : 2-R 4-LU X-R
  2. X in 41 : 1-D 3-L 4-U X-RU
  3. X in 14 : 2-R X-D 3-U 2-L 1-D 4-L 2-D X-L (1 of 4)
  4. X in 52 : 2-DR 1-RD 2-L 5-L 2-U 1-RUL X-URU (1 of 3)
   

 

Fig. 7
  1. X in 53 : 5-L 2-DR X-URD
  2. X in 42 : 2-R 4-LU 5-U X-R (1 of 6)
  3. X in 35 : 2-D 3-D X-LUR 2-ULU X-D 2-R X-U 4-RU X-D 2-D 4-R 2-U
    X-U    (1 of 16)
   
Fig. 8
  1. X in 41, Y in 53 : 3-U 4-DLU X-RU Y-U (1 of 2)
  2. X in 21, Y in 25 : 2-LD X-RD 3-U X-L Y-LDL (1 of 4)
  3. X in 51, Y in 54 : 1-D X-R 5-DLU 2-R 4-D Y-ULD 4-U X-U (1 of 4)
  4. X in 51, Y in 54 : 2-L 1-D X-R 5-DLU 2-R 4-D Y-ULD 4-U X-U (1 of 4)
   
Fig. 9
  1. X in 25, Y in 46 : 3-RU X-LD Y-L (1 of 2)
  2. X in 36, Y in 43 : 1-D 2-D 3-U X-L 2-U 4-U 2-R X-D Y-R (1 of 12)
  3. X in 53, Y in 55 : 1-D X-RU 4-URDL X-D 2-D X-RD 4-UR X-L Y-UL
   
Fig. 10
  1. 1-D X-UR
  2. 5-URURDL X-URURDL
  3. 1-D 2-R X-DRDL Y-DL
  4. 2-R 3-D X-L 5-URU 2-LDRUL X-URUL (1 of 2)
  5. 1-L X-D 3-L 4-L 3-U X-R 3-D 1-D 3-R X-UR
  6. 4-R 5-ULURD 4-LURDL X-DRDL
  7. Y-U 1-L 2-L 1-D X-R 1-UR X-D 3-R 1-DLU 4-U Y-LDL 1-D 2-D 1-RD
    Y-U X-RU     (1 of 8)
  8. Y-D 2-LURD Y-LUR 2-DLUR Y-D 1-LD Y-L X-DR 1-D Y-RU Z-RU (1 of 3)
 
Fig. 11
  1. 3-L X-LDL
  2. X-L 3-UR X-U
  3. 1-L 4-U 2-RU X-DR (1 of 2)
  4. 3-U Y-RD X-DRD 1-R Y-U
  5. 4-R 2-D 5-U 3-LD Y-D X-RD Z-DLD (1 of 4)
  6. 1-DR X-D 1-L 4-L 1-U X-RU 3-RDRU X-L 1-D Y-D X-RD 1-L 3-ULD Z-DL
    X-RU 3-DR X-D Y-D     (1 of 14)
  7. 4-L Y-LUR X-DLURDR 2-DLURD X-LULURD Z-LULUR 2-U 4-RU 2-D Z-D
    Y-LD     (1 OF 2)
  8. 2-DL 4-L X-D 4-R 3-RDLU 4-L 1-D 4-R 3-RD 2-RU 4-L 5-L 3-L 4-DLU
    2-RDL 4-D X-DRD 2-RUR 3-RU Y-RU X-UL Z-UL     (1 OF 15)

Acknowledgments

I would like to thank Harry Nelson for his helpful review of analysis results, his thorough review of this article and his valuable suggestions--analyzing number-piece configurations being, by far, the best one.