Cornell University

CS 2112 Fall 2020
Object-Oriented Design and Data Structures—Honors

Programming Assignment N: Popinjay Puzzle Solver

Author: Andrew Myers (acm22)
Program usage: java popinjay.Main
Source code: src/main/
Test cases: src/test/

Summary

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.

Challenges and Design Decisions

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.

Major issues

There are no known problems with the implementation.

Specification Changes

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.

Design and Implementation

Architecture

The program comprises six classes, which depend on each other as shown in the following module dependency diagram.

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.

Code Design and Algorithms

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.

Implementation Strategy

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.

Testing

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.

Work plan

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.

Known problems

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.

Comments

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.