Block_Puzzle_Solver

Team Members:​Lilly Chou, Rashmi Vidyasagar, Joanna Chau

Puzzle Representation Blocks are represented by their top-left coordinate and their bottom-right coordinate. For example, the block at the top-left corner of the tray configuration above has its top-left coordinate at 0 0, and has its bottom-right coordinate at 1 0. Thus, this block is represented by the line:

0 0 1 0 The 2 × 2 block in the tray configuration above is represented by the line:

1 1 2 2 Tray configuration files represent trays and all of the blocks contained in a tray. The first line of every tray configuration file will have two positive integers: the height and the width of the tray (separated by a single space character). All subsequent lines of each tray configuration will have four space-separated non-negative integers that represent a block. Blocks can appear in the tray configuration file in any order. You may assume that the length and width of a tray are no greater than 256 each.

The tray configuration on the previous page can be represented by a file containing the following:

5 4 0 0 1 0 0 3 1 3 2 0 3 0 2 3 3 3 1 1 2 2 3 1 3 2 4 0 4 0 4 1 4 1 4 2 4 2 4 3 4 3

Goal configuration files are similar to tray configuration files, except they don’t specify the dimensions of the tray. Instead, each line of a goal configuration file specifies the position of a block. In the example above, if our goal was to move the 2 × 2 block two spaces down in the tray configuration above (and we didn’t care where any of the other blocks were), our goal configuration file would contain the single line:

3 1 4 2 If we also wanted to have other blocks at other positions, we would have more lines in our goal configuration file. Note that if there were multiple 2 × 2 blocks in the initial configuration, any of the 2 × 2 blocks can be at the specified position to satisfy the goal file example above.

Each move is represented by four non-negative space-separated integers. The first two integers make up the current top-left coordinate of the block we want to move. The last two integers make up the top-left coordinate of where we want the block to be after we execute the move. In the example above, if you wanted to move the 2 × 2 block up one space, you would output the move:

1 1 0 1 If you wanted to make more moves, your program would output more lines of moves.

Division of Labor We worked on the project as a group with everyone present at every meeting. Together, we came up with potential algorithms to solve the problem and rotated typing of the code. We decided to work in this manner to prevent inconsistencies and to ensure that the different classes and methods all worked together properly. Additionally, doing the project this way allowed us to all learn together! Regarding the division of the report, Lilly wrote up the design for the entire algorithm, Joanna wrote up the experimental results, including graphics, and Rashmi wrote up the program development, disclaimers, and improvements that could be made to this project.

Design Overview The logic of our implementation is divided into two parts: Solver.java is responsible for creating Tray objects, generating next moves by creating new Tray objects with new block locations, and printing out the solution; Tray.java is the representation of the puzzle board by storing information about the blocks on the board through Block objects. Our solution make use of class Block to represent the blocks in the puzzles. Every Block object stores information about its location and size, as well as its priority and the type of Tray it exists in (see Class Block). Our Tray class contains information about the its parent (previous move) and children (next possible moves) Trays, location of the blocks, and various data structures containing information about its blocks.

