CPSC 415 - Artificial Intelligence - Fall 2023

Program #2⅔ — Search algorithms

Possible experience: +50XP

Due: Thursday, Oct. 12th, midnight (see also bonus point deadline)


I've entitled this assignment "Program #2⅔" because it is being offered to you in addition to the already-planned six up-to-50XP programs mentioned on the syllabus. Feel free to do this assignment instead of one of the other six, in addition to the other six, or not at all! The choice is yours.


In this programming assignment, you will write an algorithm to solve sliding-block puzzles of the kind discussed in class. I suggest you use the A* search algorithm with h2 (the better of the two heuristic functions discussed in class) but you're an adult and can do whatever.

The Puzzle class

I have provided a Python class called Puzzle to represent the sliding block puzzle you're solving. It's in the file puzzle.py in the class's github repo.

You can instantiate an Puzzle in two ways:

  1. Via the constructor, to generate either a puzzle in its out-of-the-box, solved state. Give it the dimension (height/width) of the puzzle as an argument:
    >>> solved = Puzzle(5)
    >>> print(solved)
    | 1| 2| 3| 4| 5|
    | 6| 7| 8| 9|10|
    |21|22|23|24|  |
  2. From the gen_random_puzzle() class function. This will generate a random (scrambled) puzzle of the dimension you choose:
    >>> scrambled = Puzzle.gen_random_puzzle(5)
    >>> print(scrambled)
    | 8|22|24|18|12|
    |20| 7|10| 9|23|
    |  | 2| 5|14|13|
    | 3|17|11|19|21|
    |15| 6| 4| 1|16|

Here are the important Puzzle methods: