Problem G
jigsawpuzzle
Is it possible to construct a puzzle from a specified set of identically dimensioned square blank pieces, other than for the number and position of notches and projections on the edges? We will assume that any projection will fit into any notch. Arbitrary rotations with either side being face up is permitted. The four-digit labels as shown in the figure indicate the configuration of notches: ’1’ for a flat side, ’0’ for a notched side, and ’2’ for a side with a projection. With the flip and rotations there are multiple representations that describe the same piece. For example, piece 1201 is equivalent to each of these pieces: 2011, 0112, 1120, 1021, 1102, 2110, and 0211.
This problem adheres to these typical expectations for a puzzle: that each piece has four sides; all adjacent pieces interlock (there are no flat sides except for puzzle edges); the pieces are laid out in rows and columns and form a solid rectangle when assembled; the edges of the resulting rectangles all formed by flat sides. Though puzzles are not typically formed as a single row or column, there is no reason to say that they couldn’t be, so we will allow it.
This problem is fairly difficult to conclusively solve. So instead, let’s determine if it is merely feasible that the puzzle can be constructed according to these progressively restrictive criteria:
-
Are there a valid number of pieces that could form a rectangular puzzle using all the pieces (recognizing there could be more than one possible rectangle)?
-
Are there a valid number of flat edges and corners, as well as types of corners, to build a rectangular puzzle of any of the sets of dimensions allowed by the first criteria?
-
Are there a valid number of notches and projections to build a rectangular puzzle of those allowed by the first and second criteria?
Input
The first line will contain a single integer representing the number of puzzle pieces not to exceed 1000. Each subsequent line, one per piece, will contain a single 4-digit number constructed as shown above, describing a puzzle piece.
Output
Print the answers as "Yes", "No", or "Unsolved" to each of the three questions in order, each answer on a separate line.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1020 1100 1200 1122 1102 2211 |
Yes Yes Yes |
