Using symmetry to solve width 5 Target Tiling puzzles using the T-piece
By symmetric positions, I mean board patterns that have left-right (reflective) symmetry, that is, they are unchanged if the order of the columns is reversed. In a symmetric board position, every individual row will itself be symmetric. But of course not all patterns will be symmetric, so for those non-symmetric patterns, the challenge is to achieve symmetry.
Why is symmetry useful in the first place?
It would be pointless to achieve symmetry unless there were something to be gained by it. In fact there is a lot to be gained:
1. There are far fewer symmetric patterns than non-symmetric ones.
2. It is easier to recognize familiar symmetric patterns.
3. In solving symmetric positions, it is possible to do so while maintaining symmetry!
4. The number of “operators” that maintain symmetry is much smaller than the set of all available operators, so there are fewer choices of what to do at each point (in search terms, the branching factor is smaller).
Exploiting symmetry
Taking advantage of symmetry has two parts: achieving symmetry, and then maintaining symmetry while simplifying and solving. I will discuss each of these after presenting some examples.
Examples of symmetry
Here is one example of a symmetric position with 6 partially filled rows:
Symmetric board illustrating all 6 possible symmetric rows (except filled and empty)
In fact, every possible symmetric row pattern appears in this diagram. There are 6 such symmetric row patterns. Notice that rows 3 and 5 (counting from the bottom) are the cases I discussed last week: Center-hole, and 3-in-the-middle, respectively. I explained how each of these patterns could be cleared by an appropriate macro-operator: the Clear-3 macro for the 3-in-the-middle pattern, and the Clear-Center-Hole macro for the Center-hole pattern. It is possible to learn a “clearing macro” for each of the other 4 row patterns, as well.
Solving While Maintaining Symmetry
The key to maintaining symmetry is to only place T-pieces so that the result is still symmetric. There are 2 cases I find useful:
1. Placing a single T-piece in a symmetric position
This can only be done in 2 ways, since there are exactly 2 rotations of the T-piece that are left-right symmetric, and the piece must be placed exactly in the center (straddling the center the column).
Symmetric placement of T-piece: in center with stem-down
Symmetric placement of T-piece: in center with stem up
2. Place two T-pieces so that together they form a symmetric pattern
Again, there are only 2 ways to do this. The pieces cannot cover any of the center column, since they would both have to cover the same cell, which is not possible. Here are the 2 placement patterns:
Placing 2 T-pieces symmetrically, stems facing in
Placing 2 T-pieces symmetrically, stems facing out
Either of these 2-piece macro-operators will maintain symmetry when they are applied to any symmetric position. Taken together, this set of 4 operators (2 single-piece + 2 double-piece) are sufficient to solve (i.e. Wipe Out) any symmetric starting position. Let’s give names to these operators: T1-Stem-Down, T1-Stem-Up, T2-Stems-In, and T2-Stems-Out, respectively. Looking back to the examples from last week, we can see how the macros Clear-3 and Clear-Center-Hole are actually composed from these 4 operators:
Clear-3 = T2-Stems-In + T1-Stem-Down
and
Clear-Center-Hole = T1-Stem-Down + Clear-3
where “+” means “followed by”. Note that any macro-operator composed from symmetric operators will itself be symmetric!
Solving the Illustrative Symmetric pattern we started out with:
Symmetric board with all 6 possible symmetric rows
We start by applying T2-Stems-In to arrive at:
Result of applying T2-stems-in operator
Next it is natural to apply T1-stem-down (since there is a “T-shaped hole” in the middle of the top 2 rows):
Result after T1-stem-down
Now, the top row is a “3-in-the-middle” which can be cleared by the Clear-3 macro, yielding:
After Clear-3 macro operator
Here the top row is a “Center-Hole” pattern, which can be cleared by the Clear-Center-Hole operator to leave:
AFter Clear-Center-Hole macro
Dropping a T-piece with stem up into the middle of this pattern transforms it into:
After T1-Stem-Up
Filling the 2 holes with 2 T-pieces using T2-Stems-Out, reduces the pattern to 2 cells in just a single row:
After T2-Stems-Out
Almost there! A simple T1-Stem-Down fills the center hole, and yields 2 rows of “3-in-the-middle”:
After T1-Stem-Down
The final two rows, each being examples of “3-in-the-middle”, can be cleared by two successive applications of Clear-3.
That solves the puzzle!! Notice how the positions remained symmetrical at each stage of the solution. Typically rows were cleared one by one.
To be continued …
Next time: Achieving Symmetry (transforming non-symmetric patterns into symmetric ones)
Leave a Reply