Recently, I’ve been busy with the exercises in Artificial Intelligence: A Modern Approach by Russell and Norvig. Third chapter of the book is on uninformed search methods and constraint satisfaction problems. I have implemented a class base that provides capabilities to define various search,  constraint satisfaction problems (CSP) and solve them. I aimed for an implementation that follows the approach in book (I have the 1st edition) closely and tried to make sure that each algorithm resembles the given pseudocodes. Performance was not a consideration for me so there are many different ways to implement better performing code and actually there are already many different libraries available for search and CSPs. All code is implemented in Python3.1.

I have implemented a SearchProblem class that can be used to solve a search problem. A search problem is defined with the following components;

• Initial State: Starting state for the problem. To be able to solve a problem, we need to find a state representation and define it. This is achieved by sub-classing Search.State class and implementing a few necessary methods.
• Operators: Operators generate new states from a given state. Operators are given as functions that return new states from a given one.
• Goal Test: Goal test checks a state and tells if we reached our goal and can stop searching. This is also implemented as a function that takes a state as parameter and returns a boolean value
• Path Cost Function: Although not necessary for every problem, path cost function gives a cost value for getting to a state from another state. If necessary, a path cost function should take two states as input and return a numeric value representing cost.

Different uninformed search methods are implemented.

• Depth-First
• Uniform Cost
• Depth Limited
• Iterative Deepening

For example, for the famous missionaries and cannibals problem, after defining necessary classes and methods following piece of code solves it with breadth-first search. (Details of the implementation can be found in the source code at the end of post)

Solution found;

State: 3M 3C |B-| 0M 0C, Depth: 0, Path Cost: 0, Applied Operator: None
State: 3M 1C |-B| 0M 2C, Depth: 1, Path Cost: 1, Applied Operator: Move 2 C
State: 3M 2C |B-| 0M 1C, Depth: 2, Path Cost: 2, Applied Operator: Move 1 C
State: 3M 0C |-B| 0M 3C, Depth: 3, Path Cost: 3, Applied Operator: Move 2 C
State: 3M 1C |B-| 0M 2C, Depth: 4, Path Cost: 4, Applied Operator: Move 1 C
State: 1M 1C |-B| 2M 2C, Depth: 5, Path Cost: 5, Applied Operator: Move 2 M
State: 2M 2C |B-| 1M 1C, Depth: 6, Path Cost: 6, Applied Operator: Move 1 M 1 C
State: 0M 2C |-B| 3M 1C, Depth: 7, Path Cost: 7, Applied Operator: Move 2 M
State: 0M 3C |B-| 3M 0C, Depth: 8, Path Cost: 8, Applied Operator: Move 1 C
State: 0M 1C |-B| 3M 2C, Depth: 9, Path Cost: 9, Applied Operator: Move 2 C
State: 1M 1C |B-| 2M 2C, Depth: 10, Path Cost: 10, Applied Operator: Move 1 M
State: 0M 0C |-B| 3M 3C, Depth: 11, Path Cost: 11, Applied Operator: Move 1 M 1 C


I have implemented necessary state classes, operators and goal tests for the following problems; chain problem (exercise 3.15), sequence prediction problem (exercise 3.16) and 8 Puzzle.

For CSPs, there is no need to define specific state classes for each problem. CSPs are defined with their variables, their domains and constraints. Since CSP is actually a more specific version of a search problem, I have tried to re-use code implemented for search problem as much as possible. CSP class is initialized with variables, their domains and constraint functions and it converts the problem to a search problem, uses depth-first search to solve it. Forward checking is also implemented where a function that returns the illegal values for a specific assignment of variables should be given to CSP class.

For 8-queens problem, following code implements the constraints, forward checking function, defines a CSP and solves it.

Solution found for the problem (each letter corresponds to a row on chess board and values are columns where queen is located);

State: {'A': 1, 'C': 8, 'B': 5, 'E': 3, 'D': 6, 'G': 2, 'F': 7, 'H': 4}, Depth: 8, Path Cost: 8, Applied Operator: Assign Value


You can also find definition of a cryptarithmetic problem given in the book in source code.

Source Code

Feel free to contact me for any bug reports, suggestions and I’d be glad to answer your questions.