# 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]

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]

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.")

```