Untitled
unknown
plain_text
16 days ago
3.9 kB
1
Indexable
Never
def print_board(state): for i in range(3): print(state[i*3:(i+1)*3]) print() # Function to find the index of the blank space (represented by 0) def find_blank_space(state): return state.index(0) # Function to generate new states by moving the blank space def generate_new_states(state, blank_index): new_states = [] row, col = divmod(blank_index, 3) # Possible moves: up, down, left, right moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] for move in moves: new_row, new_col = row + move[0], col + move[1] if 0 <= new_row < 3 and 0 <= new_col < 3: new_blank_index = new_row * 3 + new_col new_state = list(state) new_state[blank_index], new_state[new_blank_index] = new_state[new_blank_index], new_state[blank_index] new_states.append(tuple(new_state)) return new_states # Function to solve the 8-puzzle using DFS def dfs_solve(state, goal_state, visited, path): if state == goal_state: return path + [state] visited.add(state) blank_index = find_blank_space(state) new_states = generate_new_states(state, blank_index) for new_state in new_states: if new_state not in visited: result = dfs_solve(new_state, goal_state, visited, path + [state]) if result: return result return None # No solution found # Initial and goal states initial_state = (1, 2, 3, 4, 0, 6, 7, 5, 8) # Use 0 to represent the blank space goal_state = (1, 2, 3, 4, 5, 6, 7, 8, 0) # Solve the puzzle using DFS visited = set() solution_path = dfs_solve(initial_state, goal_state, visited, []) # Print the solution path if solution_path: print("Solution found in {} steps!".format(len(solution_path) - 1)) for step in solution_path: print_board(step) else: print("No solution found.") ..second code from collections import deque # Utility function to display the puzzle board def print_board(state): for i in range(3): print(state[i*3:(i+1)*3]) print() # Function to find the index of the blank space (represented by 0) def find_blank_space(state): return state.index(0) # Function to generate new states by moving the blank space def generate_new_states(state, blank_index): new_states = [] row, col = divmod(blank_index, 3) # Possible moves: up, down, left, right moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] for move in moves: new_row, new_col = row + move[0], col + move[1] if 0 <= new_row < 3 and 0 <= new_col < 3: new_blank_index = new_row * 3 + new_col new_state = list(state) new_state[blank_index], new_state[new_blank_index] = new_state[new_blank_index], new_state[blank_index] new_states.append(tuple(new_state)) return new_states def bfs_solve(initial_state, goal_state): queue = deque([(initial_state, [])]) visited = set() while queue: current_state, path = queue.popleft() if current_state == goal_state: return path + [current_state] visited.add(current_state) blank_index = find_blank_space(current_state) new_states = generate_new_states(current_state, blank_index) for state in new_states: if state not in visited: queue.append((state, path + [current_state])) return None # No solution found # Initial and goal states initial_state = (8, 7, 6, 5, 4, 3, 2, 1, 0) # Use 0 to represent the blank space goal_state = (1, 2, 3, 4, 5, 6, 7, 8, 0) # Solve the puzzle solution_path = bfs_solve(initial_state, goal_state) # Print the solution path if solution_path: print("Solution found in {} steps!".format(len(solution_path) - 1)) for step in solution_path: print_board(step) else: print("No solution found.")
Leave a Comment