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
  • Breadth-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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

"""
Problem Definition
"""
# operators
operators = []
operators.append(Search.Operator("Move 2 M", Move2MAcross))
operators.append(Search.Operator("Move 1 M", Move1MAcross))
operators.append(Search.Operator("Move 2 C", Move2CAcross))
operators.append(Search.Operator("Move 1 C", Move1CAcross))
operators.append(Search.Operator("Move 1 M 1 C", Move1M1CAcross))

# create initial state
initialState = MCState(3, 3, 1)

# define problem
MCProblem = Search.SearchProblem(initialState, operators, MCGoalTest)

node = MCProblem.BreadthFirstSearch()
solution = MCProblem.GetSolutionPath(node)
for n in solution:
    print(n)

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import itertools
import CSP

def CheckConstraints(state):
    # for every pair of queen
    for s1, s2 in itertools.combinations(state.assignments.keys(), 2):
        #if 2 queens are on the same column
        if state.assignments[s1] == state.assignments[s2]:
            return False
        #if 2 queens are attacking each other diagonally
        rowDiff = ord(s2)-ord(s1)
        if state.assignments[s1] + rowDiff == state.assignments[s2] or 
           state.assignments[s1] - rowDiff == state.assignments[s2]:
            return False
    return True

def ForwardChecking(state, val):
    """
    Return a dictionary of illegal values for each unassigned variable
    """
    # find unassigned variables
    unassignedVars = list(state.varList)
    [ unassignedVars.remove(k) for k in state.assignments.keys() ]
    # nextVariable is being assigned right now it is not an unassigned variable
    unassignedVars.remove(state.nextVariable)
    # dictionary that holds values to be removed for each variable
    removeVals = {}
    # for every unassigned variable, construct a list of values to be removed
    for v in unassignedVars:
        vals = []
        # two queens can't be on same column
        vals.append(val)
        # add diagonal positions if they are inside boundaries of chess board
        rowDiff = ord(v)-ord(state.nextVariable)
        if val+rowDiff > 0 and val+rowDiff <= 8:
            vals.append(val+rowDiff)
        if val-rowDiff > 0 and val-rowDiff <= 8:
            vals.append(val-rowDiff)
        removeVals[v] = vals
    return removeVals

if __name__ == '__main__':
    varsAndDomains = {('A','B','C','D','E','F','G','H'):[1,2,3,4,5,6,7,8]}
    csp = CSP.CSP(varsAndDomains, [CheckConstraints], ForwardChecking)
    node = csp.Solve()
    print(node)

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.