Game Playing: The Sliding Tiles Puzzle

---

The Game Setup

Animation of puzzle being solved. Return with the browser's Back button) You can download this zip file for this project

To keep things simple we'll work with a 3x3 game with tiles numbered 1 to 8. Here is an example of a game in its final (solved) configuration.

1	2	3
4	5	6
7	8

The Representation of a Board configuration

As we'll see, during the search for a solution many thousands of partial solutions may be floating around in our workspace. It's important to keep these partial solutions as small as we can. A simple 9 character string does nicely. Here is an example to show how a 3x3 board might look.

42_713856

Every configuration string is 9 (3^2) characters long. Each digit (1-8) is uniquely present and the underscore is used to indicate the empty slot. The string is simply ordered by row and then by column. The two goal solutions is 12345678_.

A Class for Helper Functions

We will build some small programs that both create and solve 3x3 configurations. To get better code reuse the common elements have been gathered into a class containing common function and attributes. Let's look at these now.

 1 # tiles.py
 2 #
 3 import sys
 4
 5 class TileGame :
 6     def __init__ (self, sampleBoard) :
 7         self.legalMoves = legalMoves3
 8         self.goal       = "12345678_"
 9         self.dim        = 3
10         self.makeManhatten()
11

The class name is TileGame and when an instance is created a sample board is passed to solve. A table is created with the Manhatten distances between all squares. The legal moves into each square from its neighbors is attached to the game instance. The dimension dim is always 3x3 for this version of the project but can be expanded to a 4x4 game.

Now let's create a game with a start board and then examine the attributes set up.

$ python
>>> import tiles
>>> startBoard = "4321_5678"
>>> game = tiles.TileGame(startBoard)
>>> game.goal
'12345678_'
>>> game.dim
3

Let's look at the methods (functions) within TileGame.

12     def getMoves(self, board) :
13         empty = board.find('_')
14         return empty, self.legalMoves[empty]

>>> game.getMoves(startBoard)
(4, (1, 3, 5, 7))

The method getMoves uses the legalMoves table to return a tuple with the slot that is empty and the slots from which a tile may be slid into it.

16     def makeMove(self, board, empty, mov) :
17         lbrd = list(board)
18         lbrd[empty],lbrd[mov] = lbrd[mov],lbrd[empty]
19         return "".join(lbrd)
20

>>> game.makeMove("4321_5678", 4, 7)
'4321756_8'

The method makeMove creates a new board by moving a tile to the empty square. In line 17 the old board is made into a list that can be modified. Line 18 the contents are exchanged and in line 19 temporary list is converted back to a string.

21     def futureCost(self, board) :
22         # estimate future cost by sum of tile displacements
23         future = 0
24         for sq in range(self.dim*self.dim):
25             occupant = board[sq]
26             if occupant != '_' :
27                 shouldbe = self.goal.find(occupant)
28                 future  += self.manTable[(sq,shouldbe)]
29         return future
30

The method futureCost uses the "manhatten distance" which is distance between two points when you are confined in moving only along the x or y axis as in the streets of Manhatten. futureCost returns the sum of these distances for each tile to its proper locatino in the goal.

31     def makeManhatten(self) :
32         self.manTable = {}; Dim = self.dim
33         for aa in range(Dim*Dim) :
34             for bb in range(Dim*Dim) :
35                 arow = aa//Dim; acol=aa%Dim
36                 brow = bb//Dim; bcol=bb%Dim
37                 self.manTable[(aa,bb)] = abs(arow-brow)+abs(acol-bcol)
38

The manTable dictionary is set up when the game instance is initialized. Obviously, it makes a difference whether the game is 3x3 or 4x4. The keys in the dictionary are tuples of 2 two slot positions. The values the distance between them. Notice in line 37 the use of the abs function which to guarentee that "There are no Negative Distances".

Finally, a simple utility method to print a board to the screen. The tiles are laid out in rows with even spacing between columns (line 49).

39     def printBoard(self, board, mesg="", sep="\f") :
40         if sep  : print(sep)
41         if mesg : print(mesg)
42         expand = ["%02s"%x for x in board]
43         rows = [0]*self.dim
44         for i in range(self.dim) :
45             rows[i] = "".join(expand[self.dim*i:self.dim*(i+1)])
46         print("\n".join(rows))
47

>>> game.printBoard("4321_5678", "At move zero")