Program Development Initially, we created a simple outline of the classes we would write, along with their instance variables and methods. Then, using this outline, we wrote up the basic framework of our three classes, Solver, Tray, and Block. We decided to focus on Tray and Block first, since those would be the building blocks of our program. We then came up with a means of determining whether a block could move to certain spaces or not, which led to the creation of our boolean[][] blocks variable in the Tray class, which represents an entire board. If the value at any position blocks[i][j] was false, that meant that it was an empty space on the board, otherwise, there was a block in that location. We used this to determine a Block’s surroundings and to write the method, getValidMoves,​which determines whether any Block in a Tray could move up, down, left, or right. We considered these moves to be the children of the current Tray and created a new variable in the Tray class, a HashSet myChildren, that stored all of a Tray’s possible moves. The hashcode we used to store the Trays in our HashSet was dependent on that of the Block class. Since each ArrayList is supposed to have its own unique hashcode, we decided that the hashcode for Block should be the hashcode of the ArrayList of the Block’s coordinates and that the hashcode for the Tray class should be the sum of the hashcodes of all of the Blocks in it. After creating this basic implementation, we proceeded to the Solver class, where we implemented the m​ove(​) method. Initially, we just created a Stack fringe, which took in the initial Tray configuration. This Tray would then be popped off and we would check if it was the goal configuration. If it was,we would return it, otherwise we would add all of the Tray’s children to the fringe and add the current Tray to the HashSet visited to prevent us from looking at it again and causing an infinite loop. This appeared to work decently for most of the easy puzzles, but it was too slow for the medium and hard puzzles, meaning it needed to be optimized. At this point, now that our algorithm worked, we had to figure out how to improve it and make it more efficient. We decided to implement a PriorityQueue for the fringe, instead of the Stack, where the priority was determined by a Tray’s Blocks’ distances to the goal configuration’s Blocks. The Trays with smaller distances would have higher priority, so they would be popped off first. This would allow us to find the shortest path to the goal configuration faster and more efficiently. However, although this version of our program improved our project’s runtime, it still wasn’t passing all of the tests. To further improve our implementation, we created a r​eset(​) method that would set certain instance variables of a Tray object to null after the Tray had been analyzed and moved to the HashSet visited. This would prevent our program from holding on to information it no longer needed and helped better our Solver’s runtime for the harder puzzles. However, even after all of these modifications, we were still having issues with some of the hard puzzles. Upon inspection, we learned that our Solver was having a difficult time determining the solution to Trays of many one­by­one Blocks. As a result, we created a separate method to handle the case where the initial configuration was a large board full of one­by­one Blocks. By having a method that could handle this case specifically, we were able to get those series of hard puzzles to work quite quickly. However, during this whole process we noticed an issue when our Solver tried to determine the solution to the 100 x 100 puzzle with multiple one­by­one Blocks. When we ran our program, our HashSet visited did not contain as many items as we expected. After performing some tests, we determined that our hashcode function was the problem. There were several Trays that had the same hashcode, so whenever we checked if the HashSet visited contained some new Tray, if there was already a Tray in it with the same hashcode, the new Tray would not be added, even if its configuration was completely different. This meant that the hashcode of the ArrayList was not completely unique, so the hashcode of our Block class would have to be modified. We then decided that the best alternative would be to parse the four values in the ArrayList of coordinates and make that the new hashcode. Additionally, we modified the hashcode of Tray such that it used a multiplier, further reducing the chance of collision. We ran the puzzles again and many of them worked, but now there was an different error. When the size of the Tray was greater than or equal to 100 x 100, the Block’s hashcode function could not parse the value we were giving it into an Integer, because we were providing it with a value that contained more than ten digits. (The Java class, Integer only supports values up to 2^31 ­ 1.) As a result, we had to modify our hashcode once again. This time, we made two separate cases: one where the size of the board was less than 100 x 100 and the other where it was greater than or equal to 100 x 100. (Our program determined whether the size was greater than this bound by using the boolean BIG in the Block class. The size of the Tray was passed into the Block’s constructor and if it was greater than or equal to 100 x100, BIG was set to true.) If the size was less than 100 x 100, our hashcode would use the previous method (parsing the four values together). Otherwise, it would parse the first three values together, modifying those values by certain criteria, such as leading 0’s if the value was less than 100, etc. As soon as this was adjusted, all of our tests ran successfully, verifying all of the easy, medium, and hard puzzles. We decided to build the program in this sequence, because it made the most sense logically. In the beginning, we wanted to make sure we were approaching the problem correctly, so we didn’t really focus on optimization. We primarily focused on writing a program that could solve at least the easy sliding block puzzles. After accomplishing this portion of the project, we started focusing on optimization and gradually made modifications to increase the speed and efficiency of our program. However, all the while, our algorithm remained unchanged. We simply added to it when necessary, and made certain other aspects more time and memory efficient. We tested our program primarily by looking at some of the individual puzzles given in the easy, medium, and hard folders. We would run our program and see which puzzles didn’t work; then using the debugger and the “run configurations” option, examine what exactly our program did with each of those puzzles individually. This allowed us to better understand what our code was doing and how to fix whatever problems we were having. Additionally, we used the function .g​etCpuTime(​) to determine the CPU time our program was taking for different puzzles. This gave us a good estimate of our program’s time efficiency for different types of puzzles, allowing us to better optimize our project.

Disclaimers Our hashcode function for the Block class, and thus the Tray class, was not entirely bulletproof. While creating our algorithm and writing code, we found that for Trays with dimensions greater than or equal to 100 x 100, our hashcode had some issues. At this point, we had decided to use the coordinates of each Block concatenated into a String, which was then parsed into an Integer to represent the hashcode. However, this became a problem when the Solver tried to solve puzzles that were of dimensions 100 x 100 or larger, because Integers cannot hold values where the total number of digits is greater than 10. (The maximum value for an Integer in Java is 2^31 ­ 1.) Because of this, we made a separate hashcode for this specific case which also depended on the coordinates, but rather than parse a concatenated String of all four values in the ArrayList of coordinates, it parsed the String of the first three values, such that each of the values fulfills certain criteria, such as leading 0’s for values less than 100, etc. This appears to work with all of the test cases given, but there is chance of collision, especially as the Trays get larger. (Tray’s hashcode function is dependent on that of Block.)

Improvements If we were to make an improvement to speed up our program, we would come up with a better, more generic, fool­proof hashcode. At the moment, our hashcode still appears to have some collisions, but we would ideally like to fix this such that each Tray, unless it has the exact same dimensions and the exact same Block positions, would have a different, unique hashcode. This should allow our program to speed up significantly, because when comparing Blocks and Trays, we would only need to compare hashcodes (Integers), rather than the objects themselves, which would greatly reduce the amount of memory taken by running the program and the amount of time needed for the program to solve the puzzle. Evidence of this was gathered from running different implementations of our code. Previously, for our Block class’ .e​quals​method, we compared the ArrayList of coordinates themselves and the program appeared to take longer. However, when we started comparing hashcodes, the program was able to determine a solution for the puzzle (if there was one) much faster than before. We encountered the same scenario with the Tray class as well. In addition, in our current implementation, we have two cases for our hashcode: one for Trays with dimensions greater than or equal to 100 x 100 and the other for Trays with dimensions less than 100 x 100. Ideally, we would have only one version of calculating the hashcode for a Tray, no matter what its size, which would clean up our code.