from collections import deque
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 dfs(first_state):
q = [(first_state, [first_state])]
vis = set()
vis.add(serial(first_state))
while q:
state, path = q.pop()
if serial(state) == serial(goal_state):
return path
for new_state in get_state(state):
ser = serial(new_state)
if ser not in vis:
vis.add(ser)
q.append((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("DFS solution\n")
display(dfs(initial_state))
0 Comments