# Game Playing: The Sliding Tiles Puzzle

## The Game Setup

In this chapter we'll look at a one-person game that was popular in my childhood. It's a bit like the Rubic cube which came later and which is more challenging. Here is a picture of one.

The game has a small platform with generally 16 slots in a 4 by 4 square. There are 15 tiles usually numbered from 1 to 15, one per slot. This leaves an empty slot. Any tile adjacent to the empty slot may slide into it, which then makes the tiles previous slot empty. The object is to slide tiles, one at a time, to bring them into order. The order is first by row and then by column, with the empty slot at the end.

Animation of puzzle being solved. Return with the browser's Back button)

To keep things simple we'll first 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 partials as tight as we can. A simple string can do this nicely. These two examples show how both a 3x3 (three by three) board and a more standard 4x4 board might look.

```42_713856

12345678_9cfdbae
```

Every configuration string is either 9 (3^2) or 16 (4^2) characters long. Each digit 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 are 12345678_ and 123456789abcdef_. To have enough characters we just switched to hexidecimal.

## A Class for Helper Functions

We will build some small programs that both create and solve puzzles in both 3x3 and 4x4 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.

```01 # tiles.py
02 #
03 import sys
04
05 class TileGame :
06     def __init__ (self, sampleBoard="", dim=None) :
07         if len(sampleBoard) == 9 or dim==3 :
08              self.dim = 3;
09              self.legalMoves = legalMoves3; self.goal="12345678_"
10         elif len(sampleBoard) == 16 or dim==4 :
11              self.dim = 4;
12              self.legalMoves = legalMoves4; self.goal="123456789abcdef_"
13         else : scream("Invalid dimension or sample board")
14
15         self.makeManhatten()
16         if sampleBoard and sorted(sampleBoard) != sorted(self.goal) :
17             scream ("Invalid sample board")
18
```

The class name is TileGame and when an instance is created either a sample board configuration or a dimension (3 or 4) is passed to set up attributes for control.

The attribue dim is passed or set from the sample board. It determines which moves on the board are legal and what constitutes the goal board. (lines 7 to 12). A sample board generally is the starting configuration for the puzzle to be solved. The built-in sorted can be applied to it and also to the goal attribute. If it is valid their sorts will be equal. (line 16)

```>>> sorted("123456789abcdef_")
['1', '2', '3', '4', '5', '6', '7', '8', '9', '_', 'a', 'b', 'c', 'd', 'e', 'f']
```

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

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

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

```19     def getMoves(self, board) :
20         empty = board.find('_')
21         return empty, self.legalMoves[empty]

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

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

```22
23     def makeMove(self, board, empty, mov) :
24         lbrd = list(board)
25         lbrd[empty],lbrd[mov] = lbrd[mov],lbrd[empty]
26         return "".join(lbrd)

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

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

```27
28     def futureCost(self, board) :
29         # estimate future cost by sum of tile displacements
30         future = 0
31         for sq in range(self.dim*self.dim):
32             occupant = board[sq]
33             if occupant != '_' :
34                 shouldbe = self.goal.find(occupant)
35                 future  += self.manTable[(sq,shouldbe)]
36         return future
```

The method futureCost uses the idea of "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. The distance from where the tile is in a configuration and where it is in the goal.

```37
38     def makeManhatten(self) :
39         self.manTable = {}; Dim = self.dim
40         for aa in range(Dim*Dim) :
41             for bb in range(Dim*Dim) :
42                 arow = aa/Dim; acol=aa%Dim
43                 brow = bb/Dim; bcol=bb%Dim
44                 self.manTable[(aa,bb)] = abs(arow-brow)+abs(acol-bcol)
```

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 44 the use of the abs function which guarentees that "There are no Negative Distances".

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