At move zero
 4 3 2
 1 _ 5
 6 7 8

The slots are numbered to align with the Python zero-based array and string indexing.

0	1	2
3	4	5
6	7	8

Also in tiles.py are a couple of extras including tables of legal moves for both the 3x3 and 4x4 games and a function to trap errors and exit with error

48 def scream(error) :
49     sys.stderr.write("Error: %s\n" % error)
50     sys.stdout.write("Error: %s\n" % error)
51     sys.exit(1)
52
53 legalMoves3 = ( # for a 3x3 board
54    (1,3     ),  # these can slide into square 0
55    (0,4,2),     # these can slide into square 1
56    (1,5),       # these can slide into square 2
57    (0,4,6),     # these can slide into square 3
58    (1,3,5,7),   # these can slide into square 4
59    (2,4,8),     # these can slide into square 5
60    (3,7),       # these can slide into square 6
61    (4,6,8),     # these can slide into square 7
62    (5,7))       # these can slide into square 8
63

64 legalMoves4 = ( # for a 4x4 board
65    (1,4     ),  # these can slide into square  0
66    (0,5,2),     # these can slide into square  1
67    (1,6,7),     # these can slide into square  2
68    (2,7),       # these can slide into square  3
69    (0,5,8),     # these can slide into square  4
70    (1,4,6,9),   # these can slide into square  5
71    (2,5,7,10),  # these can slide into square  6
72    (3,6,11),    # these can slide into square  7
73    (4,9,12),    # these can slide into square  8
74    (5,8,10,13), # these can slide into square  9
75    (6,9,11,14), # these can slide into square 10
76    (7,10,15),   # these can slide into square 11
77    (8,13),      # these can slide into square 12
78    (9,12,14),   # these can slide into square 13
79    (10,13,15),  # these can slide into square 14
80    (11,14))     # these can slide into square 15

The Search for the solution

What makes this game interesting is that the search space, even for the 3x3 version of the puzzle contains enough possibilites that we need be quite clever in our approach. The number of possible node configurations in the 3x3 puzzle is 9 factorial or 362880. (why?). For a 4x4 puzzle the number would zoom to 20922789888000.

We'll look at doing the two brute force searches and then optimize them with 2 interesting algorithms that will greatly prune the results as the work proceeds. These are the Greedy and the A-star algorithms both of which use a heuristic to estimate the "goodness" of any particular configuration.

Intermediate results are stored in a priority queue in order of their "goodness". The "best" configurations move to the front of queue and get immediate follow-up for the next moves. Less promising wither away.

Generating Puzzles

When you bought one of these puzzles, it came with the tiles in order. You then could slide the tiles around to scramble them into a puzzle to be solved.

The little program tilesScramble.py does a random walk (drunkards walk) of the empty space for the number of steps input and outputs a new configuration.

 1 #  tilesScramble.py
 2 #
 3 #  Scramble the solution by making N random moves.
 4
 5 def scramble(times) :
 6     import tiles, random
 7     board = "12345678_"
 8     game = tiles.TileGame(board) # the goal board
 9     used = {}
10     while times > 0 :
11         used[board] = True             # mark as taken
12         empty, moves = game.getMoves(board)
13         move = random.choice(moves)
14         nextBoard = game.makeMove(board,empty,move)
15         if used.get(nextBoard) : continue
16         board = nextBoard
17         times -= 1
18     return board
19
20 def main() :
21     import sys, sarg
22     moves = sarg.Int("moves",15)   # Number of times to randomly move
23     print(scramble(moves))
24
25 if __name__ == "__main__" : main()
26

A TileGame object is created (line 8) and the initial board set to the goal. The while loop (line 10) steps the appropriate number times randomly choosing a legal move at each step and also avoiding looping (line 15).

Below are a couple of sample runs. The number of random moves to make is taken using the sarg module (line 22). The default is 15 moves

$ python tilesScramble.py moves=10
2731_5846
$ python tilesScramble.py
5_1463827

You might well wonder why go this trouble when we could convert the goal to a 9 element list, use random.shuffle on it. Then bring it back to a string. The problem is that we're apt to get something that can't be solved. With the program we have something we know can be solved.

Representing Game Nodes

There is more information that must accompany the layout of the tiles. I want to take the approach of keeping this information in a tuple rather than creating an object class for the game nodes. One reason is for speed and size. Another is that by ordering the items in the tuple we will automatically get a very simple insertion into a priority queue.

