Project 3 Specification

* UtilityTest.java is just a test to make sure that SolutionChecker is installed and working properly. It doesn't do any checking on your Solver, which is your job. When you run it, you should see the output:

0 moves from one board to the same board is valid! Everything is OK.
ERROR - SolutionChecker - checkSolution() - Board after moves does not equal goal board.
0 moves from one board to another is not valid! Everything is OK. (You should see an error message above).
null moves from one board to another is valid! Everything is OK.

The error in the middle is meant to be there; It is an indication that the SolutionChecker has found a problem with the solution being tested. If you look at the corresponding code, which tests to see if an empty SolutionMove array can connect two different boards, you will see that this is the correct behavior.

* The BoardComboGenerator is a fairly general (and complex) tool. However, there are a few special cases that are easy to understand and still produce good boards. For example, passing in arguments "5 4 3 1 1 1 boardFile" will create a 5x4 board (the first two args) with 3 open spaces (the 3rd arg) and all the rest filled with 1x1 pieces (the 4th-6th arguments specify that piece dimensions should be generated in the range (1 to 1)^((1 to 1)/(1 to 1)), which will always be 1). If we pass in arguments "5 4 3 5 1 1 boardFile", a 5x4 board will be generated with 3 empty spaces and piece dimensions in the range (1 to 5)^((1 to 1)/(1 to 1)). That is, pieces will have heights and widths randomly drawn from the range 1 to 5. Finally, if we pass in arguments "5 4 3 2 1 4 boardFile", a 5x4 board will be generated with 3 empty spaces and piece dimensions in the range (1 to 2)^((1 to 1)/(1 to 4)). This will generate dimensions in the range 1 to 2, but will have heavier weighting toward 1 (if the root is 1, then the dimension will be 2; If the root is 2, 3, or 4, then the dimension will be 1).

* UtilityTest.java and the board files utilityTestBoardOne and utilityTestBoardTwo show how to use SolutionChecker. They should be placed right in your slide directory.

* Note that SolutionChecker will always return true on a call to isSolutionValid() when the input SolutionMove array is null, even if there is a valid set of moves to get from the initial board to the final board. A major part of your job on this project is ensuring that solve() only returns null when there really is no set of moves to connect the boards.

* The project is due at 11:59:59 PM on Monday night. That is, it is due as Monday turns into Tuesday.

* A set of helpful testing tools can be found here.
* slide.utility.BoardComboGenerator is meant to be run standalone and will generate a random board and a random rearrangment of the pieces of that board. The program takes 7 arguments: The height of the board, the width of the board, the number of spaces to leave open, the max base of the exponent, the max exponent power, the max exponent root, and the base path for the output files. The height and width of each piece are determined randomly using the formula b^(p/r), where b varies from 1 to the base you specified, p from 1 to the power you specified, and r from 1 to the root you specified. The random board will be put to a file with "Initial" appended to the base path you specified. The rearrangement of that board will be put to a file with "Final" appened to the base path.
* The signature of the constructor for slide.utility.BoardFileWriter is public BoardFileWriter(BoardProducer inputBoard, String outputFilePath). The file is written when a call to public boolean writeFile() is made. That method will output a boolean indicating the success of the write.
* The signature of the constructor for slide.utility.SoultionChecker is public SolutionChecker(BoardProducer initialBoard, BoardProducer finalBoard, SolutionMove[] moves). The correctness of the solution can be determined by calling public boolean isSolutionValid(). A null solution (meaning there is no solution) is considered valid.
* The BoardProducer interface has been updated slightly. If you wrote any of your own implementations of this interface, you will need to update them. A new version of BoardFileSyntaxCheckerAndReader, that impements the updated interface, has been provided.

* You may not do any heavy computation in the constructor of Solver. Anything that isn't initialization (such as traversal of the (conceptual) game tree) may not go in the constructor. In objective terms, your constructor may not take more than 5-10 seconds to complete.

* Your first goal when working on this project should be to design and implement a complete and correct solution. Beyond this, you should try to increase the size and complexity of boards you can solve by decreasing running time and memory usage. Unfortunately, this is not a two part process; There is some base level of efficiency that you must build into the structures and algorithms you use. There is no level of tweaking that will convert a fundamentally O(n^2) algorithm to an O(nlog(n)) algorithm, for example. Part of the challenge in this project (and any complex problem) is figuring out how much time you have to spend on efficiency, and how much time you must spend just getting a working solution.

* Although it is a valid approach, it is not necessarily required that you actually build the game tree / graph we have been discussing lately. Keep in mind that there are other ways to (conceptually) build a tree (through recursion, traversal, etc).
* The BoardProducer and SolutionMove classes are meant primarily to aid in communication between us (the people grading the projects) and you (the people implementing the projects). BoardProducer describes a board configuration in much the same way that I might say, "the board has a height of 4 and a width of 5 and has a 1x2 piece at row 0, column 3, ...". Similarly, an array of SolutionMove objects describes the series of moves that you have found will transform the start board into the finish board. It is unlikely that you will be able to use these classes as part of your internal representation of the board/pieces/moves/etc, as you cannot modify them directly and they aren't very subclass-friendly.

* The row and column in a SolutionMove specify the coordinate of the upper-left corner, at the time the move is being executed, of the piece to be moved.
* The pieces in the ProducerPiece array returned by getPieces() in a BoardProducer implementation may appear in any order.

* Added examples to the Overview section.
* "Board files" corresponding to the examples can be found here. These files are meant as input to the BoardFileSyntaxCheckerAndReader.

* You are responsible for writing a program that can find solutions (or lack thereof) for any game board (within the specified bounds on dimensions) and any initial and final board configuration.
* The solution your program produces need not contain the fewest possible number of moves. Keep in mind, however, that it may take longer for your program to generate solutions with more moves, and we will be testing the performance of your program.
* The game board may not be rotated.

