Simmoril’s Domain

I had some time to kill today, so I decided to take a brief look at a subject I’ve been wanting to study for some time: backtracking algorithms. One of the most common example problems used to demonstrate backtracking algorithms is the eight queens puzzle,  so I thought I’d try my hand at writing a solver for it in python.

The solver itself consists of one core class, Board, which contains a representation of a chess board as an 8×8 matrix of integers (the reason for this will be explained later in the article) and a list of queens on the board, where each queen is represented by a (row, col) tuple.

class Board:
    def __init__(self):
        self.board = [ [ 0 for x in range(8) ] for y in range(8) ]
        self.queens = []

Since we’ll be placing queens on the board and removing them as part of the backtracking algorithm, our Board class should provide this functionality. The backtrack algorithm will only need to remove the last queen that was placed, so we can implement it like a stack, with two operations: push:

   def push_queen(self, coord):
        #XXX: Should check if coord is a valid move
        row, col = coord
        self.board[row][col] += QUEEN
        self.mark_queen(coord, 1)
        self.queens.append(coord)

and pop:

    # Remove the last queen that was placed on the board.
    def pop_queen(self):
        row, col = self.queens.pop()
        # 'Unmark' all the squares the queen was covering.
        self.mark_queen((row, col), -1)
        # 'Unmark' the square the queen itself was on.
        self.board[row][col] -= QUEEN

(I’ll explain the += QUEEN and -= QUEEN business in a moment. For now, just understand that these lines of code ‘mark’ and ‘unmark’ the square the queen lies on).

We can’t just mark the square a queen occupies on the board; we also need to indicate which squares are no longer valid for a queen to be placed in. This is where the mark_queen() function comes into play. It marks all of the squares that the queen can cover. The way I have chosen to implement this is by ‘radiating’ out from the queen: that is, I check squares in all 8 directions from the queen, starting with a distance of 1 and going up to a distance of 7 (the maximum distance away a square on the board could be from the queen). If the square is still within the boundaries of the board, I mark it as being covered by the queen:

    # 'Mark off' the squares the given queen at coord covers on the board.
    def mark_queen(self, coord, mark):
        row, col = coord
        # 'Radiate' out in all 8 directions from the queen.
        for x in range(1, 8):
            if row - x >= 0:
                self.board[row - x][col] += mark           # -x,  0 (W)
                if col - x >= 0:
                    self.board[row - x][col -x] += mark    # -x, -x (SW)
                if col + x < = 7:
                    self.board[row - x][col + x] += mark   # -x, +x (NW)
            if row + x <= 7:
                self.board[row + x][col] += mark           # +x,  0 (E)
                if col - x >= 0:
                    self.board[row + x][col - x] += mark   # +x, -x (SE)
                if col + x < = 7:
                    self.board[row + x][col + x] += mark   # +x, +x (NE)
            if col - x >= 0:
                self.board[row][col - x] += mark           #  0, -x (S)
            if col + x < = 7:
                self.board[row][col + x] += mark           #  0, +x (N)

To further explain this code, it’s helpful to take a step back and look at a problem with a naive implementation of this function. Let’s assume for a second that instead of integers, we just use two values, say T and F, to indicate that a square is or isn’t covered by a queen. So we place a queen on the board by setting that square to F, and using mark_queen() to set all the squares the queen covers to F, indicating that a queen can no longer be placed in those squares. Now, say we place a second queen on the board using the same process; set the square the second queen is on to F and use mark_queen() to set all the squares the second queen covers to F. So far, so good.

Let’s see what happens if we use pop_queen() to remove that second queen we just placed. We set the square the second queen was on to T, and then use mark_queen() to set all of the squares the second queen covered to T, indicating they are now valid squares to place a queen. And here we have our problem: this is not necessarily true! If there is a square that both the first and second queen cover, its value needs to remain F since the first queen still covers it! But in using our naive implementation of mark_queen(), we have erroneously marked that square as T.

One way to solve this problem is to use an integer instead of just T and F. The integers act as ‘counters’ for the squares, indicating how many queens cover those squares. When the counter is 0, the square is free (since no queens are covering it) and any value greater than 0 will indicate the square is covered by at least one queen. Following this idea, we can now see how mark_queen() works: when a queen is placed on the board, we increment the counter of every square it covers, and when a queen is removed from the board, we decrement the counter of every square that queen covered. This method solves the problem above, since now if two queens cover the same square and we remove one of them, the counter will stay above 0 and the square will retain it’s “covered” status. To record the queen itself, I picked an arbitrarily large integer in order to distinguish it from squares that are merely covered:

