In this assignment(IN PYTHON), you are going to write a program that solves the
ID: 3878834 • Letter: I
Question
In this assignment(IN PYTHON), you are going to write a program that solves the eight puzzle problem. You will solve it using 1) [20 points] Iterative deepening depth-first search (100 cases in the given file) 2) [20 points] A* with the Misplaced Tile heuristic (100 cases in the given file) 3) [20 points] A* with the Manhattan Distance heuristic (100 cases in the given file) 4) [20 points] Breadth First Search (only required for graduate students, first 20 cases in the given file) To test your program and analyze the efficiency, you need to test your program on the 100 different input cases. (20 cases for BFS since BFS will take much longer than the others, 100 cases for Iterative deepening depth-first search and the two types of A* searches). The input data is Input8PuzzleCases.txt. This file contains a hundred different states of 8-puzzle. All of the given cases are solvable.
8, 7, 5, 4, 1, 2, 3, 0, 6
7, 8, 6, 0, 2, 5, 1, 4, 3
1, 0, 7, 5, 3, 6, 8, 4, 2
3, 8, 4, 0, 1, 7, 5, 2, 6
6, 1, 2, 7, 0, 8, 5, 4, 3
2, 5, 3, 1, 4, 6, 8, 0, 7
6, 8, 5, 3, 4, 7, 2, 1, 0
2, 7, 8, 0, 1, 5, 4, 3, 6
6, 5, 2, 1, 4, 8, 0, 7, 3
0, 6, 1, 3, 4, 7, 8, 5, 2
8, 5, 1, 7, 3, 2, 4, 6, 0
4, 2, 7, 1, 5, 0, 8, 6, 3
2, 7, 5, 8, 4, 6, 3, 0, 1
6, 5, 8, 0, 2, 1, 7, 4, 3
8, 5, 6, 2, 7, 0, 1, 4, 3
2, 0, 7, 5, 1, 8, 6, 3, 4
4, 2, 5, 7, 3, 1, 6, 8, 0
7, 2, 0, 1, 3, 4, 6, 5, 8
2, 6, 8, 7, 5, 0, 3, 1, 4
1, 5, 0, 4, 7, 2, 6, 8, 3
6, 5, 3, 8, 4, 7, 2, 1, 0
8, 2, 4, 0, 3, 5, 6, 7, 1
5, 4, 2, 8, 3, 6, 0, 1, 7
4, 0, 5, 8, 7, 2, 3, 6, 1
6, 0, 1, 4, 7, 3, 5, 2, 8
4, 5, 3, 1, 0, 6, 7, 2, 8
1, 0, 8, 5, 3, 7, 6, 4, 2
4, 2, 6, 3, 7, 0, 8, 1, 5
8, 4, 5, 7, 1, 3, 2, 6, 0
1, 5, 7, 4, 0, 8, 2, 3, 6
5, 7, 0, 6, 3, 8, 1, 2, 4
2, 3, 1, 6, 7, 0, 5, 8, 4
1, 6, 3, 0, 4, 5, 7, 2, 8
8, 0, 3, 4, 6, 1, 2, 5, 7
6, 2, 4, 8, 5, 7, 0, 1, 3
4, 7, 0, 8, 2, 5, 3, 6, 1
3, 6, 1, 7, 8, 0, 5, 2, 4
1, 3, 4, 5, 2, 6, 8, 7, 0
1, 0, 6, 2, 4, 5, 7, 8, 3
0, 5, 4, 2, 6, 1, 8, 3, 7
8, 4, 6, 3, 2, 7, 5, 0, 1
3, 6, 8, 4, 2, 7, 1, 5, 0
0, 6, 2, 7, 1, 5, 3, 4, 8
3, 5, 6, 0, 1, 4, 2, 8, 7
4, 0, 7, 3, 6, 2, 1, 5, 8
1, 6, 4, 2, 8, 3, 0, 7, 5
6, 0, 1, 3, 2, 7, 4, 5, 8
3, 5, 0, 6, 7, 8, 2, 4, 1
2, 0, 5, 4, 7, 3, 6, 8, 1
7, 2, 0, 4, 1, 6, 5, 3, 8
6, 4, 8, 1, 3, 7, 2, 5, 0
8, 3, 6, 5, 0, 2, 1, 7, 4
6, 2, 5, 8, 1, 3, 7, 4, 0
4, 3, 2, 0, 5, 8, 1, 6, 7
5, 1, 4, 0, 3, 7, 2, 8, 6
3, 8, 5, 4, 1, 7, 0, 6, 2
8, 4, 2, 6, 1, 0, 7, 3, 5
5, 1, 6, 4, 2, 8, 7, 0, 3
4, 6, 5, 3, 8, 7, 2, 0, 1
1, 3, 2, 8, 6, 0, 4, 7, 5
7, 8, 3, 2, 0, 1, 5, 4, 6
5, 2, 4, 8, 1, 6, 3, 0, 7
0, 4, 3, 1, 2, 5, 7, 6, 8
3, 5, 0, 7, 4, 1, 2, 8, 6
4, 7, 0, 5, 6, 1, 2, 3, 8
3, 5, 1, 4, 6, 2, 0, 8, 7
0, 8, 6, 4, 3, 7, 1, 2, 5
7, 4, 0, 2, 5, 8, 6, 3, 1
0, 3, 5, 8, 4, 2, 7, 6, 1
2, 4, 6, 0, 3, 7, 5, 1, 8
6, 4, 7, 1, 3, 2, 8, 5, 0
1, 8, 5, 2, 0, 6, 3, 7, 4
6, 8, 5, 2, 4, 3, 7, 1, 0
2, 4, 3, 7, 1, 8, 6, 5, 0
5, 2, 3, 0, 4, 7, 6, 1, 8
3, 4, 5, 6, 7, 2, 0, 8, 1
4, 6, 5, 2, 7, 8, 0, 3, 1
5, 1, 8, 6, 4, 0, 7, 2, 3
1, 2, 3, 5, 4, 0, 6, 8, 7
2, 0, 6, 7, 8, 4, 5, 3, 1
7, 2, 8, 4, 6, 0, 3, 1, 5
7, 0, 6, 4, 1, 2, 8, 3, 5
3, 5, 4, 7, 0, 6, 1, 2, 8
8, 2, 7, 0, 6, 5, 4, 1, 3
0, 5, 1, 4, 3, 2, 8, 7, 6
4, 1, 8, 7, 5, 0, 3, 6, 2
2, 3, 4, 6, 5, 8, 1, 0, 7
8, 2, 6, 1, 0, 5, 7, 3, 4
5, 4, 2, 0, 8, 1, 7, 3, 6
4, 8, 2, 0, 5, 1, 7, 3, 6
2, 1, 3, 0, 7, 8, 6, 5, 4
8, 6, 4, 0, 3, 5, 2, 1, 7
8, 3, 7, 4, 2, 6, 5, 0, 1
6, 7, 2, 4, 1, 5, 0, 3, 8
7, 4, 1, 5, 3, 2, 6, 8, 0
8, 0, 2, 4, 5, 1, 3, 6, 7
1, 2, 4, 5, 3, 6, 7, 0, 8
6, 5, 1, 0, 8, 3, 4, 7, 2
7, 5, 8, 3, 4, 1, 0, 6, 2
6, 5, 7, 3, 8, 0, 4, 1, 2
Explanation / Answer
from numpy import *
import numpy as np
import queue
import gc
import time
GOAL_STATE = [0, 1, 2, 3, 4, 5, 6, 7, 8]
parent=0
def swap(state,index1,index2):
temp=state[index1]
state[index1]=state[index2]
state[index2]=temp
return state
def move_state(state,move):
next_state=list(state)
index=state.index(0)
if move =='R':
if index % 3 == 2:
return None
next_state = swap(next_state,index,index+1)
elif move=='L':
if index%3 ==0:
return None
next_state=swap(next_state,index,index-1)
elif move == 'U':
if index<3:
return None
next_state=swap(next_state,index,index-3)
elif move == 'D':
if index > 5:
return None
next_state=swap(next_state,index,index + 3)
else:
return None
return next_state
def move(state):
next_state=[]
global parent
ty_state = move_state(state,'R')
if ty_state is not None:
next_state.append(ty_state)
ty_state =move_state(state,'L')
if ty_state is not None:
next_state.append(ty_state)
ty_state =move_state(state,'U')
if ty_state is not None:
next_state.append(ty_state)
ty_state =move_state(state,'D')
if ty_state is not None:
next_state.append(ty_state)
#print("ceng",next_state)
return next_state
def search(list_input):
puzzle=list()
puzzle_cp=set()
puzzle_cp.add(tuple(list_input))
puzzle.append(list_input)
explored = set()
#puzzle_cp.add(list_input)
t=0
while puzzle:
#print("puzzle:", puzzle)
c_state = puzzle.pop()
puzzle_cp.remove(tuple(c_state))
explored.add(tuple(c_state))
if c_state == GOAL_STATE:
print("step",len(explored))
#free memory
del puzzle
del explored
del puzzle_cp
return c_state
# reversed because avoid BUG
for move_state in reversed(move(c_state)):
if tuple(move_state) not in explored and tuple(move_state) not in puzzle_cp :
#print(move_state)
puzzle.append(move_state)
puzzle_cp.add(tuple(move_state))
return None
with open('Input8PuzzleCases.txt') as f:
listRow = f.readlines();
for i in range(100):
start_time=time.clock()
#string to list
list_input = listRow[i].split(",")
list_input = [int(x) for x in list_input]
print("print list:",list_input)
#state=search([4, 3, 1, 0, 2, 6, 7, 5, 8])
state=search(list_input)
while state is None:
gc.collect()
print("false")
break
#state=search(list_input)
print("print list successful:",i,":",state)
print("time:",time.clock()-start_time )
print("================================================")
gc.collect()
#listinput = np.matrix(listRow[i])
#a= listinput.reshape((3,3));
#
#print(a)