* We highly recommend that you write methods to print out the internal state of your program, including ASCIIgraphical representations of the current board configuration.
* It may also be helpful to write utility programs that automate repetitive / tedious tasks, etc.

In this project, you will be writing a program to play Slide. The Slide game board is broken into a grid and covered in non-overlapping rectangular pieces and open spaces. The pieces may not leave the game board surface and may only move horizontally and vertically into open spaces (ie into non-overlapping positions). The goal is to describe some series of piece moves that will transform the given initial board configuration to the given final configuration. If there is no such series of moves, then the game is declared un-winnable.

Here, each '*' represents a 1x1 piece and ' ' represents open space. The initial and final boards are given. Notice that pieces of the same size are interchangeable. This is a key difference between our version and some of the sliding block games you may have played (including those that use numbers, colors, or portions of a picture to distinguish blocks of the same size). Also notice that this game board is rectangular (3x2), not square.

Here, *'s are used to represent 1x1 pieces, #'s for 1x2 pieces, and X's for 2x2 pieces. Although it is not shown here (for clarity), it is legal for pieces to move more than one space at a time.

You may work in groups of 2 or 3. This project is due at midnight on Monday, August 8th.

Board configurations (such as the initial and final) will be described by some implementation of the BoardProducer interface. This interface provides three methods: getBoardHeight(), getBoardWidth(), and getPieces(). The last method returns an array of ProducerPiece objects, each of which describes the location of one piece.
* The game board may be of any rectangular shape from 1x1 to 255x255 (ie the first two methods will always return values from 1 to 255).
* The pieces described in the array returned by getPieces() will always lead to a valid game board; They will never overlap in an invalid way or extend beyond the edge of the board.
* The pieces may appear in this array in any order.
* Positions on the board not covered by a piece are considered open.
* The "row" and "column" referred to in each ProducerPiece describe the coordinate of the upper left corner of that piece.
* Coordinates are 0 indexed (ie the upper-left-most position on any game board is (0, 0)).

The BoardFileSyntaxCheckerAndReader class is an implementation of the BoardProducer interface that reads a board description from a file. Files used as input to this class must take the following form:
* Fields are space delimited.
* The first line describes the boards dimensions and must contain two fields: The height and width of the board (in that order). This line must be present in a valid board description file.
* Subsequent lines describe the pieces on the board and must contain four fields: The row and column of the upper left corner of the piece and the height and width of the piece (in that order).

Run on its own, the BoardFileSyntaxCheckerAndReader class will check the syntax of the specified file and print out information on the board it describes.

If there is no series of moves that will solve the game, then the output of the solve() method in the Solver class should be null. Otherwise, the output should be an array of SolutionMove objects that describes the transformation from the initial state to final state. The first object in this array should be the first move to be made starting at the initial state, and so on.

When considering a possible solution, keep in mind that pieces of the same size are interchangeable. Pieces or combinations of pieces of different sizes are not interchangeable.

Your job, in short, is to find the most efficient and correct solution that links the input and output.

We recommend that you do this using an exhaustive search of the (conceptual) game tree created by looking at each possible move from each possible board position. Your will focus primarily on making this process efficient.

To prevent endless cycling through the graph of board configurations (and to make that graph into a tree), we recommend that you keep track of board configurations that you have seen before. A good way to do this is with hashing. You may write your own hash function if you like. Alternatively, you may use those provided in java.security (Look at the MessageDigest class) or you might represent your board as a string and use the hashCode() method provided by the String class.

The point of your writeup (contained in the README file) is to describe the overall behavior of your implementation and provide a feel for how you designed and built that implementation. When reviewing your writeups, we will consider how well you explain each aspect of your solution, how much time / effort you spent designing and planning, and how good your solutions are.

Answer these questions and provide any additional information you feel is necessary:
* Begin with a list of the logins of the members in your group.

* Describe your approach to solving this problem. How much time did you spend on design, coding, testing, tweaking, etc?
* Describe the overall operation of your final solution. Include a description of the major data structures and algorithms, the interaction of the various classes and/or methods you wrote, etc.
* Analyze the run time and memory usage of each data structure and algorithm in your solution in various cases (worst case, best case, average case).
* Describe alternative solutions you considered and why / how you ended up with your final solution.
* Describe anything you might try if you had more time and anything you wish you had done differently.

* Describe your testing and debugging strategy. How did you go about making sure that all of your code runs correctly?

* Describe any special aspects of compiling / running your solution.

You should try to test all of your code. We will look at how well you cover the common case and corner cases.

You should write readable and well organized code. This includes writing comments, using descriptive variable names, breaking code up into reasonably sized and topical methods, etc.

* You must put all of your code in files in the slide package or sub packages therein.
* When grading, we will replace all files we have provided with clean versions, with the exception of the Solver class. This means that you may not modify any of these files (with the intention of those modifications being graded).
* The Solver class must have a constructor with signature public Solver(BoardProducer, BoardProducer) and method with signature public SolutionMove[] solve().
* You may create new classes if you like, including subclasses of the provided classes. These files will be compiled into your project.

Submit from the directory containing the slide package directory. You may include any file you like, but need only include Solver.java and any files you have created yourself (including test code and your README file). The project name is 'pj3'. There should be one submission of the project per group.

Each person in the class must also submit their own README file under the name 'pj3-eval'. This file should contain your login, the logins of your group members, a summary of what each person in the group did, a rating (from 1 to 10) of the other members in your group, and any other comments you may have.

35% - Your writeup and the design effort it represents, testing/debugging, code style, comments, etc.
65% - Correctness and efficiency of your implementation.