Untitled

 avatar
unknown
plain_text
a year ago
2.9 kB
9
Indexable
import heapq

def h(puzzle, target):
    # Heurystyka - liczba kwadratów w złym miejscu
    return sum(1 for p, t in zip(puzzle, target) if p != t)

def solve(start, target, moves):
    heap = [(h(start, target), 0, start, "")]
    visited = set()
    while heap:
        _, cost, state, path = heapq.heappop(heap)
        if state == target:
            return path
        if state in visited:
            continue
        visited.add(state)
        for move, move_name in moves:
            new_state = move(state)
            if new_state not in visited:
                new_cost = cost + 1
                heapq.heappush(heap, (new_cost + h(new_state, target), new_cost, new_state, path + move_name))

# Początkowe ułożenie i ułożenie docelowe
start_state = [
    [2, 1, 0, 1],
    [0, 0, 1, 0],
    [2, 3, 2, 1],
    [3, 2, 3, 3]
]
target_state = [
    [0, 0, 0, 0],
    [1, 1, 1, 1],
    [2, 2, 2, 2],
    [3, 3, 3, 3]
]

# Definicje funkcji dla każdej dzwigni
def move_a(state):
    new_state = [row[:] for row in state]
    new_state[0], new_state[1], new_state[2], new_state[3] = new_state[1], new_state[2], new_state[3], new_state[0]
    return new_state

def move_b(state):
    new_state = [row[:] for row in state]
    new_state[0], new_state[1], new_state[2], new_state[3] = new_state[3], new_state[0], new_state[1], new_state[2]
    return new_state

def move_c(state):
    new_state = [row[:] for row in state]
    for i in range(4):
        new_state[i] = [state[j][i] for j in range(3, -1, -1)]
    return new_state

def move_d(state):
    new_state = [row[:] for row in state]
    for i in range(4):
        new_state[i] = [state[j][i] for j in range(1, 4)] + [state[0][i]]
    return new_state

def move_e(state):
    new_state = [row[:] for row in state]
    new_state[0], new_state[1], new_state[2], new_state[3] = new_state[1], new_state[2], new_state[3], [0, 0, 0, 0]
    return new_state

def move_f(state):
    new_state = [row[:] for row in state]
    new_state[0], new_state[1], new_state[2], new_state[3] = [0, 0, 0, 0], new_state[0], new_state[1], new_state[2]
    return new_state

def move_g(state):
    new_state = [row[:] for row in state]
    for i in range(4):
        new_state[i][0], new_state[i][1], new_state[i][2], new_state[i][3] = new_state[i][1], new_state[i][2], new_state[i][3], 0
    return new_state

def move_h(state):
    new_state = [row[:] for row in state]
    for i in range(4):
        new_state[i][0], new_state[i][1], new_state[i][2], new_state[i][3] = 0, new_state[i][0], new_state[i][1], new_state[i][2]
    return new_state

# Lista ruchów
moves = [(move_a, "a"), (move_b, "b"), (move_c, "c"), (move_d, "d"), (move_e, "e"), (move_f, "f"), (move_g, "g"), (move_h, "h")]

# Rozwiązanie
solution = solve(start_state, target_state, moves)
print("Sekwencja dzwigni:", solution)
Editor is loading...
Leave a Comment