import heapq
# Helper function to find the position of the blank tile (0)
def find_blank(state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
# Function to generate possible moves from the current state
def get_neighbors(state):
moves = []
x, y = find_blank(state)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, Down, Left, Right
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < 3 and 0 <= ny < 3: # Check bounds
new_state = [row[:] for row in state]
new_state[x][y], new_state[nx][ny] = new_state[nx][ny], new_state[x][y]
moves.append(new_state)
return moves
# Function to calculate heuristics
def calculate_heuristic(state, goal, h_type):
if h_type == "h1":
return 0 # Heuristic h1(n) = 0
elif h_type == "h2":
return sum(1 for i in range(3) for j in range(3) if state[i][j] != 0 and state[i][j] != goal[i][j])
elif h_type == "h3":
distance = 0
for i in range(3):
for j in range(3):
if state[i][j] != 0:
goal_x, goal_y = divmod(state[i][j] - 1, 3)
distance += abs(i - goal_x) + abs(j - goal_y)
return distance
elif h_type == "h4":
return 2 * calculate_heuristic(state, goal, "h3") # Example: Arbitrarily exaggerated heuristic
return float('inf')
# A* search algorithm
def a_star(initial, goal, heuristic="h1"):
open_list = []
heapq.heappush(open_list, (0, initial, 0, [])) # (f(n), state, g(n), path)
visited = set()
while open_list:
_, current, g, path = heapq.heappop(open_list)
visited.add(tuple(tuple(row) for row in current))
if current == goal:
return path + [current] # Return the solution path
for neighbor in get_neighbors(current):
if tuple(tuple(row) for row in neighbor) not in visited:
h = calculate_heuristic(neighbor, goal, heuristic)
f = g + 1 + h
heapq.heappush(open_list, (f, neighbor, g + 1, path + [current]))
return None
# Example usage
if __name__ == "__main__":
initial_state = [
[1, 2, 3],
[4, 0, 5],
[7, 8, 6]
]
goal_state = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]
heuristic_type = input("Choose heuristic (h1, h2, h3, h4): ")
result = a_star(initial_state, goal_state, heuristic_type)
if result:
print("Solution found!")
for step in result:
for row in step:
print(row)
print("---")
else:
print("No solution found.")
Comments
Post a Comment