Iterative Deepening A* implementation of 15 Puzzle solver in Python

Question

Introduction

I recently finished the course Mathematical Thinking in Computer Science on Coursera. The sixth module is optional and involves learning about transpositions, permutations, and applying these concepts to solving the 15 Puzzle.

The script shared below is self-contained.

module6/15puzzle.py

def print_board(board):
 """Prints the 15-puzzle board in a 16x16 grid format."""
 line = "+" + "-" * 19 + "+"
 print(line)
 for i in range(0, len(board), 4):
 row = ""
 for j in range(4):
 if board[i + j] == 0:
 row += "| " + " "
 else:
 row += "| " + f"{board[i + j]:2}" + " "
 row += "|"
 print(row)
 print(line)
# Our solved board is a list from 1 to 15 with the empty tile (0) at the end.
# If we want to find a different solved state, we can change this list.
# Remember to update the find_position function accordingly.
solved_board = list(range(1, 16)) + [0]
def is_solved(board):
 """Check if the board is in the solved state."""
 return board == solved_board
def find_position(sorted_list, element):
 """
 Find the index of an element in a sorted list using binary search.
 Note that this assumes that the sorted_list is sorted in ascending order
 with a 0 at the end for the empty tile.
 """
 if element == 0:
 return (
 len(sorted_list) - 1
 ) # The empty tile (0) is always at the end in a solved board.
 # Now we perform a binary search to find the element on the
 # rest of the list.
 left = 0
 right = len(sorted_list) - 2
 while left <= right:
 mid = (left + right) // 2
 if sorted_list[mid] < element:
 # Element is in the right half
 left = mid + 1
 elif sorted_list[mid] > element:
 # Element is in the left half
 right = mid - 1
 else:
 # Element found at mid
 return mid
 raise ValueError(f"Element {element} not found in the sorted list.")
def manhattan_distance(tile, position):
 """Calculate the Manhattan distance of a tile to its solved position."""
 target_position = find_position(solved_board, tile)
 current_row, current_col = divmod(position, 4)
 target_row, target_col = divmod(target_position, 4)
 # Calculate Manhattan distance.
 return abs(current_row - target_row) + abs(current_col - target_col)
def heuristic(board):
 """
 Simple heuristic: sum of Manhattan distances of all tiles to
 their solved positions.
 """
 distance_sum = 0
 for position, tile in enumerate(board):
 if tile == 0:
 continue
 distance_sum += manhattan_distance(tile, position)
 return distance_sum
def evaluate_move_quality(board, empty_position, target_position):
 """
 Evaluate the quality of a move by calculating the change in Manhattan
 distance for the tile being moved.
 """
 tile_to_move = board[target_position]
 if tile_to_move == 0:
 # Invalid move, cannot move the empty tile.
 return float("inf")
 # How far is the tile from its solved position?
 current_distance = manhattan_distance(tile_to_move, target_position)
 new_distance = manhattan_distance(tile_to_move, empty_position)
 # If the new distance is less than the current distance, it is a good move.
 # So negative values rank higher (better).
 return new_distance - current_distance
def apply_move(board, empty_position, target_position):
 """
 Apply a move by swapping the empty tile with the target tile.
 We do not check for validity or out-of-bounds.
 We use this for both applying and undoing moves.
 """
 board[empty_position], board[target_position] = (
 board[target_position],
 board[empty_position],
 )
 return board
def get_valid_ordered_moves(board, empty_position):
 """
 Get all valid moves from the current board state, ordered by their quality.
 """
 # A valid move is a tuple of (move_quality, target_position).
 valid_moves = []
 # Possible moves are up, down, left, or right.
 directions = [-4, 4, -1, 1]
 for direction in directions:
 target_position = empty_position + direction
 # First quick check for out-of-bounds.
 if target_position < 0 or target_position >= len(board):
 continue
 target_row, target_col = divmod(target_position, 4)
 # Second check for valid moves: we cannot be out of bounds in the grid.
 if (
 target_row < 0
 or target_row >= 4
 or target_col < 0
 or target_col >= 4
 ):
 continue
 # If we reach here, the move is valid.
 move_quality = evaluate_move_quality(
 board, empty_position, target_position
 )
 valid_moves.append((move_quality, target_position))
 # Sort moves by quality (lower is better)
 valid_moves.sort(key=lambda x: x[0])
 return valid_moves