# Arbitrarily large constant to use for the value of the queen
QUEEN = 100000

This helps aid us in printing out the board in a human-readable format:

    # Pretty-print the board
    def pprint(self):
        for x in range(8):
            for y in range(8):
                if self.board[x][y] == QUEEN:
                    print "Q",
                else:
                    print "_",
                    #print self.board[x][y],
            print

The last thing we need to implement the backtrack algorithm is a function to find all the free squares where we can place a queen. Following the ideas above, we just need to find all the squares that have a value of 0:

    # Generate a list of all the valid squares a queen can be placed on.
    def list_valid_moves(self):
        valid_moves = []
        for x in range(8):
            for y in range(8):
                if self.board[x][y] == 0:
                    valid_moves.append((x, y))
        return valid_moves

We are now ready to implement the backtrack algorithm. Given all the work above to implement the Board class, this function is surprisingly short:

    # Backtracking depth-first solver.
    def solver(self):
        # Get a list of valid moves
        valid_moves = self.list_valid_moves()
        for valid_move in valid_moves:
            self.push_queen(valid_move)
            self.solver()
            if len(self.queens) == 8:
                return
	    # this queen placement did not lead to a solution with 8 queens.
	    # Therefore, this placement can't be part of any valid solution, so
	    # roll it back and try the next one.
            self.pop_queen()
        # Nothing in the list of valid moves led to a solution, or there were
	# no valid moves left to try.
        return

In this function, we first generate a list of all the valid squares to place a queen. Then, for each valid square, we try placing a queen there and repeating the process: generating a new list of valid squares, and placing a queen in each one. Eventually, we will get to a point where one of two things will have occurred:

• We have placed 8 queens in total on the board, in which case this is a valid solution and we're done.
• There are no more valid squares to place a queen, and there are less than 8 queens in total on the board, in which case no solution involving the given queen placements exists.

So once the function terminates, the board will either contain a full solution, or it will contain a partial solution, in which case no full one exists. Another way to think of the code is as a depth-first search on the solution tree: the for loop cycles through all the children (possible queen placements) of a given node (the current board configuration), and each call to self.solver() expands a child node (places a queen) to go deeper into the solution tree (analyzing the new board configuration). However, instead of examining the entire tree, as soon as the algorithm sees a solution isn't possible from the current configuration it 'backs up' (removes the last queen placed) and tries a different branch (a different queen placement). The code goes through about 26,000 queen placements before finding the full solution; much faster than checking all 4.5 billion possible configurations. This is the solution it found:

$ python 8queens.py
Q _ _ _ _ _ _ _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
_ _ _ _ _ _ Q _
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
$

And here's the code. Enjoy!

Recently I’ve been doing a lot of work with awk, and I’ve been really impressed with all of the features available in its programming language. This got me to thinking about what kind of programs one could write in awk, that go beyond just text manipulation.

So, I decided to see if I could implement Tic-Tac-Toe with AI in awk. The quintessential project for undergraduate AI classes, it’s long been a favorite of mine because it’s not too long, but also not completely trivial.

My implementation, which is ~200 LoC, uses the negamax algorithm to scan the entire game tree for Tic-Tac-Toe, and gives the player the option to either go first or let the computer go first. The performance isn’t too bad: the computer’s first move (if the player goes first) takes about 10-15 seconds, but after that, it’s pretty much instantaneous.

I had a lot of fun implementing this, and there were some interesting things I encountered along the way:

• A large chunk of my time was spent trying to debug my implementation of the negamax algorithm. Unfortunately awk doesn’t really have a debugger per se, so I sort of cheated and implemented the algorithm in perl first, then translated that implementation into awk.
• The one blunder that really tripped me up was the find_best_move() function, which uses negamax to find the computer’s best move. I erroneously called negamax with a ‘color’ or 1 (instead of -1) and I didn’t negate the score that came back. Essentially, the thing to remember is the for loop that scans for the best move should look exactly like the for loop inside negamax, except that you’re recording what the best move is and returning that instead of the heuristic value of the board.
• One super-important detail in awk is that to make a variable local to a function, it has to be part of the parameter list. If it’s not, the variable comes into existence in the global namespace, which can lead to some very subtle bugs.
• Portable awk programming is tough! There are a lot of differences between implementations of awk, and getting one script to work on all of them is a real challenge.
• awk’s regex engine makes for a nice, fast board evaluator if you can create a regex to determine if a win exists for a player.
• One interesting way to view writing big awk programs is to think of the rules as ‘event handlers’, and each line of input as an ‘event’. This helped me avoid having to use getline() everywhere, and I think is a nicer way to structure the overall program.

