The 8-puzzle was one of the earliest heuristic search problems. The object of th
ID: 3666981 • Letter: T
Question
The 8-puzzle was one of the earliest heuristic search problems. The object of the puzzle is to slide the tiles horizontally or vertically (see pp.103, fig.3.28) into the empty space until the configuration matches the goal configuration. Two simple heuristics for the 8-puzzle/15-puzzle were given: Manhattan distance and misplaced tiles. Implement A* npuzzle.py program in Python using both heuristics and comparing the performance of the resulting algorithms. You define the initial and terminal configurations. You decide whether program will produce output as sequence of configurations graphically or as text. Please include code for it in Python
Explanation / Answer
import random
class State:
def __init__(self, nsize):
"""Initialze the n-puzzle problem, with n-size value, tsize the total nodes and initial the goal state from n.
"""
self.nsize = nsize
self.tsize = pow(self.nsize, 2)
self.goal = range(1, self.tsize)
self.goal.append(self.tsize)
def printst(self, st):
"""Print the list in a Matrix Format."""
for (index, value) in enumerate(st):
print ' %s ' % value,
if index in [x for x in range(self.nsize - 1, self.tsize,
self.nsize)]:
print
print
print st
def getvalues(self, key):
"""Utility function to gather the Free Motions at various key positions in the Matrix."""
values = [1, -1, self.nsize, -self.nsize]
valid = []
for x in values:
if key + x in range(0, self.tsize):
if x == 1 and key in range(self.nsize - 1, self.tsize, self.nsize):
continue
if x == -1 and key in range(0, self.tsize, self.nsize):
continue
valid.append(x)
return valid
def expand(self, st):
"""Provide the list of next possible states from current state."""
pexpands = {}
for key in range(self.tsize):
pexpands[key] = self.getvalues(key)
pos = st.index(self.tsize)
moves = pexpands[pos]
expstates = []
for mv in moves:
nstate = st[:]
(nstate[pos + mv], nstate[pos]) = (nstate[pos], nstate[pos +
mv])
expstates.append(nstate)
return expstates
def one_of_poss(self, st):
"""Choose one of the possible states."""
exp_sts = self.expand(st)
rand_st = random.choice(exp_sts)
return rand_st
def start_state(self, seed=1000):
"""Determine the Start State of the Problem."""
start_st = (self.goal)[:]
for sts in range(seed):
start_st = self.one_of_poss(start_st)
return start_st
def goal_reached(self, st):
"""Check if the Goal Reached or Not."""
return st == self.goal
def manhattan_distance(self, st):
"""Calculate the Manhattan Distances of the particular State.
Manhattan distances are calculated as Total number of Horizontal and Vertical moves required by the values in the current state to reach their position in the Goal State.
"""
mdist = 0
for node in st:
if node != 0:
gdist = abs(self.goal.index(node) - st.index(node))
(jumps, steps) = (gdist // self.nsize, gdist % self.nsize)
mdist = mdist + jumps + steps
return mdist
def huristic_next_state(self, st):
"""This is the Huristic Function. It determines the next state to follow and uses Mahattan distances method as the huristics. This this determined way, a A* approach for path finding is used.
If more than one path have same manhattan distance, then a random choice of one of them is analyzed and carried forward. If not best path, randomness to providethe other choice is relied upon. No Depth First search is Used."""
exp_sts = self.expand(st)
mdists = []
for st in exp_sts:
mdists.append(self.manhattan_distance(st))
mdists.sort()
short_path = mdists[0]
if mdists.count(short_path) > 1:
least_paths = []
for st in exp_sts:
if self.manhattan_distance(st) == short_path:
least_paths.append(st)
return random.choice(least_paths)
else:
for st in exp_sts:
if self.manhattan_distance(st) == short_path:
return st
def solve_it(self, st):
list_of_states = []
while not self.goal_reached(st):
st = self.huristic_next_state(st)
#self.printst(st)
list_of_states.append(st)
return list_of_states
if __name__ == '__main__':
print 'N-Puzzle Solver!'
print 10 * '-'
state = State(3)
print 'The Starting State is:'
start = state.start_state(10)
state.printst(start)
print 'Here it Goes:'
print state.solve_it(start)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.