Each tuple representing a game node will have the following 4 items in the order shown.

• The expected cost based on both past moves an and estimate of future moves
• The number of past moves so far
• The 9 character configuration of the board
• A pointer to the parent node of this node or None for the start node

The ordering of the information in the tuple is very important. If you sort a set of node tuples, the order you get is by "least expected overall cost".

Adding Heuristics to Solution Search

We'll take a give board configuartion and generate its "children" or successor boards. These will be reinserted into the priority queue.

With heuristics we can estimate how "good" a partial solution this, that is, how close it is likely to be to the final solution and insert it into the priority queue accordingly.

This is the heart of the A-star algorithm. Rather than depth-first or breadth-first, we use a priority queue to reinsert a partial result ahead of others whose "estimated overall cost" is greater. We always take from the front of the queue, that is, the partial solution with the least expected cost.

The "future expected cost" is of course the futureCost method in tiles.py above.

The Search Itself

The progam tilesSearch.py is shown below and will be explained in detail.

 1 #  tilesSearch.py
 2 #
 3 #  Search for sequence of moves to bring a randomized tile puzzle
 4 #  into order
 5
 6 import sys, sarg, time
 7 from   tiles  import TileGame
 8
 9 try:
10     import Queue as Q  # python ver. < 3.0
11 except ImportError:
12     import queue as Q
13
14 def main() :
15     board = sys.argv[1]
16     ratio = sarg.Int("ratio",2)
17     timed = sarg.Int("time",0)
18     game  = TileGame(board)
19     startTime = time.time()
20     path = search(game,board,ratio)
21     elapsed = time.time()-startTime
22     if timed : timeMsg = "Search took %s secs" % elapsed
23     else     : timeMsg = ""
24     print("tilesSearch.py: Moves=%s %s" % (len(path),timeMsg))
25     for entry in path : print(entry)
26

Function main gets a board and two optioal values from the command line. (line 15-17) A ratio used to balance the number of past moves to the overall futureCost calculated as a summation of manhatten distances to the goal state as explained above. The startTime is set from the system clock (line 19). The function search is then called with an initialized game instance followed by the parameters needed.

The search is also timed and output on request. (line 22). The path returned is printed.

The search function is similar to tilesScramble.py

27 def search(game, board, ratio) :
28     closed  = {}
29     queue   = Q.PriorityQueue()
30     origCost = game.futureCost(board)*ratio
31     orig = (origCost,0,board,None) # (cost,nMoves,board,parent)
32     queue.put(orig)
33     closed[orig] = True
34     expanded = 0
35     solution = None

The setup phase creates a closed dictionary to prevent looping, and a priority queue. The first node is queued, orig, is queued and we're ready to start.

36     while queue and not solution :
37         parent = queue.get()
38         expanded += 1
39         (parCost, parMoves, parBoard, ancester) = parent
40         empty, moves = game.getMoves(parBoard)
41         for mov in moves :
42             childBoard = game.makeMove(parBoard,empty,mov)
43             if closed.get(childBoard) : continue
44             closed[childBoard] = True
45             childMoves = parMoves+1
46             childCost = game.futureCost(childBoard)*ratio + childMoves
47             child = (childCost,childMoves,childBoard,parent)
48             queue.put(child)
49             if childBoard == game.goal : solution = child

The search loop (lines 36) gets the next node from the queue (line 37) and expands it (line 40). Legal moves from this position each have their cost evaluated (line 46) using both the futureCost function and the moves used so far. These are reinserted back into the queue. (line 48). We break on the first solution found. If no solution is found the queue runs dry. (Failure)

50
51     if solution :
52         print("%s entries expanded. Queue still has %s" % \
53              (expanded,                     queue.qsize()))
54         # find the path leading to this solution
55         path = []
56         while solution :
57             path.append(solution[0:3]) # drop the parent
58             solution = solution[3]     # to grandparent
59         path.reverse()
60         return path
61     else :
62         return []
63

If we get a solution (line 51), it is reconstructed from the linkages to parent nodes. But that is the solution in reverse. This is fixed in line 59 and the path returned. No solution results in an empty path being return.

Testing various Strategies