If you want to try out the script yourself, just download it and run with the command awk -f ttt.awk. I’ve tried it out with gawk and BSD awk, and those both seem to work fine, but the script doesn’t work with AIX’s awk (due to issues with the split() function).

ttt.awk

So in an attempt to keep my coding skills sharp, I’ve been making my way through some of Facebook’s Engineering Puzzles. In particular, one puzzle that I found especially interesting was the ‘Gattaca’ problem, and so I thought I’d share my solution to the problem here.

The first thing to notice about the problem is that the talk about the DNA string and gene prediction stuff is pretty much a smokescreen. For this problem, the only thing that really concerns us is the gene predictions, which we’ll just call ‘intervals’. Each interval has three pieces: a start and end index to identify its boundaries, and a value. Our job then is to find the group of non-overlapping intervals that gives us the largest sum.

First, we start with a little boilerplate code. The Interval class is just a small, struct-like class to represent an interval. This is mostly for the sake of improving  the readability of the code; one could use a tuple or a dict instead.

# Small container class for intervals.
class Interval:
    def __init__(self, start, end, val):
        self.start = start
        self.end = end
        self.val = val

Next, we parse out the intervals from the input file (given as the first command-line argument to the script). Since we can ignore all the DNA string information, we scan through the file until we find an interval, which will be the only lines that have 3 whitespace-delimited fields.

# Get the list of the intervals from the input file.
def get_intervals():
    intervals = []
    f = open(sys.argv[1], 'r')
    for line in f:
        fields = line.strip().split()
        if len(fields) == 3:
            # Interval has 3 fields (start, end, val)
            intervals.append(Interval(*[int(x) for x in fields]))
    return intervals

Now that we have a list of intervals, the next task is to determine if two intervals overlap or not. An interval is a range of integers denoted by a start index, , and an end index, , where . Say we have a second interval, denoted by . Then, if and do not overlap, one of two things must be true: either must start after ends, or must end before starts. In other words, either or . If neither of these are true, then the intervals overlap.

# Returns True if intervals a and b do not overlap, false otherwise.
def comp_intv(a, b):
    if a.end < b.start:
        return True
    elif b.end < a.start:
        return True
    else:
        return False

We now have all the pieces we need to do a search for the largest sum. For this, I use a technique similar to the one used to find paths through the graph in the Boggle Bash Trainer. We start with an arbitrary interval, call it , and an ‘allowed’ list of intervals that do not overlap with any intervals already in the group. We take this ‘allowed’ list, and pare it down by removing any intervals that overlap with . If this new ‘allowed’ list is empty, then the maximum total is just the value of . If the list isn’t empty, then the maximum total is the value of this interval plus the maximum total out of all possible additions from the new ‘allowed’ list.

# Find the max total from a given starting interval and list of compatible
# intervals.
def find_max(start, allowed):
    # Find all compatible intervals.
    my_allowed = [x for x in allowed if comp_intv(x, start)]
    if not my_allowed:
        # No more possible additions, so max is just this interval's val
        return start.val
    else:
        # Otherwise, max is the addition of start's val plus the max val
        # out of start's possible additions.
        return start.val + max([find_max(x, my_allowed) for x in my_allowed])

Some things to note are that the comp_intv() function from above returns false if called with the same interval for a and b. This ensures that an interval is only used once in a group. Also, note that on subsequent calls to find_max(), each new 'allowed' list is the list of intervals that does not overlap with any of the intervals added to the group thus far. So if say the group has intervals , then the 'allowed' list contains all intervals that do not overlap with or . So when we try to add and pare down the allowed list to remove any intervals that overlap with , we are left with a list of intervals that does not overlap with any of .

From here, there is just one last step to find the largest sum. We simply call find_max() for every interval in the input file, then find the largest sum in that list. This gives us the largest possible sum out of all the intervals. Note that in this initial call, the 'allowed' list is simply the list of all intervals (since at this point, no intervals have been added to the group).

total = max([find_max(intv, intervals) for intv in intervals])

The full script can be downloaded here.

