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 ucs(first_state):
q = []
heapq.heappush(q, (0, first_state, [first_state]))
vis = set()
while q:
cost, 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, (cost + 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("UCS solution\n")
display(ucs(initial_state))
0 Comments