from collections import deque
import heapq
initial_state = [
[1, 8, 2],
[4, 0, 3],
[7, 6, 5]
]
goal_state = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]
def get_point(state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return (i, j)
return (0, 0)
def get_state(state):
new_states = []
x, y = get_point(state)
# Up
if x > 0:
temp = [row[:] for row in state]
temp[x][y], temp[x-1][y] = temp[x-1][y], temp[x][y]
new_states.append(temp)
# Down
if x < 2:
temp = [row[:] for row in state]
temp[x][y], temp[x+1][y] = temp[x+1][y], temp[x][y]
new_states.append(temp)
# Left
if y > 0:
temp = [row[:] for row in state]
temp[x][y], temp[x][y-1] = temp[x][y-1], temp[x][y]
new_states.append(temp)
# Right
if y < 2:
temp = [row[:] for row in state]
temp[x][y], temp[x][y+1] = temp[x][y+1], temp[x][y]
new_states.append(temp)
return new_states
def serial(first_state):
return tuple(tuple(row) for row in first_state)
def heuristic(state):
h = 0
for i in range(3):
for j in range(3):
if state[i][j] != 0:
goal_x = (state[i][j] - 1) // 3
goal_y = (state[i][j] - 1) % 3
h += abs(i - goal_x) + abs(j - goal_y)
return h
def astar(first_state):
q = []
heapq.heappush(q, (heuristic(first_state), 0, first_state, [first_state]))
vis = set()
while q:
f, g, state, path = heapq.heappop(q)
if serial(state) in vis:
continue
vis.add(serial(state))
if state == goal_state:
return path
for new_state in get_state(state):
if serial(new_state) not in vis:
heapq.heappush(q, (g + 1 + heuristic(new_state), g + 1, new_state, path + [new_state]))
return None
def display(state1):
if state1 is None:
print("No solution found\n")
return
for step, state in enumerate(state1):
print(f"Step {step}")
for row in state:
print(row)
print()
print("A* solution\n")
display(astar(initial_state))
0 Comments