|
CS 2112 Fall 2020
|
|
|
CS 2112 Fall 2020
|
This assignment required building an automatic solver for the ”Popinjay puzzle“, designed by Prof. Haym Hirsh. This puzzle includes 11 pieces with a roughly J shape, as depicted. They must be fit into a 10×10 square grid. The pieces can be rotated or flipped over. Since the pieces consist of 8 squares, a solution leaves just 100–11×8 = 12 unfilled squares in total.
This assignment offered some interesting challenges, particularly because there are so many possible board configurations. My solver needed to consider more than 300 million board configurations before finding a solution, so efficiency was crucial.
The most challenging part of this assignment was figuring out how to represent the board and the pieces on the board in a way that permitted fast searching. A second key challenge was to exploit the symmetries of the puzzle: it was helpful to reduce the search space by not exploring search states that differed only in the identities of the pieces.
To make the search process fast, I had the solver run on a single board data structure that was updated by adding and removing pieces as the search proceeeded. The board uses a 2D array to keep track of which piece (if any) occupies each location, so that it is quick to determine whether a given piece could fit onto the board. The board also keeps track of the set of pieces currently on the board, so that pieces can be quickly removed from the board. These are maintained in a hash table. There is also an invariant that must be maintained between these two parts of the representation.
To avoid searching redundant board states, I sped up the search by requiring each piece to be located at a position that is lexicographically later than all lower-numbered pieces. This constraint reduces the number of solutions by 11!. The solver gets an additional 2× speedup by preventing the first piece from being flipped over. With these two optimizations, the search for a solution takes less than half an hour.
A final performance improvement was achieved by computing the squares (that is, points) covered by a piece in a lazy fashion. A piece is identified by a shape and an affine transformation that translates, rotates, and flips this piece into position. The affine transformation is only applied to the parts of the shape as necessary.
Although the assignment was just to solve the Popinjay puzzle, I tried to factor out most of the specifics of the puzzle into the main program. Most of the classes are quite generic and could be reused to solve other broadly similar puzzles.
It would have been nice to use multiple cores to carry out the search, but I did not try to implement this. Partitioning the work among the cores would have made the searh algorithm more complex.
There are no known problems with the implementation.
The assignment did not specify what output was supposed to be generated for the puzzle solution, or how diagnostic output should be generated during the search process. My program generates a human-readable ASCII output in which each square of the board is represented either by a single dot (if empty), or a doubled character indicating which of the 11 pieces occupies that square: either 1--9, a, or b. For example, here is a board with a few pieces placed onto it:
11111111117777777777 11. . . . 5555. . 77 1111. . . 55. . 7777 22222222225555555555 22. . 4444444444. . 2222. 44. . . . . 88 . . . 4444. . . . 88 33336666666666. . 88 33. . . . . 6688. 88 33333333336666888888
Every million times a board state is considered, the program prints the current board state to the console to give some sense of how the search is progressing. On my current machine, this means an output about every 5 seconds, which is adequate to reassure the user that useful work is still being done.
The program comprises six classes, which depend on each other as shown in the following module dependency diagram.
The public interfaces to these classes are available as Javadoc output.
The main program, and the search algorithm itself, are found in class
Main. It constructs a Board object that the search
method Main.tile then operates on, using AffineTransform to
construct candidate Pieces from the J-like Shape,
and tries to apply them to the board. A Shape is really a collection of
Point objects, and a Piece transforms these points
using the method AffineTransform.apply.
The search for a solution is implemented as a recursive method Main.tile()
with the following signature:
Maybe<Board> tile(Board b, ArrayList shapes, int k);
Its job is to look for a way to fill in the rest of the provided board using
the shapes starting from index k. The board is assumed to already
contain the first k shapes. The method works by trying all
possible ways to add shape k, and for each candidate placement,
then calling tile recursively with the current shape index
incremented to k+1.
The public interfaces of Shape and Piece use the Iterator
design pattern, because it is convenient for iterating over the points that make up
a shape. A Piece doesn't store its points directly; intead, it keeps
track of the shape it is based on, along with the affine transformation that moves
its points to the location where the piece is. The Piece iterator then
simply instantiates a Shape iterator and transforms each of its
points according to the piece's transformation. This design is a bit more complex
than simply transforming all the shape's points at once, but it improves
performance significantly because often some of the transformed points lie
off the board or on top of another piece, and not all the points need to be
transformed.
The most complex invariant maintained by the code is the invariant on class
Board, implemented as a method classInv(). The
board's pieces and the map from board locations to pieces must agree with
each other. The methods of Board check this invariant using
assertions.
The class AffineTransformation is a core technology
of this implementation. An affine transformation is the composition
of a translation and an arbitrary linear transformation. In this case,
90° rotation transformations are used to rotate a piece around its
origin. The code applies a series of such transformations to reach
all four rotational positions; it then applies a reflection around
the x axis—another affine transformation—and tries all four rotations
again. The linear algebra needed for all these transformations is
all handled in AffineTransformation, simplifying the
rest of the code.
This code was implemented entirely by Andrew Myers, who wrote the documentation and test cases too. The source code for the main program comprises about 350 lines of Java code, including comments.
The implementation strategy was a mix of top-down and
bottom-up. The initial search algorithm was roughly laid down while assuming
that classes like Board and Piece existed. The
implementer than switched to the core geometry classes such as
Shape, Point, and AffineTransform, as
the needs of the client code had clarified their interfaces.
Because the specification of the methods were fairly clear, the search algorithm worked correctly on the first serious try. However, it was slower than desired. A profiler was used to diagnose possibilities for speedup, and it was at this point that lazy transformation of Piece points was implemented.
For this program, the proof is in the pudding to some extent: can the program successfully find the solution to the puzzle? However, this test took around a half hour to complete, so to gain confidence that it would work, the program was also tested by simplifying the puzzle in a couple of ways: by removing one of the pieces, and by removing one of the squares from the J, turning it into an L. Once it worked correctly on these easier puzzles, there was much more confidence that it would work on the full puzzle.
Unit tests were also constructed using JUnit for the core classes of interest,
especially Board, AffineTransformation and
Piece, because they contain interesting code that would be easy to
get wrong. Simple test cases were written for each of the interesting methods
of these classes. The class invariant on Board was particularly
useful for catching small bugs early on.
The test cases can be found in the directory src/test. All of the test cases succeed, and the program as a whole works correctly.
Since this was a solo-authored project, there was no need to divide up
the work. However, with more programmers, it would have been sensible
to work in parallel on some of the core components such as
AffineTransform, Piece, Point, and
Shape.
There are no serious known problems with the existing specification, design, or implementation, though this would be the place to talk about them. The test cases could be a bit more complete, and some of the specifications were written quickly, so there is probably some room for improvement there.
This program was fun to write, and especially satisfying when it finally printed out a solution. The original motivation for solving the puzzle was that Professor Hirsh gave me a wooden version of it. It was so hard to solve by hand that I decided to write a solver.