class SearchResult:
 """
 Convenience class to hold the result of the search.
 """
 __slots__ = ["found", "path", "next_cost_threshold"]
 def __init__(
 self, found=False, path=None, next_cost_threshold=float("inf")
 ):
 self.found = found
 self.path = path if path is not None else []
 self.next_cost_threshold = next_cost_threshold
def iterative_deepening_search(
 board, empty_position, depth, threshold, path, visited_path
):
 """
 Perform an iterative deepening search to find the solution path.
 """
 if is_solved(board):
 return SearchResult(found=True, path=path[:])
 f_value = depth + heuristic(board)
 if f_value > threshold:
 return SearchResult(
 found=False, path=None, next_cost_threshold=f_value
 )
 board_key = tuple(board)
 if board_key in visited_path:
 return SearchResult(
 found=False, path=None, next_cost_threshold=float("inf")
 )
 visited_path.add(tuple(board))
 next_minimum_threshold = float("inf")
 for move_quality, target_position in get_valid_ordered_moves(
 board, empty_position
 ):
 # Apply the move
 tile_to_move = board[target_position]
 apply_move(
 board,
 empty_position=empty_position,
 target_position=target_position,
 )
 path.append(tile_to_move)
 # Recurse with the new board state
 result = iterative_deepening_search(
 board,
 empty_position=target_position,
 depth=depth + 1,
 threshold=threshold,
 path=path,
 visited_path=visited_path,
 )
 if result.found:
 visited_path.remove(board_key)
 return result
 # No solution but we may have found a better threshold.
 next_minimum_threshold = min(
 next_minimum_threshold, result.next_cost_threshold
 )
 # Undo the move because we are exploring other paths
 apply_move(
 board,
 empty_position=target_position,
 target_position=empty_position,
 )
 path.pop()
 # We have explored all valid moves at this depth without
 # finding a solution.
 visited_path.remove(board_key)
 return SearchResult(
 found=False,
 path=None,
 next_cost_threshold=next_minimum_threshold,
 )
def count_transpositions(permuted_list, sorted_list):
 """
 Count the number of transpositions needed to sort a permuted list.
 Uses cycle decomposition.
 """
 assert len(permuted_list) == len(
 sorted_list
 ), "Lists must be of the same length"
 transpositions = 0
 visited = [False] * len(permuted_list)
 for position in range(len(permuted_list)):
 # Skip if already visited or if the element is already in
 # the correct position
 if (
 visited[position]
 or permuted_list[position] == sorted_list[position]
 ):
 continue
 cycle_length = 0
 current_position = position
 # Keep traversing the cycle until we find a visited element
 while not visited[current_position]:
 visited[current_position] = True
 cycle_length += 1
 # Find the next position in the cycle
 next_value = permuted_list[current_position]
 current_position = find_position(sorted_list, next_value)
 if cycle_length > 0:
 # Each cycle of length k contributes (k - 1) transpositions
 transpositions += cycle_length - 1
 return transpositions
def is_permutation_even(permuted_list, sorted_list):
 """Check if the permutation is even by counting transpositions."""
 transpositions = count_transpositions(permuted_list, sorted_list)
 return transpositions % 2 == 0
def solve(board):
 """
 Checks if the board is solvable and then uses iterative deepening search.
 """
 # First, we need to check if the board is solvable:
 # For a solved 15-puzzle, the empty tile (0) is always at the end of
 # the list. We always need an even number of transpositions to put the
 # empty tile back in the last position. If you make an odd number of
 # transpositions, the empty tile will "change colour" from black to white
 # or vice versa, which is not allowed in the solution. Therefore, we will
 # always need an even number of transpositions to solve the puzzle.
 if not is_permutation_even(board, solved_board):
 print("The board is not solvable.")
 return None
 threshold = heuristic(board)
 empty_position = board.index(0)
 while True:
 path = []
 visited_path = set()
 result = iterative_deepening_search(
 board=board,
 empty_position=empty_position,
 depth=0,
 threshold=threshold,
 path=path,
 visited_path=visited_path,
 )
 if result.found:
 return result.path
 elif result.next_cost_threshold == float("inf"):
 print("No solution found.")
 return None
 # If we reach here, we need to increase
 # the threshold and try again.
 threshold = result.next_cost_threshold
