Untitled
unknown
plain_text
a year ago
2.4 kB
2
Indexable
Never
import sys from random import randint from heapq import heappop, heappush COLUMNS = 4 ROWS = 3 dist = [[abs(t // COLUMNS - s // COLUMNS) + abs(t % COLUMNS - s % COLUMNS) if s > 0 else 0 for t in range(ROWS * COLUMNS)] for s in range(ROWS * COLUMNS)] def compute_empty_position(grid): for i, v in enumerate(grid): if v == 0: return i def heuristic(grid): return sum(dist[rv][index] for index, rv in enumerate(grid)) class Node(object): def __init__(self, grid, actions, empty_position, h, last=None): self.grid = grid self.actions = actions self.h = h self.dist = len(self.actions) + h self.last = last self.empty_position = empty_position def neighboors(self): possibilities = [] i = self.empty_position col = i % COLUMNS if col + 1 < COLUMNS and self.last != 2: possibilities.append((i + 1, 1)) if col > 0 and self.last != 1: possibilities.append((i - 1, 2)) if i < (ROWS - 1) * COLUMNS and self.last != 4: possibilities.append((i + COLUMNS, 3)) if i >= COLUMNS and self.last != 3: possibilities.append((i - COLUMNS, 4)) for action, move in possibilities: before = dist[self.grid[i]][i] + dist[self.grid[action]][action] new_grid = list(self.grid) new_grid[i], new_grid[action] = new_grid[action], new_grid[i] new_grid = tuple(new_grid) after = dist[new_grid[i]][i] + dist[new_grid[action]][action] yield Node(new_grid, self.actions + [action], action, self.h - before + after, move) def __lt__(self, other): return self.dist < other.dist def solve(grid): orig = grid[:] visited = set() q = [Node(orig, [], compute_empty_position(orig), heuristic(orig))] while q: node = heappop(q) visited.add(node.grid) if node.h == 0: return node.actions for n in node.neighboors(): if n.grid not in visited: heappush(q, n) print("no solution found!") if __name__ == '__main__': grid = tuple(int(x) for _ in range(ROWS) for x in input().split(" ")) res = solve(grid) for action in res: print(action // COLUMNS, action % COLUMNS)