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)

You can download this zip file for this project

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

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.

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

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.

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) 09 board = game.goal # start with solution 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

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
Nonefor 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"

In the *water bucket* problem, we used brute force to search for a solution. The breadth first search lets us examine and keep possible partial solutions even handily. As each new step in a partial solution was taken, the result was sent to back of the queue to let other partial solutions have their chance. In this way, the shortest and best solution to the problem is found first. A depth first approach, on the other hand, would requeue the result at the front. This makes us hammer away at whatever we started and even if we do find a solution, it is unlikely to be the optimal one.

But supposing we do something between these extremes. If we can estimate how "good" a partial solution this, that is, how close it is to the final solution, and requeue it based on this, we can shorten the search greatly.

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

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.

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

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-2018 Chris Meyers