I. Introduction ---> Python An instance of the N-puzzle game consists of a board
ID: 3849666 • Letter: I
Question
I. Introduction ---> Python
An instance of the N-puzzle game consists of a board holding N = m^2 1 (m = 3, 4, 5, ...) distinct movable tiles, plus an empty space. The tiles are numbers from the set {1, ..., m^2 1}. For any such board, the empty space may be legally swapped with any tile horizontally or vertically adjacent to it. In this practice, we will represent the blank space with the number 0 and focus on the m = 3 case (8-puzzle).
Given an initial state of the board, the combinatorial search problem is to find a sequence of moves that transitions this state to the goal state; that is, the configuration with all tiles arranged in ascending order 0, 1,..., m^2 1. The search space is the set of all possible states reachable from the initial state.
The blank space may be swapped with a component in one of the four directions {‘Up’, ‘Down’, ‘Left’, ‘Right’}, one move at a time. The cost of moving from one configuration of the board to another is the same and equal to one. Thus, the total cost of path is equal to the number of moves made from the initial state to the goal state.
II. Algorithm Review
Recall from the lectures that search begins by visiting the root node of the search tree, given by the initial state. Among other book-keeping details, three major things happen in sequence in order to visit a node:
• First, we remove a node from the frontier set.
• Second, we check the state against the goal state to determine if a solution has been found.
• Finally, if the result of the check is negative, we then expand the node. To expand a given node, we generate successor nodes adjacent to the current node, and add them to the frontier set. Note that if these successor nodes are already in the frontier, or have already been visited, then they should not be added to the frontier again.
This describes the life cycle of a visit, and is the basic order of operations for search agents in this assignment—(1) remove, (2) check, and (3) expand.
III. Write driver.py
Write driver.py, which solves any 8-puzzle board when given an arbitrary starting configuration. The program will be executed as follows:
$ python driver.py <method> <board>
The method argument will be one of the following. You need to implement all three of them:
bfs (Breadth-First Search)
dfs (Depth-First Search)
ast (A-Star Search)
The board argument will be a comma-separated list of integers containing no spaces. For example, to use the bread-first search strategy to solve the input board given by the starting configuration {0,8,7,6,5,4,3,2,1}, the program will be executed like so (with no spaces between commas):
$ python driver.py bfs 0,8,7,6,5,4,3,2,1
IV. What Your Program Outputs
When executed, your program will create / write to a file called output.txt, containing the following statistics:
path_to_goal: the sequence of moves taken to reach the goal
cost_of_path: the number of moves taken to reach the goal
nodes_expanded: the number of nodes that have been expanded
search_depth: the depth within the search tree when the goal node is found max_search_depth: the maximum depth of the search tree in the lifetime of the algorithm running_time: the total running time of the search instance, reported in seconds max_ram_usage: the maximum RAM usage in the lifetime of the process as measured by the ru_maxrss attribute in the resource module, reported in megabytes
Example #1: Breadth-First Search
Suppose the program is executed for breadth-first search as follows:
$ python driver.py bfs 1,2,5,3,4,0,6,7,8
Which should lead to the following solution to the input board:
Example #2: Depth-First Search
Suppose the program is executed for depth-first search as follows:
$ python driver.py dfs 1,2,5,3,4,0,6,7,8
Which should lead to the following solution to the input board:
Explanation / Answer
driver.py
-----------------------------------------------
import numpy as np
from copy import deepcopy
import time
import resource
from collections import deque
from queue import PriorityQueue
from sys import argv
max_depth = 0
max_frontier = 0
count = 0
class Node(object):
def __init__(self, state = None):
self.state = state
self.depth = 0
self.parent = None
self.opt = None
self.blank = []
"""
Define a function to compute the corresponding position of a given tile.
"""
def getPos(state, val):
for i in range(0, len(state)):
for j in range(0, len(state)):
if (state[i][j] == val):
return [i, j]
"""
Define the four directions of the blank space: 'Up', 'Down', 'Left', 'Right'.
Given the current state, one move at a time, and each movement would result in a new state.
Notice here we also need to check if the new state is valid.
currNode: indicates the current situation of board, represented as a Node;
x: the movement of '0' in the x-axis;
y: the movemetn of '0' in the y-axis.
"""
def move(currNode, x, y):
n = len(currNode.state)
pos_old = currNode.blank
x_new = pos_old[0] + x
y_new = pos_old[1] + y
if (x_new < 0 or x_new >= n or y_new < 0 or y_new >= n):
pass
else:
newNode = Node(deepcopy(currNode.state))
newNode.depth = currNode.depth + 1
newNode.blank = [x_new, y_new]
newNode.state[pos_old[0]][pos_old[1]], newNode.state[x_new][y_new] = newNode.state[x_new][y_new], newNode.state[pos_old[0]][pos_old[1]]
return newNode
def up(currNode):
return move(currNode, -1, 0)
def down(currNode):
return move(currNode, 1, 0)
def left(currNode):
return move(currNode, 0, -1)
def right(currNode):
return move(currNode, 0, 1)
"""
Define a heuristic function that estimates how close a state is to the goal.
Here we use the Manhattan priority function, the sum of the distances of the tiles from their goal positions.
The manhattan distance of each tile is the sum of the horizontal and vertical distances.
"""
def manhattan(currState, goalState):
sum = 0
for i in range(0, len(currState)):
for j in range(0, len(currState)):
if (currState[i][j] != 0):
x_goal, y_goal = getPos(goalState, currState[i][j])
sum += abs(x_goal - i) + abs(y_goal - j)
return sum
"""
Define the basic search method.
Keep track of the parent and movement of every node, so that we can rebuild the path.
In order to complete four methods, we need to check the method and make different steps among them.
"""
def search(initNode, goalNode, frontier, method, f_limit = None, valueRecord = None):
global max_depth # to record the max depth
global max_frontier # to record the max size of frontier
global count # to count the number of expanded nodes
path = [] # to record the path
if (method == 'ASTAR'):
priority = manhattan(initNode.state, goalNode.state)
frontier.put((priority, 0, time.clock(), initNode))
elif (method == 'IDASTAR'):
f_initNode = initNode.depth + manhattan(initNode.state, goalNode.state)
if (f_initNode <= f_limit):
frontier.append(initNode)
else:
return None
else:
frontier.append(initNode)
explored = set()
explored.add(''.join(str(n) for n in initNode.state))
# print (explored)
while (frontier):
if (method == 'ASTAR'):
max_frontier = max(max_frontier, frontier.qsize())
else:
max_frontier = max(max_frontier, len(frontier))
# print(max_frontier)
node = Node()
if (method == 'BFS'):
node = frontier.popleft()
if (method == 'DFS' or method == 'IDASTAR'):
node = frontier.pop()
# print(node.state)
if (method == 'ASTAR'):
# print(frontier.get())
node = frontier.get()[3]
# print (node.state)
flag = True
for i in range(0, len(node.state)):
for j in range(0, len(node.state)):
if node.state[i][j] != goalNode.state[i][j]:
flag = False
if flag:
while (node):
neighbor = ''.join(str(n) for n in node.state)
# path.append(parent[neighbor][1])
# state = parent[neighbor][0]
path.append(node.opt)
node = node.parent
if (method == 'ASTAR'):
len_frontier = frontier.qsize()
else:
len_frontier = len(frontier)
return [path[::-1][1:], len(path) - 1, count, len_frontier, max_frontier, len(path) - 1, max_depth]
count += 1
upNode = up(node)
downNode = down(node)
leftNode = left(node)
rightNode = right(node)
def appendNode(node, neighborNode, s, order):
global max_depth
if (neighborNode):
neighbor = ''.join(str(n) for n in neighborNode.state)
# print (explored)
if (method == 'IDASTAR'): # IDASTAR uses map instead of set
f = neighborNode.depth + manhattan(neighborNode.state, goalNode.state)
if (f <= f_limit):
if (neighbor not in valueRecord or valueRecord[neighbor] >= f):
max_depth = max(node.depth + 1, max_depth)
frontier.append(neighborNode)
valueRecord[neighbor] = f
else: # BFS, DFS and ASTAR share the same recording method for visited nodes
if neighbor not in explored:
max_depth = max(node.depth + 1, max_depth)
if (method == 'ASTAR'):
p1 = neighborNode.depth + manhattan(neighborNode.state, goalNode.state)
p2 = order
# print(p1, p2)
frontier.put((p1, p2, time.clock(), neighborNode))
else:
frontier.append(neighborNode)
explored.add(neighbor)
neighborNode.parent = node
neighborNode.opt = s
if (method == 'BFS' or method == 'ASTAR'):
appendNode(node, upNode, 'Up', 0)
# print ('up')
appendNode(node, downNode, 'Down', 1)
# print ('down')
appendNode(node, leftNode, 'Left', 2)
# print ('left')
appendNode(node, rightNode, 'Right', 3)
# print ('right')
if (method == 'DFS' or method == 'IDASTAR'):
appendNode(node, rightNode, 'Right', 3)
appendNode(node, leftNode, 'Left', 2)
appendNode(node, downNode, 'Down', 1)
appendNode(node, upNode, 'Up', 0)
# print (node.state)
return None
"""
Define the BFS method, using an explicit queue.
Keep track of the parent and movement of every node, so that we can rebuild the path.
"""
def BFS(initNode, goalNode):
frontier = deque()
return search(initNode, goalNode, frontier, 'BFS')
"""
Define the DFS method, using an explicit stack.
Keep track of the parent and movement of every node, so that we can rebuild the path.
"""
def DFS(initNode, goalNode):
frontier = []
return search(initNode, goalNode, frontier, 'DFS')
"""
Define the A-Star method, using a priority queue.
Keep track of the parent and movement of every node, so that we can rebuild the path.
"""
def ASTAR(initNode, goalNode):
frontier = PriorityQueue()
return search(initNode, goalNode, frontier, 'ASTAR')
"""
Define the IDA-Star method, using an explicit stack.
Note the differences with DFS:
1) IDA-Star needs f-limit;
2) IDA-Star uses valueRecord instead of explored to check the visited nodes.
"""
def IDASTAR(initNode, goalNode):
f_limit = 0
res = []
while (not res):
valueRecord = {}
frontier = []
res = search(initNode, goalNode, frontier, 'IDASTAR', f_limit, valueRecord)
f_limit += 1
return res
"""
Define the main function to check the answer
"""
if __name__ == '__main__':
start_time = time.clock()
"""
Read the input into method and input_list.
"""
method, input_list = argv[1], argv[2]
"""
Convert the input into the matrix format.
And build the corresponding goalState.
"""
init = []
input_new = input_list.split(',')
n = int(np.sqrt(len(input_new)))
for i in range(0, n):
init.append([])
ele = input_new[n * i : (i + 1) * n]
for j in ele:
init[i].append(int(j))
goal = [[(n * x + y) for y in range(0, n)] for x in range(0, n)]
# print(goal)
# print(init)
"""
Solution starts here.
"""
initNode = Node(init)
goalNode = Node(goal)
initNode.blank = getPos(initNode.state, 0)
goalNode.blank = getPos(goalNode.state, 0)
if (method == 'bfs'):
res = BFS(initNode, goalNode)
if (method == 'dfs'):
res = DFS(initNode, goalNode)
if (method == 'ast'):
res = ASTAR(initNode, goalNode)
if (method == 'ida'):
res = IDASTAR(initNode, goalNode)
max_RAM = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss / (10 ** 6)
# print (res, "--- %s seconds ---" %(time.clock() - start_time), max_RAM)
"""
Generate the output file for result.
"""
output = []
output.append('path_to_goal: ' + str(res[0]))
output.append('cost_of_path: ' + str(res[1]))
output.append('nodes_expanded: ' + str(res[2]))
output.append('fringe_size: ' + str(res[3]))
output.append('max_fringe_size: ' + str(res[4]))
output.append('search_depth: ' + str(res[5]))
output.append('max_search_depth: ' + str(res[6]))
output.append('running_time: ' + str(time.clock() - start_time))
output.append('max_ram_usage: ' + str(max_RAM))
file = open("output.txt","w+")
for i in range(0, 9):
file.write(output[i] + ' ')
file.close
-------------------------------------------------------------------------------
'n-puzzle game solver using breath first search and depth first search algorithms'
puzzle.py
-------------------------------
import collections
import math
import os
import sys
import time
#Declare tuple subtype for nodes
Node = collections.namedtuple('Node', 'state cost parent move depth')
#Print board
def board(state):
#Check if input is valid
if state == 0:
print '0'
else:
#Row size
size = int(math.sqrt(len(state)))
#Build list
row = []
for i in range(size):
row.append(i*size)
#Build board
for i in row:
print state[i:i+size]
#Find goal state
def goal(state):
n = len(state)
goal = []
#Build goal
for i in range(n):
goal.append(i)
return tuple(goal)
#Move tile up
def up(state):
state_l = list(state)
#Size of square
size = int(math.sqrt(len(state_l)))
#Find 0
index = state_l.index(0)
#Check if not in top row
if index not in range(size):
#Move up
state_l[index-size], state_l[index] = state_l[index],state_l[index-size]
state = tuple(state_l)
return state
else:
return 0
#Move tile down
def down(state):
state_l = list(state)
#Size of square
size = int(math.sqrt(len(state_l)))
#Find 0
index = state_l.index(0)
#Check if not in last row
if index not in range(size*(size-1),size*size):
#Move down
state_l[index+size], state_l[index] = state_l[index], state_l[index+size]
state = tuple(state_l)
return state
else:
return 0
#Move left
def left(state):
state_l = list(state)
#Size of square
size = int(math.sqrt(len(state_l)))
#Find 0
index = state_l.index(0)
#Check not in left column
if index not in range(0,len(state),size):
#Move left
state_l[index-1], state_l[index] = state_l[index], state_l[index-1]
state = tuple(state_l)
return state
else:
return 0
#Move right
def right(state):
state_l = list(state)
#Size of square
size = int(math.sqrt(len(state_l)))
#Find 0
index = state_l.index(0)
#Check not in right column
if index not in range(size-1,len(state_l),size):
#Move right
state_l[index+1], state_l[index] = state_l[index], state_l[index+1]
state = tuple(state_l)
return state
else:
return 0
#Expand nodes
def expand(parent):
expanded = []
expanded.append(Node(up(parent.state), parent.cost+1, parent, "Up", parent.depth + 1))
expanded.append(Node(down(parent.state), parent.cost+1, parent,"Down", parent.depth + 1))
expanded.append(Node(left(parent.state), parent.cost+1, parent, "Left", parent.depth + 1))
expanded.append(Node(right(parent.state), parent.cost+1, parent, "Right", parent.depth + 1))
#Ignore invalid states
expanded = [parent for parent in expanded if parent.state != 0]
#return expanded
return tuple(expanded)
#breath first search method
def bfs(node):
#Final state
final = goal(node.state)
#Declare frontier
frontier = collections.deque()
frontier.append(node)
#Explored node and frontier nodes
explored = set()
nodes_expanded = 0
max_fringe_size = 0
max_depth = 0
while True:
#Node to test
actual = frontier.pop()
#Fringe size
fringe_size = len(frontier)
#Max search depth
if actual.depth > max_depth:
max_depth = actual.depth
#Check if goal is reached
if actual.state == final:
#Backtrack path to parent
final = actual
path = []
while True:
#Check if root node
if actual.depth == 0:
break
path.insert(0, actual.move)
actual = actual.parent
return path, final, nodes_expanded, fringe_size, max_fringe_size, max_depth+1
#Add explored node to explored set
explored.add(actual.state)
#Expand node
for i in expand(actual):
#Check if new nodes have been explored or already in frontier
if i.state not in explored:
#Order frontier for BFS
frontier.appendleft(i)
explored.add(i.state)
#Number of expanded nodes
nodes_expanded = nodes_expanded + 1
#Max frontier size
if len(frontier) > max_fringe_size:
max_fringe_size = len(frontier)
return 0
#depth first search method
def dfs(node):
#Final state
final = goal(node.state)
#Declare frontier
frontier = collections.deque()
frontier.append(node)
#Explored node and frontier nodes
explored = set()
nodes_expanded = 0
max_fringe_size = 0
max_depth = 0
while True:
#Node to test
actual = frontier.popleft()
#Fringe size
fringe_size = len(frontier)
#Max search depth
if actual.depth > max_depth:
max_depth = actual.depth
#Check if goal is reached
if actual.state == final:
#Backtrack path to parent
final = actual
path = []
while True:
#Check if root node
if actual.depth == 0:
break
path.insert(0, actual.move)
actual = actual.parent
return path, final, nodes_expanded, fringe_size, max_fringe_size, max_depth, 0
#Add explored node to explored set
explored.add(actual.state)
#Auxiliar stack
aux = collections.deque()
#Expand node
for i in expand(actual):
if i.state not in explored:
aux.append(i)
explored.add(i.state)
#Order frontier for DFS
aux.reverse()
for i in aux:
frontier.appendleft(i)
#Number of expanded nodes
nodes_expanded = nodes_expanded + 1
#Max frontier size
if len(frontier) > max_fringe_size:
max_fringe_size = len(frontier)
return 0
#RAM usage in MB
def memory():
#For Linux based
if os.name == 'posix':
import resource
return float(resource.getrusage(resource.RUSAGE_SELF).ru_maxrss / 1024)
#For Windows
else:
import psutil
p = psutil.Process()
return float(p.memory_info().rss / (1024 * 1024))
#txt output
def txtout(path, cost, nodes_expanded, fringe_size, max_fringe_size, depth, max_depth, t_total, mem):
f = open("output.txt", "w+")
f.write("path_to_goal: " + str(path))
f.write(" cost_of_path: " + str(cost))
f.write(" nodes_expanded: " + str(nodes_expanded))
f.write(" fringe_size: " + str(fringe_size))
f.write(" max_fringe_size: " + str(max_fringe_size))
f.write(" search_depth: " + str(depth))
f.write(" max_search_depth: " + str(max_depth))
f.write(" running_time: " + str(t_total))
f.write(" max_ram_usage: "+ str(mem))
f.close()
#Command line execution
def main():
#Initial time
t_ini = time.time()
#Method chosen
method = sys.argv[1]
#Initial state
initial = sys.argv[2]
#Execute bfs
if method == "bfs":
ini_state = [int(x) for x in initial.split(',')]
ini_state = tuple(ini_state)
ini_node = Node(ini_state, 0, None, None, 0)
t = bfs(ini_node)
#Execute dfs
if method == "dfs":
ini_state = [int(x) for x in initial.split(',')]
ini_state = tuple(ini_state)
ini_node = Node(ini_state, 0, None, None, 0)
t = dfs(ini_node)
#Memory used
mem = memory()
#Final time
t_end = time.time()
#Total time
t_total = t_end - t_ini
#Text output document
txtout(t[0], t[1].cost, t[2], t[3], t[4], t[1].depth, t[5], t_total, mem)
#Pythonism
if __name__ == "__main__":
main()