Part I: State Representation and Move Generation

Many of you might have played one or another version of the "sliding brick puzzle" $($SBP$).$ If you have not, you can play one here. And if you like it$,$ you can play a rather challenging one here $($although this last one, unfortunately, only runs on Windows machines$).$ For the next two assignments, you will create a program that can solve the SBP$.$

$$ A sliding brick puzzle is played on a rectangular w by h board $($w cells wide and h cells tall$).$ Each cell in the board can be either free, have a wall, or be the goal.

$$ On top of the board $($over some of the free cells$),$ there is a set of solid pieces $($or bricks$)$ that can be moved around the board. One of the bricks is special $($the master brick$).$

$$ A move consists of sliding one of the bricks one cell up$,$ down, left or right. Notice that bricks collide with either walls or other bricks, so we cannot move a brick on top of another. Bricks can only slide; they cannot rotate nor be flipped.

$$ To solve the puzzle, we must find a sequence of moves that allows you to move the master brick on top of the goal. No other pieces are allowed to be placed on top of the goal.

Here is an illustration of a particular configuration of an SBP $($but if you still do not understand how the game works, just see this video, or play the game in one of the links above$)$

In this part, you will just have to create data structures and functions to represent the game state, and perform the various needed operations, such as: determining the set of valid moves, executing the moves, or determining whether we have solved the puzzle. The code for these assignments should be written in Python to run on tux.cs$.$drexel.edu.

Implementation Setup

The various parts of this assignment will require a shell script that can pass an argument to your code allowing us to be able to run your code with a consistent interface. However, you may only use built$-$in standard libraries $($e$.$g$.,$ math, random, etc.$)$; you may NOT use any external libraries or packages $($if you have any questions at all about what is allowable, please email the instructor$).$

To this end, please create a shell script run.sh that calls your code and includes $2$ command$-$line arguments that are passed to your code. For example, a shell script for python$3$ might look as follows:

#$!/$bin$/$sh if $["$$#$"-$eq $3]$; then python$3$ sbp$.$py $"$$$1""$$$2""$$$3"$ elif $["$$#$"-$eq $2]$; then python$3$ sbp$.$py $"$$$1""$$$2"$ else

python$3$ sbp$.$py $"$$$1"$ fi

Your code will need to accept these two arguments and use them properly for each particular command. As you$$ll see in the sections below, running the code will have the general format:

sh run.sh $[]$

Again, this scheme will allow you to test your code thoroughly, and also allow us to test your code using a variety of arguments.

State Representation $(1$ pts$)$

In this task, you will write code to represent the game state, load a game state from disk, and display a game state on the screen. You will have to create a class $($recommended$)$ or just a set of functions to complete these tasks.

We will represent the game state as an integer matrix, as shown in this example:

The matrix will have the same dimensions as the game board, and each position in the matrix has the following meaning:

$-1$: represents the goal

$0$: means that the cell is empty

$1$: means that there is a wall

$2$: means that the master brick is on top of this cell

$$ any number greater than $2$: represents each of the other bricks

Each piece in the board is assigned an integer: the master brick is assigned number $2,$ and the other bricks are assigned numbers starting from $3.$

We will assume the input state will have the following format: $($make sure to export errors in case the input string is wrong$)$

$"$w$,$h$,$

Row $1$ of the matrix with values separated by commas,

$...$

Row h of the matrix with values separated by commas,"

Four different example levels are included with the zip file: SBP$-$level$0.$txt$,$ SBPlevel$1.$txt$,$ SBP$-$level$2.$txt$,$ and SBP$-$level$3.$txt$.$

Your first task is to implement a function that allows you to load a game state from a disk. The input to the function should be just the name of the file.

After that, you should implement a function that can print the board $($game state$)$ in ASCII characters. For example, if you load the file SBP$-$level$0.$txt$,$ the display state function should output the following to the screen:

$5,4,$

$1,-1,-1,1,1,$

$1,0,3,4,1,$

$1,0,2,2,1,$

$1,1,1,1,1,$

For our testing purposes, you should make this print function runnable from the command line with the $$print$$ command as the first argument and the filename as the second argument where the file represents a board configuration or state. Here are two examples of running from the command line:

$>$ sh run.sh print $"$SBP$-$level$1.$txt$"$

$5,5,$

$1,1,1,1,1,$

$1,3,2,2,1,$

$1,0,4,5,1,$

$-1,0,6,7,1,$

$1,1,1,1,1,$

$>$ sh run.sPart I: State Representation and Move Generation

M