\"Finished!\" A little more details for the input and output: The input would be

Question

"Finished!"

A little more details for the input and output:

The input would be ask same as above, numbers between 1-15, 0(for blank) in any order, but then another promt asking user to give a end goal as to where they want the 0(for blank) to end up at:

Example Input (two promts asking user to enter random rows from 1-15 with a 0(for blank), then entering desired goal, for this example we want the 0 to be at the end of matrix with our matrix being sorted in order 1-15.):

So here we enter our 15 number 1-15 in mix order with 0(for blank between 10 and 11) Now we ask the user for end solution they want the matrix to look like:

Here we enter the desired goal we want and then the matrix will generate our solution to be as inputed above, basically trying to get the 0 to end as best as possible.

Basically the end goal would be to move the 0 to the end of matrix, while the matrix it self is sorted in increasing order 1-15. So if we enter a 0 between 1, 2, 3, 4, 5, 6, 7, 8, 0, 10, 9, 11, 12, 14, 13, 15. Then program would move things around to get 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0. This program needs to be done in Breath First Search.

Explanation / Answer

The Answer for your question is given below clearly based on your requirement

code:

import pprint
pp = pprint.PrettyPrinter(indent=4)

def puzz_breadth_first(start,end):
"""
Breadth First algorithm
"""
front = [[puzzle]]
expanded = []
expanded_nodes=0
while front:
i = 0
for j in range(1, len(front)): #minimum
if len(front[i]) > len(front[j]):
i = j
path = front[i]
front = front[:i] + front[i+1:]
endnode = path[-1]
if endnode in expanded: continue
for k in moves(endnode):
if k in expanded: continue
front.append(path + [k])
expanded.append(endnode)
expanded_nodes += 1
if endnode == end: break
print "Expanded nodes:",expanded_nodes
print "Solution:"
pp.pprint(path)

def puzz_astar(start,end):
"""
A* algorithm
"""
front = [[heuristic_2(start), start]] #optional: heuristic_1
expanded = []
expanded_nodes=0
while front:
i = 0
for j in range(1, len(front)):
if front[i][0] > front[j][0]:
i = j
path = front[i]
front = front[:i] + front[i+1:]
endnode = path[-1]
if endnode == end:
break
if endnode in expanded: continue
for k in moves(endnode):
if k in expanded: continue
newpath = [path[0] + heuristic_2(k) - heuristic_2(endnode)] + path[1:] + [k]
front.append(newpath)
expanded.append(endnode)
expanded_nodes += 1
print "Expanded nodes:", expanded_nodes
print "Solution:"
pp.pprint(path)

def moves(mat):
"""
Returns a list of all possible moves
"""
output = []  

m = eval(mat)
i = 0
while 0 not in m[i]: i += 1
j = m[i].index(0); #blank space (zero)

if i > 0:
m[i][j], m[i-1][j] = m[i-1][j], m[i][j]; #move up
output.append(str(m))
m[i][j], m[i-1][j] = m[i-1][j], m[i][j];
  
if i < 3:
m[i][j], m[i+1][j] = m[i+1][j], m[i][j] #move down
output.append(str(m))
m[i][j], m[i+1][j] = m[i+1][j], m[i][j]

if j > 0:   
m[i][j], m[i][j-1] = m[i][j-1], m[i][j] #move left
output.append(str(m))
m[i][j], m[i][j-1] = m[i][j-1], m[i][j]

if j < 3:
m[i][j], m[i][j+1] = m[i][j+1], m[i][j] #move right
output.append(str(m))
m[i][j], m[i][j+1] = m[i][j+1], m[i][j]

return output

def heuristic_1(puzz):
"""
Counts the number of misplaced tiles
"""
misplaced = 0
compare = 0
m = eval(puzz)
for i in range(4):
for j in range(4):
if m[i][j] != compare:
misplaced += 1
compare += 1
return misplaced

def heuristic_2(puzz):
"""
Manhattan distance
"""  
distance = 0
m = eval(puzz)   
for i in range(4):
for j in range(4):
if m[i][j] == 0: continue
distance += abs(i - (m[i][j]/4)) + abs(j - (m[i][j]%4));
return distance

if __name__ == '__main__':
puzzle = str([[1, 2, 6, 3],[4, 9, 5, 7], [8, 13, 11, 15],[12, 14, 0, 10]])
end = str([[0, 1, 2, 3],[4, 5, 6, 7], [8, 9, 10, 11],[12, 13, 14, 15]])
puzz_astar(puzzle,end)
puzz_breadth_first(puzzle,end)

Hope This Helps, if you have any doubts Please comment i will get back to you, thank you and please thumbs up

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.