# board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
# board = [5, 2, 3, 4, 1, 6, 7, 8, 9, 11, 10, 12, 13, 14, 15, 0]
# print_board(board)
# print([(tile, manhattan_distance(tile, position))
# for position, tile in enumerate(board)])
# board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15]
# board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 0]
# board = [5, 1, 4, 8, 9, 6, 3, 11, 10, 2, 15, 7, 13, 14, 12, 0]
# board = [2, 6, 3, 4, 9, 11, 7, 8, 1, 13, 14, 12, 5, 10, 15, 0]
# board = [5, 1, 8, 4, 9, 6, 3, 11, 10, 2, 15, 7, 13, 14, 12, 0]
# board = [2, 6, 4, 3, 9, 11, 7, 8, 1, 13, 14, 12, 5, 10, 15, 0]
board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 0]
print_board(board)
# print(evaluate_move_quality(
# board=board, empty_position=14, target_position=15
# ))
# print("Valid moves:")
# valid_moves = get_valid_ordered_moves(board, empty_position=14)
# print(valid_moves)
# apply_move(board, empty_position=14, target_position=10)
# print_board(board)
# apply_move(board, empty_position=10, target_position=14)
# print_board(board)
result = solve(board)
print("Solution path:")
print(result)
print_board(board)

Housekeeping Dependencies

I'm using Python 3 on MacOS. A virtual environment has been set up initially and activated/deactivated when necessary.

# Within the virtual environment from the project root directory:
pip install black isort flake8
# Automatic formatting of imports and source
isort module6
black module6 --line-length=79 
# Static code analysis
flake8 module6

Usage

(.env) $ time python module6/15puzzle.py
+-------------------+
| 1 | 2 | 3 | 4 |
+-------------------+
| 5 | 6 | 7 | 8 |
+-------------------+
| 9 | 10 | 11 | 12 |
+-------------------+
| 14 | 15 | 13 | |
+-------------------+
Solution path:
[12, 11, 13, 15, 14, 9, 10, 13, 11, 12, 15, 14, 13, 10, 9, 13, 14, 15]
+-------------------+
| 1 | 2 | 3 | 4 |
+-------------------+
| 5 | 6 | 7 | 8 |
+-------------------+
| 9 | 10 | 11 | 12 |
+-------------------+
| 13 | 14 | 15 | |
+-------------------+
python module6/15puzzle.py 0.10s user 0.01s system 91% cpu 0.113 total

I'm looking for...

1. Performance is acceptable on an M1 MacBook Pro, although I have not tested this implementation on really tough cases. Are there any overlooked areas here? I'm not interested in using pre-computed databases. A really good search implementation is enough in my opinion.
2. I've mostly avoided using OOP in favour of improving cache friendliness, although it might be entirely irrelevant in case of Python. Are there any ways to improve optimality?
3. Are there any concerns with readability and maintainability?
4. General comments. What would you like this to have or do differently?

• STerliakov: Do you need the shortest solution or any correct solution? If the latter, you can make this a whole lot faster. Cache locality is indeed hardly relevant in Python (you have little to no control over it).
• Hungry Blue Dev: @STerliakov I'm aiming for a short-enough solution. It doesn't matter if it takes 2-3 extra steps compared to the shortest solution.

Answer 1

Bug

get_valid_ordered_moves returns invalid moves. You can't check row overflow by modified index alone, so your check will allow move from cell number 7 ((1, 3) in (r, c) format) to cell number 8 ((2, 0)).

 if target_position < 0 or target_position >= len(board):
 continue
 target_row, target_col = divmod(target_position, 4)
 # Second check for valid moves: we cannot be out of bounds in the grid.
 if (
 target_row < 0
 or target_row >= 4
 or target_col < 0
 or target_col >= 4
 ):
 continue

For any 0 <= n < 15 it is true that 0 <= n%4 < 4 and 0 <= n//4 < 4, so your second check is redundant. And it shouldn't be.

Too bright

This is, I hope, correct:

def find_position(sorted_list, element):
 """
 Find the index of an element in a sorted list using binary search.
 Note that this assumes that the sorted_list is sorted in ascending order
 with a 0 at the end for the empty tile.
 """
 if element == 0:
 return (
 len(sorted_list) - 1
 ) # The empty tile (0) is always at the end in a solved board.
 # Now we perform a binary search to find the element on the
 # rest of the list.
 left = 0
 right = len(sorted_list) - 2
 while left <= right:
 mid = (left + right) // 2
 if sorted_list[mid] < element:
 # Element is in the right half
 left = mid + 1
 elif sorted_list[mid] > element:
 # Element is in the left half
 right = mid - 1
 else:
 # Element found at mid
 return mid
 raise ValueError(f"Element {element} not found in the sorted list.")

