CPSC 415 - Artificial Intelligence - Fall 2023

Program #2⅔ — Search algorithms

Possible experience: +50XP

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

Note

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.

Overview

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 h₂ (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|
   |11|12|13|14|15|
   |16|17|18|19|20|
   |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:

• .legal_moves(). This method returns a list containing some or all of the values U, L, R, and D indicating which moves are legal to play on the Puzzle in its current state. A "move" means "moving the blank square in a certain direction." So, if .legal_moves() returned ['L','R','U'], then you know that there are three possible moves from the puzzle's current state: moving the blank square left (and thus moving the tile next to it right), moving the blank square right (and thus moving the tile next to it left), and moving the blank square up (and thus moving the tile above it down).
• .move(the_move). This plays the move in question, which must be one of the legal moves returned from the method above. This obviously changes the state of the board, so if you want to hypothetically try a certain move (as you will, zillions of times in your algorithm) you must "deep copy" the puzzle object first:

  from copy import deepcopy
  ...
  copy_of_puzzle = deepcopy(puzzle)
  copy_of_puzzle.move('D')
  

  so that the original board stays as it is.
• .is_solved(). Returns True if the puzzle object, right now, is in the out-of-the-box, solved state.
• .has_solution(solution). Returns True if the puzzle object will be solved if the list of moves passed as an argument are executed on it, in order.
• .verify_visually(solution). Same as above, except that it visually demonstrates the solution being executed, move by move. (Useful for debugging and especially for flexing.)

Your mission

Your job is to write a Python function called solve(). Its first line should look like this:

def solve(p):

where the argument is a Puzzle object. It should return a list of moves which, when executed on the puzzle, leads to a solution.

Getting started

Refresh your repo with the latest contents by doing a git pull operation. (Make sure all your own stuff is committed first!) Then, use the file slider.py as a starting point. Change the comments at the top of your slider.py to include your own name instead of mine, and rename the file to "yourumwid_slider.py". Then, make sure that when you run the program like this:

$ python3 yourumwid_slider.py 4

you get output that looks like this:

-------------
| 4|12| 9| 6|
|13| 7|11| 3|
|14| 1| 8|10|
|  |15| 5| 2|
-------------
Sorry, DULL does not solve this puzzle.

When you get this result, commit the yourumwid_slider.py file to your repo. You are now ready to begin thinking.

Turning it in

You will turn this assignment in by attaching a git bundle to an email. (A "git bundle" is essentially a portable, zipped-up git repo.) The subject line of the email should be "CPSC 415 Program #2.6667 turnin".

To do this, first make sure that all your code is checked into git. Running "git status" and ensuring your workspace is clean is a great way to do that. Then, bundle up your git repo:

$ git bundle create yourUmwUsername.git --all

and send me the yourUmwUsername.git file as an email attachment. (Please do not name it literally "yourUmwUsername.git" Substitute your actual UMW username. For instance, "jsmith3.git".)

Bonus: starting early and often

• +1XP if your repo has your initial commit of yourumwid_slider.py (with the comment changed) on or before October 6th
• +1XP if your repo has at least one non-trivial commit on or before October 7th
• +1XP if your repo has non-trivial commits on at least four (4) different dates

Note: the definition of "non-trivial" is "whatever Stephen deems is non-trivial."

Getting help

Come to office hours, or send me email with subject line "CPSC 415 Program #2.6667 help!!"