So… much… fail…

Introduction

So, I recently became addicted to an online game called Boggle Bash, which is pretty much the original Boggle with a couple of twists thrown in. Although I’d been playing it for a couple weeks, at the very outset I had an overwhelming urge to build a program to ‘assist’ me in playing Boggle Bash. This is the story of me finally giving into that urge.

The Rules

For those of you who haven’t played Boggle, it’s a word game where 16 die are randomly ‘thrown’ into the slots of a 4×4 grid. The goal of the game is to form as many words as you can before the timer runs out. How do you form a word? Well, you start at any slot and move to any adjacent slot (up,down, left, right, and diagonally) that you haven’t already visited. Here’s a screenshot from the Boggle Bash website to illustrate:

In this example, you can form the word TEN by starting with the T in row 2, column 4, and moving down to the E, then diagonally down to the N. But, you can’t form the word TENSE, since you can’t use the one E twice. There’s some other weird nuances, like no words less than 3 letters long, no proper nouns, no acronyms, etc., but you get the basic idea.

Bending the Rules

Some of you out there might already begin to see how a computer program could play Boggle. One method (and, coincidentally, the one I chose) is brute force, which is a two step process:

1. Find every single possible legal combination of letters.
2. Check each combination of letters. If it’s a word, keep it. If not, discard it.

Simple, yet highly effective. Let’s take a look at each step.

Walking a Boggle Board

One way to look at the Boggle board is not as a 4×4 grid, but as a graph with 16 nodes (sorry, my graphviz skills suck, tilt your head to see it oriented properly):

The problem of finding Boggle-legal words now becomes the problem of finding paths on the graph that have 3 or more vertices (without visiting any vertex more than once). Fair warning: the following explanation might not make total sense, and I take full responsibility.

Building the Graph

The first thing we need to do is build a representation of the above graph by creating an adjacency list, which is just a list that tells us which vertices are connected to which.

We start with a 4×4 matrix representing the Boggle board. This matrix is then used to build the adjacency list via the following algorithm: for every vertex in the matrix:

1. Try to move in all 8 directions (up-left, up, up-right, left, right, down-left, down, down-right).
2. For each direction, if you haven’t walked off the matrix, add the new vertex to this vertex’s adjacency list.

So, as a quick example, starting with node 0, we see we can walk right, down-right, and down, so the adjacency list for 0 is (1, 4, 5).

Finding all valid paths

Given the adjacency list, we now need to find a list of all valid paths through the graph. We start by trying to find all valid paths of an arbitrary length, call it n. To do this, for every vertex in the graph:

1. Use the adjacency list to find all vertices adjacent to the current one that you haven’t already visited.
2. For each adjacent vertex, find all paths of length n – 1 from that vertex. Tack on the current vertex to each path you find and voila! You have now found all paths of length n from the given vertex.

Sound confusing? Yeah, it was to me at first too. Here’s a quick example to illustrate: say you wanted to find all paths of length three. The method above takes us through the following steps:

1. We start at vertex 0, and the adjacency list tells us we can go to vertices 1, 4, and 5. We now look for all paths of length 2 from these vertices.
2. We start with vertex 1. The adjacency list tells us we can go to vertices 0, 2, 4, 5, and 6. We discard vertex 0, since we’ve already visited it, leaving 2, 4, 5, and 6. We now look for paths of length 1 from each of these vertices.
3. We start with vertex 2. Since our path length is now 1, we stop here, and record our first found path of length 3, namely (0 -> 1 -> 2).
4. We now start with vertex 4 from step 2. Again, the path length is now 1, so we stop here, and record the second found path of length 3, namely (0 -> 1 -> 4).

Building lists of paths for every length from 3 to 16 gives us a list of every valid path through the Boggle board (yes, there are a lot of them!).

Finding Real Words

So now we’ve got this big list of paths like (0 -> 1 -> 2), (0 -> 1 -> 4), (0 -> 1 -> 5), etc. The next task is to turn these paths into strings, and check if the strings are valid words. This step is actually quite a bit easier than building the list of paths. Just substitute letters for each of numbers, put all the letters together, and then use a spell-checker to see if the string you have it a valid word. For example, using the above graph and Boggle screenshot, we can translate the path (0 -> 1 -> 2) into the string JED. Our spell-checker (hopefully) tells us that’s not a word, and so we discard it.

From Theory to Practice

