Untitled
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