Commits

johannes committed e8a2c29

Initial commit

  • Participants

Comments (0)

Files changed (1)

File 15-puzzle.py

+#!/usr/bin/python
+
+import random
+from copy import deepcopy
+from heapq import heappush, heappop
+
+EMPTY = 16
+
+start = [
+[ 1,  2,  3,  4],
+[ 5,  6,  7,  8],
+[ 9, 10, 11, 12],
+[13, 14, 15, EMPTY],
+]
+
+def symbol(number):
+	if number == EMPTY:
+		return '  '
+	else:
+		return '%2d' % number
+
+def printboard(board):
+	for row in board:
+		print ' '.join(symbol(num) + ' ' for num in row)
+	print
+
+def find(board, number):
+	for y, row in enumerate(board):
+		for x, current in enumerate(row):
+			if current == number:
+				return (x, y)
+
+	raise RuntimeError('Could not find %d' % number)
+
+def available_moves(board):
+	x, y = find(board, EMPTY)
+
+	if x < 3: yield ((x + 1, y), (x, y))
+	if x > 0: yield ((x - 1, y), (x, y))
+	if y < 3: yield ((x, y + 1), (x, y))
+	if y > 0: yield ((x, y - 1), (x, y))
+
+def apply_move(board, move):
+	(from_x, from_y), (to_x, to_y) = move
+
+	assert board[to_y][to_x] == EMPTY
+
+	board[to_y][to_x] = board[from_y][from_x]
+	board[from_y][from_x] = EMPTY
+
+
+def scramble(board):
+	for i in range(40):
+		move = random.choice(list(available_moves(board)))
+
+		apply_move(board, move)
+
+def board_id(board):
+	id = 0
+	for row in board:
+		for current in row:
+			id = id * 16 + current
+	return id
+
+def is_goal_state(board):
+	return board == start
+
+def est_func_old(board):
+	est = 0
+	for row1, row2 in zip(board, start):
+		for current1, current2 in zip(row1, row2):
+			if current1 != current2:
+				est += 1
+	return est
+
+def est_func(board):
+	est = 0
+	for y, row in enumerate(board):
+		for x, current in enumerate(row):
+			wanted_x = (current - 1) % 4
+			wanted_y = (current - 1) / 4
+			est += abs(x - wanted_x) + abs(y - wanted_y)
+	return est
+
+def solve(start_board):
+	explored = set([board_id(start_board)])
+	est = est_func(start_board)
+	frontier = [(est, est, deepcopy(start_board), [])]
+
+	while True:
+		# The common short names f = g + h translates to
+		#
+		# f: cost_estimate
+		# g: path cost so far (implicit in this code)
+		# h: est(imate) for the rest of the path
+		cost_estimate, est, board, parents = heappop(frontier)
+
+		if is_goal_state(board):
+			return parents
+
+		for move in available_moves(board):
+			new_board = [[c for c in row] for row in board]
+			apply_move(new_board, move)
+
+			new_id = board_id(new_board)
+			if new_id in explored:
+				continue
+
+			new_parents = [m for m in parents]
+			new_est = est_func(new_board)
+			new_cost_est = cost_estimate - est + 1 + new_est
+
+			new_parents.append(move)
+
+			heappush(frontier, (new_cost_est, new_est, new_board, new_parents))
+	
+
+board = deepcopy(start)
+scramble(board)
+printboard(board)
+
+solution = solve(board)
+print 'Solved in %d moves.' % len(solution)
+print
+for move in solution:
+	apply_move(board, move)
+	printboard(board)
+