CS510 HW ASSIGNMENT 1
CS510 HW Assignment 1
Due date: 10/15/2018
Programming Asignment (100 points)
Part 1
Sliding Brick Puzle
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. You can also find a video here. For the next several
asignments, you wil create a program that can solve the SBP. In this asignment you wil
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, execute the moves or
determine whether we have solved the puzzle.
• A sliding brick puzzle is played on a rectangular w by h board (w cels wide and h cells
tal). Each cel in the board can be either free, have a wall, or be the goal.
• On top of the board (over some of the free cels) 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 cel up, down, left or right. Notice that
bricks collide with either wals 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 have to find a sequence of moves that alows you to move the
master brick on top of the goal cel(s). No other pieces are alowed to be placed on
top of the goal cel(s).
Here is an ilustration of a particular configuration of a SBP (but if you stil do not understand
how the game works, just se this video, or play the game at one of the links above).
CS510 HW ASSIGNMENT 1
Complete this asignment in C/C++ or Python:
1.A: State representation
In this task, you wil write code to represent the game state, load a game state from disk, and
display a game state in the screen. Depending on the programing language you choose, you wil
have to create a class (C++) or just a set of functions (C) for completing this task. We wil
represent the game state as an integer matrix, as shown in this example:
The matrix wil 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 cel is empty
• 1: means that there is a wal
• 2: means that the master brick is on top of this cel
• any number higher or equal than 3: represents each of the other bricks
Thus, as you can se, each piece in the board is asigned an integer: the master brick is asigned
number 2, and the other bricks are asigned numbers starting from 3.
• Write a function that alows you to load a game state from disk. The input to the function
should be just the name of the file. The file format that you have to use is the following:
w,h,
Row 1 of the matrix with values separated by commas,
...
Row h of the matrix with values separated by commas,
You can use the four included files as examples: SBP-level0.txt, SBP-level1.txt, SBP-
level2.txt, SBP-level3.txt.
3
CS510 HW ASSIGNMENT 1
• Write a function that outputs the game state on the screen. For example, if you load the
file SBP-level0.txt, the display state function must output the following to the screen
(pay attention to spaces and newlines)
5,4,
1,-1,-1,1,1,
1,0,3,4,1,
1,0,2,2,1,
1,1,1,1,1,
• Write a function that clones a state. That is that returns a separate state that is identical to
the original one.
1.B: Puzle Complete Check
Write a function that returns true if a given state represent a solved puzzle (i.e. if the master brick
is on top of the goal). Notice that checking this is very easy, since you only have to go over the
matrix, and se if there is any cel with the value -1. If there is, that means that the puzzle is not
solved, if there is not, then the puzzle is solved (since only the master brick can cover the goal
cels). For example, your function should return false with SBP-level0.txt, but true with SBP-
level0-solved.txt
1.C: Move Generation
Since each piece has a unique integer identifier, we wil represent moves as a pair
(piece,direction). Each piece can only move one cel at a time, in any of the four directions. For
example a possible move in the following board is (10,down):
• Write a function that, given a state and a piece, returns a list of al moves the piece can
perform. (notice that the list can be empty). If you are using C++, define a clas and, if
using C, a struct to represent a "move". Fel free to encode the direction (up, down, left,
CS510 HW ASSIGNMENT 1
right) however you want. For example, you can use a character to represent direction
('u','d','l','r'), or an integer. That is up to you.
• Write a function that, given a state, returns al moves that can be performed on a board
(that is, the union of the moves that each individual piece can perform).
• Implement a function 'applyMove' that, given a state and a move, performs the move in
that state.
• Implement a function 'applyMoveCloning' that, given a state and a move, returns a new
state, resulting from applying the move (i.e. first clones the state, and then applies the
move).
1.D: State Comparison
Write a function that compares two states, and returns true if they are identical, and false if they
are not. Do so using the simplest possible approach: just iterate over each position in the matrix
that represents the state, and compare the integers one by one. If they are al identical, the states
are identical, otherwise they are not.
1.E: Normalization
Notice that the previous state comparison function has a problem. Consider the following two
states:
The previous function wil consider these two states as different. However, it's quite obvious that
the states are equivalent. In order to solve this problem, we are going to define a normal form. for
a state:
If we give an index to each cel on the board starting from the top-left corner and going down
row by row from left to right (top-left corner has index 0, the cel right next to it has index 1,
etc.),
CS510 HW ASSIGNMENT 1
then we can asign an index I(b) to a brick b, as the smalest index of the cels covered by b.
Now, a state is in normal form. if, for any two bricks (that are not the master brick) with numbers n
and m such that n nextIdx) {
swapIdx(nextIdx,matrix[j][i]);
nextIdx++;
}
}
}
Where the swapIdx function is:
CS510 HW ASSIGNMENT 1
swapIdx(int idx1,int idx2) {
for(i = 0;i output-hw1.txt”.
5. Use a compresion utility to compres your files into a single file (with a .zip extension) and
upload it to the asignment page.
CS510 HW ASSIGNMENT 1
Grading Rubric:
Item Points
Random Walk (proper algorithm, wel commented) 10
BFS (proper algorithm, optimal solution, wel
comented)
22
DFS (proper algorithm, optimal solution, wel
comented)
22
IDS (proper algorithm, optimal solution, wel
comented)
22
README 9
Output-hw1.txt generated on tux 15
A* (proper algorithm, optimal solution, wel
comented)
10 (extra)
Important: Almost all of the rest of your assignments wil build on top of this assignment.
So, make sure that you do a solid job with its design and implementation. Otherwise, you
wil have problems in the future.
Academic Honesty
You must compose al program and writen material yourself. Al material taken from
outside sources must be appropriately cited. If you need asistance with this aspect of the
asignment, se a TA during office hours.