# Commits

committed e8a2c29

Initial commit

• Participants

# 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)`
`+`