But you're always dealing with arrays of the shape [1, 2, 3, ..., n, 0]. Binary search is better than linear, but it could've been just

def find_position(sorted_list, element):
 """
 Find the index of an element in a sorted list using binary search.
 Note that this assumes that the sorted_list is sorted in ascending order
 with a 0 at the end for the empty tile.
 """
 if element == 0:
 # The empty tile (0) is always at the end in a solved board.
 return len(sorted_list) - 1
 return element - 1

or even

def find_position(sorted_list, element):
 """
 Find the index of an element in a sorted list using binary search.
 Note that this assumes that the sorted_list is sorted in ascending order
 with a 0 at the end for the empty tile.
 """
 return (element - 1) % len(sorted_list)

If you insist on bisecting, please at least do import bisect and avoid writing binary search by hand.

Hardcoded sizes

Somewhere you use len(board), but in other places you use literal 4 to denote width and height. Better define

WIDTH = HEIGHT = 4
SIZE = WIDTH * HEIGHT

and never resort neither to literal 4 nor to len(board). This will simplify some of your signatures (and make a few pieces faster).

Format

Kudos for employing black and flake8! Just FYI there's ruff that is much faster and self-sufficient (no affiliation, just a very happy user).

Simplify

Your loop in heuristic can be written with a comprehension (a bit faster as well, but primarily for readability):

def heuristic(board: Board) -> float:
 """
 Simple heuristic: sum of Manhattan distances of all tiles to
 their solved positions.
 """
 return sum(
 manhattan_distance(tile, position)
 for position, tile in enumerate(board)
 if tile != 0
 )

Similarly, tuples are also comparable, so this:

valid_moves.sort(key=lambda x: x[0])

can be just

valid_moves.sort()

as you don't care about relative ordering of moves with equal cost.

Return or in-place

def apply_move(board: Board, empty_position: int, target_position: int) -> Board:
 """
 Apply a move by swapping the empty tile with the target tile.
 We do not check for validity or out-of-bounds.
 We use this for both applying and undoing moves.
 """
 board[empty_position], board[target_position] = (
 board[target_position],
 board[empty_position],
 )
 return board

This function applies in-place modification but also returns a reference to its input. This is confusing - usually such signature indicates copying. Better just drop that return

Naming

By convention, module-level constants are SCREAMING_SNAKE_CASE. So

solved_board = list(range(1, 16)) + [0]

would be usually denoted as

SOLVED_BOARD = [*range(1, 16), 0]

Code organization

Usually it's easier to navigate the file if functions follow some logical ordering. In your case I'd probably put solve first, then transpositions-related functions, then SearchResult, iterative_deepening_search and finally all the helpers. This ordering (higher to lower level) reduces scrolling necessary to find relevant blocks.

Finally, you have some module-level code that runs some example. Please put it under an if __name__ == '__main__' guard so that your module can be imported without side effects.

• Hungry Blue Dev: Yep you're definitely right about the method for getting valid moves. I found that it was incorrectly implemented right after I tried testing this on a few online 15-puzzle generators. Good comment on find_position, will modify. I'll also action the rest of your comments. Thank you!

Answer 2

Here are some minor style suggestions not covered in the previous answer.

Simpler

The print_board inner for loop is slightly simpler if you factor the "| " out of the if/else and absorb the trailing space into the f-string:

for j in range(4):
 row += "| "
 if board[i + j] == 0:
 row += " "
 else:
 row += f"{board[i + j]:2} "

DRY

In the count_transpositions function, this expression appears 3 times:

len(permuted_list)

You could set it to a variable:

num_permuted = len(permuted_list)
assert num_permuted == len(
// etc.

In this case, len is only executed once.

Layout

Thank you for showing us how you ran black to format your code. This is a tad awkward-looking:

if element == 0:
 return (
 len(sorted_list) - 1
 ) # The empty tile (0) is always at the end in a solved board.

I'm guessing black split it up that way due to the long comment at the end of a line of code. Consider moving the comment above the return line for a more natural look:

if element == 0:
 # The empty tile (0) is always at the end in a solved board.
 return len(sorted_list) - 1

Doc

Perhaps I misunderstand the nomenclature, but this print_board docstring seems misleading to me:

"""Prints the 15-puzzle board in a 16x16 grid format."""

The puzzle board is a 4x4 grid. I think "16x16" is a typo.

"""Prints the 15-puzzle board in a 4x4 grid format."""