And now for the punchline you’ve all been waiting for: my implementation of the above method is written in python, and consists of two classes: BoggleBoard.py and BoggleTrainer.py. BoggleBoard uses the above method to generate a list of all possible paths. BoggleBoard is actually quite a bit more flexible than is needed, as it can generate valid path lists for Boggle boards of arbitrary dimensions.

BoggleTrainer then uses this path list and a given board layout to generate a list of all possible strings. It then checks those string using the Enchant spell-checking library. Valid words are kept, invalid words are discarded.

Reality is a Harsh Mistress

I field-tested the code for about a week or so, and the results were pretty positive. Running the code with python 2.6.2 on a 3.00 GHz Pentium 4 with 2 GB of RAM, the script was able to find all valid words up to 8 letters long in a reasonable amount of time. However, although the script works as advertised, it turns out there’s a few shortcomings:

• The script doesn’t run fast enough to be able to check every single possible string in time (a single round of Boggle Bash is 3 minutes). The bottleneck is mostly with the Enchant library, although since the script attempts to cache all possible paths in RAM, that could be a bottleneck as well. However, at longer string lengths, the odds of finding a valid word decrease rapidly. I therefore decided to make a trade-off of only scanning strings up to 8 letters long.
• The dictionary included with Enchant doesn’t exactly match Boggle Bash’s dictionary. Most notably, names and acronyms show up as false positives, and there are words that Enchant does not recognize as valid (how is ‘online’ not a word?).
• The script itself doesn’t interface with the actual Boggle client at all. The board layout has to be entered manually as a string of 16 characters, and words from the word list have to be entered back into the Boggle client by hand. However, interfacing with the Boggle Bash client wasn’t really the main point of this exercise, so this is more of a side-note than an actual problem.

What Now?

I’m sure there’s like a kerjillion different optimizations/tweaks/enhancements that I completely missed so please feel free to leave them in the comments. One I thought of right off the top of my head was to spread out the spell checking over multiple cores by using python’s XML-RPC for message passing. Another might be trying to speed up the spell-checker, or doing something with tries. Actually interfacing with the Boggle Bash client might be cool too.

That’s it for my end, thanks to Pogo.com for creating such an enjoyable game, and I hope you’ve had as much fun reading this article as I’ve had writing it!

From Google Treasure Hunt 2008:

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 5 consecutive prime numbers,
the sum of 517 consecutive prime numbers,
the sum of 551 consecutive prime numbers,
and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as
the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).

I wrote my solution to this problem in ~60 lines of python. In a nutshell:

1. Get a precomputed list of (1,000,000) primes.

2. Find all possible summations of 551 consecutive prime numbers. If the sum is prime, store this in a list of ‘candidates’.

3. Find all possible summations of 517 consecutive prime numbers. If the sum is in the candidate list from step 2, store it in a new candidate list.

4. Repeat step 3 using this new candidate list for summations of 5 and 3 consecutive prime numbers.

5. The smallest number in the final candidates list is the answer.

The script ran pretty quickly on my machine (3.00 GHz P4), taking about 1-2 minutes to find the answer.

Honestly, I have to say I was surprised to see that (at the time of this writing) this book was averaging 4.5 stars on Amazon. I suppose my expectations of this book were heavily swayed by the title. I was expecting something a little more generic and high-level than what I got.

I think the book makes a decent attempt to provide the reader with ‘recipes’ that can be used to improve their efficiency and productivity. But the recipes themselves seem to be a little too free-flowing: by the time I got around to the 3rd or 4th recipe, I had already forgotten the overarching theme of the chapter. I feel like the material might’ve been better presented in the style of O’Reilly’s “Cookbook” book. I doubt a reader, after one pass through the book, will be able to implement every recipe they read about. I think it would be better to structure the book as a reference that they can flip through later.

Another issue I had with the book was that in the later half of the book, many of the examples given contain chunks (sometimes large chunks) of Java, Ruby, and Groovy code. While I’m sure many readers of this book are familiar with those languages, for those who aren’t, the chunks become a serious roadblock to understanding the point of the example. Many of the examples (the Groovy ones, especially) cannot simply be interpreted ‘by sight’. Perhaps a future edition of the book could have some type of fair warning at the beginning.

If you are a java developer, I think you can probably get a lot out of this book. If not, you’ll probably still be able to get a good amount of information out of the first few chapters, but I’d suggest just skimming or skipping the latter chapters altogether.

My rating: 3/5 stars.