Solving well-known algorithmic problems

Introduction

Before looking at informed search, let me show you how to apply the search framework we've created to two well-known algorithmic problems. I hope this part turns out to be refreshing after the hard reading of the previous post.

The missionaries and cannibals problem

In this problem the world is made of a river, a boat, a boat operator, three missionaries and three cannibals. The boat operator can use the boat to cross the river, carrying at most 2 passengers in every trip. When the boat operator leaves a group alone on one side of the river, the number of missionaries and cannibals in that group must be balanced to prevent one group from overwhelming and -probably- killing the other while the boat operator is busy crossing the river.

The initial state of this world is three missionaries and three cannibals sitting on one side of the river. The goal of the problem is to cross everyone to the opposite side of the river, while keeping everyone alive (consider the boat operator is once a hardened marine and has no fear of cannibals, not even of missionaries!).

Before delving into the algorithmic solution to this problem, have a try at solving it using just your grey matter. First tackle it using a casual approach, and if that doesn't cut it use a systematic approach along the lines of problem formulation as described in the previous post.

A possible formulation of the problem that allows us to solve it using our search framework could be as follows:

initial = ((3,3), (0,0)) goal = ((0,0), (3,3)) cost = lambda x : 1 def successor ( s ):     mis = lambda b: b[0]     can = lambda b: b[1]     ouch = lambda a: mis(a) > 0 and can(a) > 0 and mis(a) != can(a)     def trip(a, b, a_to_b):         if mis(a_to_b) > mis(a) or can(a_to_b) > can(a): # check physical limits             raise Exception("Not enough people!")         nxt_a = (mis(a) - mis(a_to_b), can(a) - can(a_to_b))         if ouch(nxt_a):                        # discard fail a->b trips             raise Exception("Holocaust!")         nxt_b = (mis(b) + mis(a_to_b), can(b) + can(a_to_b))         return nxt_a, nxt_b                          result = []     a, b = s[0], s[1]     boat_floats = ((0,0), (1,0), (2,0), (1,1), (0,1), (0,2))     for a_to_b in boat_floats:         try:             tmp_a, tmp_b = trip(a, b, a_to_b)         except Exception as e:             continue         for b_to_a in filter(lambda b_to_a: b_to_a != a_to_b, boat_floats):             try:                 nxt_b, nxt_a = trip(tmp_b, tmp_a, b_to_a)             except Exception as e:                 continue             if not ouch(nxt_a):                  # discard wrong b->a trips                 result.append((nxt_a, nxt_b))     return result

Snippet 1 - Formulation of the missionaries and cannibals problem

From the snippet above, the toughest part is the function obtaining all the successors of a given state. We model each state as a 2-elements tuple, each element representing one side of the river; each river side in turn is modelled as a 2-elements tuple where the first element represents a number of missionaries and the second element represents a number of cannibals. Using this approach, the initial state is given by the expression ((3,3), (0,0)) whereas the goal state is given by the expression ((0,0), (3,3)). To model the boat contents we use a 2-elements tuple with the same meaning as a river side tuple.

Within the successor() function, we define three utility lambdas returning the number of missionaries and cannibals respectively in a side tuple (mis(side) and can(side)) and the validity of a side tuple (ouch(side)). Then we define a function simulating a boat trip between two sides (trip(side_a, side_b, boat_contents)) that returns what would be the new world state after performing that trip.

The main task of the successor() function is performed in the loop that follows. Given a world state, the loop tries all the possible combinations of trips side a -> side b and backwards, recording each valid combination in a list that is returned as output of the function.

Now we can apply the uninformed search algorithm from the previous post to the problem. Let's write it as a test method that we can integrate into our unit test suite:

def testMissionariesAndCannibals(self):         <paste code from snippet 1 right here>         problem = Problem(initial, goal, successor, cost)         problem.treeSearch(Problem.depthFirstGenerator(successor), True)         self.assertTrue(problem.solved())

Snippet 2 - Solving the missionaries and cannibals problem

Observe how we've used the duplicate-checking version of the algorithm. If you've analyzed the problem a little bit as I suggest above, you've seen the state space is actually a graph. Therefore we try to avoid the search to get stuck in a loop within the graph. This problem is simple enough to be solved very quickly using depth-first search, but I suggest you do your own experiments using other search methods, with and without duplicate checking, and see the results.

The 8-queens problem

This well-known game theory problem consists of placing 8 queens on a chess board so no queen attacks any other. The problem can be extended to any number of queens since its solution does not depend on board size. However increasing board size has a big impact on the world's state space thus the resources used by the search, since the number of states is at least the cubic root of n!, being n the board size.

Let's formulate this problem in a way suitable for our search algorithm:

initial = () cost = lambda x : 1 goal = lambda b : b == n def successor ( board ):     def attacks ( q1, q2 ):         return q1[0]==q2[0] or q1[1]==q2[1] or abs(q1[0]-q2[0])==abs(q1[1]-q2[1])                  result = []     for col in range(len(board), n):         for row in range(n):             new_queen = (row, col)             hostiles = [q for q in board if attacks(new_queen, q)]             if len(hostiles) == 0:                 nxt_board = board + (new_queen,)                 result.append(nxt_board)                 return tuple(result)

Snippet 3 - Formulation of the n-queens problem

Examine snippet 3 carefully. Can you spot anything unusual? In previous problems the goal was a definite state of the world, modelled as a constant (either some number or a tuple as in the missionaries&cannibals problem above).  That's because the solutions to those problems were exactly those sought states. In this case however, there are many valid solutions and the context of the problem does not tell us that one is preferred over the other. Moreover, specifying a single solution requires us to solve the problem in the first place! To find out whether a state is a solution to our problem we need to define a function taking the state as input and validating it against the goal constraints. Instead of checking the relative positions of all the queens currently on the board each time we call the goal() function, we chose to generate only valid states in the successor() function and then cheking if we have placed n queens on the board. By generating only valid states we severely decrease the number of states that have to be generated, which helps quite a bit memory-hungry search methods like breadth-first.

But for the goal() function to be used with our search algorithm, we need to make one (and just one) little  change. Goal checking must change from using the == operator to evaluating the goal() function. The following code snippet shows the updated search algorithm using the goal() function:

def treeSearch ( self, gen ):     fringe = [self.__initial]     self.__solution = self.__recurse(fringe, gen) def __recurse ( self, fringe, gen ):     for n in fringe:         if self.__goal(n):             return [n] # the base case     for desc in gen(fringe):         sol = self.__recurse(desc, gen) # the recursive case         if sol:             try:                 sol.insert(0, desc[sol[0]])             except:                 pass             return sol

Snippet 4 - Updated common search algorithm

I'll let as an exercise to you the modification of the unit tests we've coded so far so they work with the updated algorithm.

Now we can solve the problem surprisingly fast using duplicate-checking depth-first search, as follows:

def testQueens ( self, n = 8 ):         <paste code from snippet 3 right here>         problem = Problem(initial, goal, successor, cost)         problem.treeSearch(Problem.depthFirstGenerator(successor), True)         self.assertTrue(problem.solved())               print ("Solution found: " + str(problem.solution[-1]))

Snippet 5 - Solving the 8-queens problem

As before, I urge you to experiment with other search methods and obtain your own conclusions.

In the next post I'll show you how to use cost-based search with this algorithm framework. Till then, spend some time sharpening your python coding skills.