Untitled

mail@pastecode.io avatar
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