```46     def printBoard(self, board, mesg="", sep="\f") :
47         if sep  : print sep
48         if mesg : print mesg
49         expand = ["%02s"%x for x in board]
50         rows = [0]*self.dim
51         for i in range(self.dim) :
52             rows[i] = "".join(expand[self.dim*i:self.dim*(i+1)])
53         print "\n".join(rows)
54

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

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

The slots under the tiles are numbered as follows in order 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.

```55 def scream(error) :
56     sys.stderr.write("Error: %s\n" % error)
57     sys.stdout.write("Error: %s\n" % error)
58     sys.exit(1)
59
60 legalMoves3 = ( # for a 3x3 board
61    (1,3     ),  # these can slide into square 0
62    (0,4,2),     # these can slide into square 1
63    (1,5),       # these can slide into square 2
64    (0,4,6),     # these can slide into square 3
65    (1,3,5,7),   # these can slide into square 4
66    (2,4,8),     # these can slide into square 5
67    (3,7),       # these can slide into square 6
68    (4,6,8),     # these can slide into square 7
69    (5,7))       # these can slide into square 8
70
71 legalMoves4 = ( # for a 4x4 board
72    (1,4     ),  # these can slide into square  0
73    (0,5,2),     # these can slide into square  1
...
85    (9,12,14),   # these can slide into square 13
86    (10,13,15),  # these can slide into square 14
87    (11,14))     # these can slide into square 15
88
89
```

## The Search for the solution

This game can be played in a similar manner to the water buckets problem where we used either a stack or a queue to control a depth first or breadth first search. To avoid having to repeat this material , please first read Queues, Trees and Water Buckets if this material is new to you and then return.

What makes this game more interesting than water buckets is that the search space, even for the 3x3 version of the puzzle contains enough possibilites that we need be more 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 is 20922789888000.

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

## 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.

```01 #  tilesScramble.py
02 #
03 #  Scramble the solution by making N random moves.
04
05 def scramble(dim, times) :
06     import tiles, random
07
08     game = tiles.TileGame(dim=dim)
10     used = {board: True}               # mark it "taken"
11     while times > 0 :
12         used[board] = True
13         empty, moves = game.getMoves(board)
14         move = random.choice(moves)
15         nextBoard = game.makeMove(board,empty,move)
16         if used.get(nextBoard) : continue
17         board = nextBoard
18         times -= 1
19     return board
20
21 def main() :
22     import sys
23     dim   = int(sys.argv[1])   # 3 or 4 for the size of board
24     moves = int(sys.argv[2])   # Number of times to randomly move
25     print scramble(dim, moves)
26
27 if __name__ == "__main__" : main()
```

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

Below are a couple of sample runs. The dimension (3 or 4) along with the number of random moves to make is taken from the command line.

```\$ python tilesScramble.py 3 10
2731_5846
\$ python tilesScramble.py 4 15
5_149638d27beafc
```

## 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 with both past moves and estimate of future moves
• The number of this past moves so far
• The 9 or 16 character configuration of the board (discussed above)
• 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 cost"

## The Search Itself

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

```01 #  tilesSearch.py
02 #
03 #  Search for sequence of moves to bring a randomized tile puzzle
04 #  into order
05
06 import time, Queue
07 from   tiles  import TileGame
08
09 def main() :
10     import sys, re
11     ratio = int(sys.argv[1]) # future to past cost
12     board = sys.argv[2]
13     game  = TileGame(board)
14     startTime = time.time()
15     path = search(game,board,ratio)
16     endTime = time.time()-startTime
17     print "tilesSearch.py: Move=", len(path), "Search took", endTime, "secs"
18     for entry in path : print entry
```

Function main gets two values from the command line. (line 47) A ratio used to balance out past moves from to the overall futureCost expressed as a summation of manhatten distances explained above. And the initial board at the start of the puzzle. (line 48). The function search is then called with these parameters and an initialized game instance. The search is also timed. (lines 50-52). The path returned is printed.

The search function itself is similar to tilesScramble.py

```20 def search(game, board, ratio) :
21     closed  = {}
22     queue   = Queue.PriorityQueue()
23     origCost = game.futureCost(board)*ratio
24     orig = (origCost,0,board,None) # (cost,nMoves,board,parent)
25     queue.put(orig)
26     closed[orig] = True
27     expanded = 0
28     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.

```29     while queue and not solution :
30         parent = queue.get()
31         expanded += 1
32         (parCost, parMoves, parBoard, ancester) = parent
33         empty, moves = game.getMoves(parBoard)
34         for mov in moves :
35             childBoard = game.makeMove(parBoard,empty,mov)
36             if closed.get(childBoard) : continue
37             closed[childBoard] = True
38             childMoves = parMoves+1
39             childCost = game.futureCost(childBoard)*ratio + childMoves
40             child = (childCost,childMoves,childBoard,parent)
41             queue.put(child)
42             if childBoard == game.goal : solution = child
```

The search loop (lines 29-42) get the next node from the queue (line 30) and expands it (line 31). Legal moves from this position each have their cost evaluated (line 39) using both the futureCost function and the moves used so far. These are reinserted back into the queue. (line 41). We break on the first solution found. If no solution is found the queue runs dry.

```43
44     if solution :
45         print expanded, "entries expanded. Queue still has " , queue.qsize()
46         # find the path leading to this solution
47         path = []
48         while solution :
49             path.append(solution[0:3]) # drop the parent
50             solution = solution[3]     # to grandparent
51         path.reverse()
52         return path
53     else :
54         return []
55
```

If we get a solution, it is reconstructed from the linkages to parent nodes. But that is the solution in reversed order. This is fixed in line 51 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 0 1234_5678
2391 entries expanded. Queue still has  1297
tilesSearch.py: Move= 15 Search took 0.0591349601746 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 0 1234_5678
2391 entries expanded. Queue still has  1297
tilesSearch.py: Move= 15 Search took 0.0597949028015 secs

\$ python tilesSearch.py 1 1234_5678
128 entries expanded. Queue still has  86
tilesSearch.py: Move= 15 Search took 0.00326108932495 secs

\$ python tilesSearch.py 2 1234_5678
90 entries expanded. Queue still has  64
tilesSearch.py: Move= 15 Search took 0.002366065979 secs

\$ python tilesSearch.py 3 1234_5678
110 entries expanded. Queue still has  77
tilesSearch.py: Move= 15 Search took 0.00289797782898 secs

\$ python tilesSearch.py 4 1234_5678
97 entries expanded. Queue still has  65
tilesSearch.py: Move= 15 Search took 0.0025041103363 secs

\$ python tilesSearch.py 5 1234_5678
118 entries expanded. Queue still has  80
tilesSearch.py: Move= 15 Search took 0.00318312644958 secs

\$ python tilesSearch.py 6 1234_5678
140 entries expanded. Queue still has  89
tilesSearch.py: Move= 15 Search took 0.00352501869202 secs
```

The optimum value for the ratio appears to be 2 although 4 is also quite good! 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)
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
```

As promised 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
tilesGreedy.py: 1234_5678 15 moves
took 0.000319957733154 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. 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 29 for the A-star

```\$ python tilesGreedy.py 75126348_  # Greedy Algorithm
Building table for manhatten distance
tilesGreedy.py: 75126348_ 59 moves
took 0.00218510627747 secs
['75126348_', '7512634_8', '751263_48', '751_63248', '_51763248',
...
'1235_6478', '123_56478', '123456_78', '1234567_8', '12345678_']

\$ python tilesSearch.py 3 75126348_
863 entries expanded. Queue still has  537
tilesSearch.py: Move= 29 Search took 0.0245909690857 secs
```