In this section we'll look at solving the puzzle by simple breadth-first search, and then with an intelligent heuristic. The breadth-first search does not consider future expection but only moves-so-far in the nodes produced. By setting the "future-ratio" to zero we get exactly that. The puzzle we'll use is solved in just 15 moves.

$ python tilesSearch.py 1234_5678 ratio=0 time=1
2391 entries expanded. Queue still has  1297
tilesSearch.py: Move= 15 Search took 0.0591 secs
(0, 0, '1234_5678')
(1, 1, '12345_678')
(2, 2, '12345867_')
(3, 3, '1234586_7')
(4, 4, '123458_67')
(5, 5, '123_58467')
(6, 6, '1235_8467')
(7, 7, '1235684_7')
(8, 8, '12356847_')
(9, 9, '12356_478')
(10, 10, '1235_6478')
(11, 11, '123_56478')
(12, 12, '123456_78')
(13, 13, '1234567_8')
(14, 14, '12345678_')

The solution to the puzzle is just 15 moves but 2391 nodes were evaluated. The time, about 1/16 of a second is testimony to the speed of modern laptops.

Now let's run this for various values of "future-ratio". The results are a bit surprising. For brevity I have trimmed off the details of the 15 moves. There are always the same

$ python tilesSearch.py 1234_5678 time=1 ratio=0
2391 entries expanded. Queue still has 1297
tilesSearch.py: Moves=15 Search took 0.0508 secs

$ python tilesSearch.py 1234_5678 time=1 ratio=1
128 entries expanded. Queue still has 86
tilesSearch.py: Moves=15 Search took 0.0032 secs

$ python tilesSearch.py 1234_5678 time=1 ratio=2
90 entries expanded. Queue still has 64
tilesSearch.py: Moves=15 Search took 0.002 secs

$ python tilesSearch.py 1234_5678 time=1 ratio=3
110 entries expanded. Queue still has  77
tilesSearch.py: Move= 15 Search took 0.0029 secs

The optimum value for the ratio appears to be 2. But the lesson is that any consideration of the future cost vastly improves the performance both in time and CPU effort. Up to thirty to one. It's all about the ordering of partial solutions within groups with the same number of moves already taken.

The Greedy Algorithm

Finally, I'd like to look at one other algorithm that is somewhat simpler. This algorithm simply chooses the best child of its current node and never backtracks. It needs no queue and if it succeeds it is very very fast. tilesGreedy.py can get stuck and fail to solve a puzzle. But this is one it can. And we can compare it with the A-star solution.

01 #  tilesGreedy.py
...
08 def search(game, board) :
09     path    = []
10     closed  = {}         # boards already seen
11     closed[board] = True # don't return (avoid loops)
12     while True :
13         path.append(board)9
14         if board == game.goal : break
15         empty, moves = game.getMoves(board)
16         candidates = []
17         for mov in moves :
18             child = game.makeMove(board,empty,mov)
19             priority = game.futureCost(child)
20             if not closed.get(child) :
21                 candidates.append( (priority,child) )
22                 closed[child] = True
23         if candidates :
24             candidates.sort()
25             board = candidates[0][1]  # choose lowest cost board for next
26         else :
27             print "Cannot move from ",board
28             break
29     return path

Here there is no priority queue. The program looks only at expected future cost of the children nodes from a partial solution (line 19). It takes the candidates and simply gets the best by sorting them and taking the first of the list. (lines 24-25). Let's test it.

$ python tilesGreedy.py 1234_5678 time=1
tilesGreedy.py: 1234_5678 moves=15 Search took 0.0003 secs
1234_5678
12345_678
12345867_
1234586_7
123458_67
123_58467
1235_8467
1235684_7
12356847_
12356_478
1235_6478
123_56478
123456_78
1234567_8
12345678_

Ten times faster than A-star. And 300 times faster than breadth-first.

Here is a case where the both algorithms found a solution but the greedy solution is not optimum. It meanders through 59 moves instead of 23 for the A-star

$ python tilesGreedy.py 75126348_ time=1
tilesGreedy.py: 75126348_ moves=59 Search took 0.0014 secs


$ python tilesSearch.py 75126348_ time=1
414 entries expanded. Queue still has 260
tilesSearch.py: Moves=23 Search took 0.0105 secs

You can download this zip file for this project

Have Fun. If you have comments or suggestions You can email me at mail me

Copyright © 2014-2021 Chris Meyers and Fred Obermann

* * *