Lab task 1
from simpleai.search import CspProblem, backtrack, \
min_conflicts, MOST_CONSTRAINED_VARIABLE, \
HIGHEST_DEGREE_VARIABLE, LEAST_CONSTRAINING_VALUE
# Constraint that expects all the different variables
# to have different values
def constraint_unique(variables, values):
# Check if all the values are unique
return len(values) == len(set(values))
# Constraint that specifies that one variable
# should be bigger than other
def constraint_bigger(variables, values):
return values[0] > values[1]
# Constraint that specifies that there should be
# one odd and one even variables in the two variables
def constraint_odd_even(variables, values):
# If first variable is even, then second should
# be odd and vice versa
if values[0] % 2 == 0:
return values[1] % 2 == 1
else:
return values[1] % 2 == 0
if __name__=='__main__':
variables = ('John', 'Anna', 'Tom', 'Patricia')
domains = {
'John': [1, 2, 3],
'Anna': [1, 3],
'Tom': [2, 4],
'Patricia': [2, 3, 4],
}
constraints = [
(('John', 'Anna', 'Tom'), constraint_unique),
(('Tom', 'Anna'), constraint_bigger),
(('John', 'Patricia'), constraint_odd_even),
]
problem = CspProblem(variables, domains, constraints)
print('\nSolutions:\n\nNormal:', backtrack(problem))
print('\nMost constrained variable:', backtrack(problem,
variable_heuristic=MOST_CONSTRAINED_VARIABLE))
print('\nHighest degree variable:', backtrack(problem,
variable_heuristic=HIGHEST_DEGREE_VARIABLE))
print('\nLeast constraining value:', backtrack(problem,
value_heuristic=LEAST_CONSTRAINING_VALUE))
print('\nMost constrained variable and least constraining value:',
backtrack(problem, variable_heuristic=MOST_CONSTRAINED_VARIABLE,
value_heuristic=LEAST_CONSTRAINING_VALUE))
print('\nHighest degree and least constraining value:',
backtrack(problem, variable_heuristic=HIGHEST_DEGREE_VARIABLE,
value_heuristic=LEAST_CONSTRAINING_VALUE))
print('\nMinimum conflicts:', min_conflicts(problem))
Lab task 2
from simpleai.search import CspProblem, backtrack
# Define the function that imposes the constraint
# that neighbors should be different
def constraint_func(names, values):
return values[0] != values[1]
if __name__=='__main__':
# Specify the variables
names = ('Mark', 'Julia', 'Steve', 'Amanda', 'Brian',
'Joanne', 'Derek', 'Allan', 'Michelle', 'Kelly')
# Define the possible colors
colors = dict((name, ['red', 'green', 'blue', 'gray']) for name in names)
# Define the constraints
constraints = [
(('Mark', 'Julia'), constraint_func),
(('Mark', 'Steve'), constraint_func),
(('Julia', 'Steve'), constraint_func),
(('Julia', 'Amanda'), constraint_func),
(('Julia', 'Derek'), constraint_func),
(('Julia', 'Brian'), constraint_func),
(('Steve', 'Amanda'), constraint_func),
(('Steve', 'Allan'), constraint_func),
(('Steve', 'Michelle'), constraint_func),
(('Amanda', 'Michelle'), constraint_func),
(('Amanda', 'Joanne'), constraint_func),
(('Amanda', 'Derek'), constraint_func),
(('Brian', 'Derek'), constraint_func),
(('Brian', 'Kelly'), constraint_func),
(('Joanne', 'Michelle'), constraint_func),
(('Joanne', 'Amanda'), constraint_func),
(('Joanne', 'Derek'), constraint_func),
(('Joanne', 'Kelly'), constraint_func),
(('Derek', 'Kelly'), constraint_func),
]
# Solve the problem
problem = CspProblem(names, colors, constraints)
# Print the solution
output = backtrack(problem)
print('\nColor mapping:\n')
for k, v in output.items():
print(k, '==>', v)
Lab task 3
from simpleai.search import astar, SearchProblem
# Class containing methods to solve the puzzle
class PuzzleSolver(SearchProblem):
# Action method to get the list of the possible
# numbers that can be moved in to the empty space
def actions(self, cur_state):
rows = string_to_list(cur_state)
row_empty, col_empty = get_location(rows, 'e')
actions = []
if row_empty > 0:
actions.append(rows[row_empty - 1][col_empty])
if row_empty < 2:
actions.append(rows[row_empty + 1][col_empty])
if col_empty > 0:
actions.append(rows[row_empty][col_empty - 1])
if col_empty < 2:
actions.append(rows[row_empty][col_empty + 1])
return actions
# Return the resulting state after moving a piece to the empty space
def result(self, state, action):
rows = string_to_list(state)
row_empty, col_empty = get_location(rows, 'e')
row_new, col_new = get_location(rows, action)
rows[row_empty][col_empty], rows[row_new][col_new] = \
rows[row_new][col_new], rows[row_empty][col_empty]
return list_to_string(rows)
# Returns true if a state is the goal state
def is_goal(self, state):
return state == GOAL
# Returns an estimate of the distance from a state to
# the goal using the manhattan distance
def heuristic(self, state):
rows = string_to_list(state)
distance = 0
for number in '12345678e':
row_new, col_new = get_location(rows, number)
row_new_goal, col_new_goal = goal_positions[number]
distance += abs(row_new - row_new_goal) + abs(col_new - col_new_goal)
return distance
# Convert list to string
def list_to_string(input_list):
return '\n'.join(['-'.join(x) for x in input_list])
# Convert string to list
def string_to_list(input_string):
return [x.split('-') for x in input_string.split('\n')]
# Find the 2D location of the input element
def get_location(rows, input_element):
for i, row in enumerate(rows):
for j, item in enumerate(row):
if item == input_element:
return i, j
# Final result that we want to achieve
GOAL = '''1-2-3
4-5-6
7-8-e'''
# Starting point
INITIAL = '''1-e-2
6-3-4
7-5-8'''
# Create a cache for the goal position of each piece
goal_positions = {}
rows_goal = string_to_list(GOAL)
for number in '12345678e':
goal_positions[number] = get_location(rows_goal, number)
# Create the solver object
result = astar(PuzzleSolver(INITIAL))
# Print the results
for i, (action, state) in enumerate(result.path()):
print()
if action == None:
print('Initial configuration')
elif i == len(result.path()) - 1:
print('After moving', action, 'into the empty space. Goal achieved!')
else:
print('After moving', action, 'into the empty space')
print(state)
Lab task 4
import math
from simpleai.search import SearchProblem, astar
# Class containing the methods to solve the maze
class MazeSolver(SearchProblem):
# Initialize the class
def __init__(self, board):
self.board = board
self.goal = (0, 0)
for y in range(len(self.board)):
for x in range(len(self.board[y])):
if self.board[y][x].lower() == "o":
self.initial = (x, y)
elif self.board[y][x].lower() == "x":
self.goal = (x, y)
super(MazeSolver, self).__init__(initial_state=self.initial)
# Define the method that takes actions
# to arrive at the solution
def actions(self, state):
actions = []
for action in COSTS.keys():
newx, newy = self.result(state, action)
if self.board[newy][newx] != "#":
actions.append(action)
return actions
# Update the state based on the action
def result(self, state, action):
x, y = state
if action.count("up"):
y -= 1
if action.count("down"):
y += 1
if action.count("left"):
x -= 1
if action.count("right"):
x += 1
new_state = (x, y)
return new_state
# Check if we have reached the goal
def is_goal(self, state):
return state == self.goal
# Compute the cost of taking an action
def cost(self, state, action, state2):
return COSTS[action]
# Heuristic that we use to arrive at the solution
def heuristic(self, state):
x, y = state
gx, gy = self.goal
return math.sqrt((x - gx) ** 2 + (y - gy) ** 2)
if __name__ == "__main__":
# Define the map
MAP = """
##############################
# # # #
# #### ######## # #
# o# # # #
# ### ##### ###### #
# # ### # #
# # # # # # ###
# ##### # # # x #
# # # #
##############################
"""
# Convert map to a list
print(MAP)
MAP = [list(x) for x in MAP.split("\n") if x]
# Define cost of moving around the map
cost_regular = 1.0
cost_diagonal = 1.7
# Create the cost dictionary
COSTS = {
"up": cost_regular,
"down": cost_regular,
"left": cost_regular,
"right": cost_regular,
"up left": cost_diagonal,
"up right": cost_diagonal,
"down left": cost_diagonal,
"down right": cost_diagonal,
}
# Create maze solver object
problem = MazeSolver(MAP)
# Run the solver
result = astar(problem, graph_search=True)
# Extract the path
path = [x[1] for x in result.path()]
# Print the result
print()
for y in range(len(MAP)):
for x in range(len(MAP[y])):
if (x, y) == problem.initial:
print('o', end='')
elif (x, y) == problem.goal:
print('x', end='')
elif (x, y) in path:
print('·', end='')
else:
print(MAP[y][x], end='')
print()
