### Target Tiling – Achieving and Exploiting Symmetry

**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:

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).

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:

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:**

We start by applying **T2-Stems-In **to arrive at:

Next it is natural to apply T1-stem-down (since there is a “T-shaped hole” in the middle of the top 2 rows):

Now, the top row is a **“3-in-the-middle”** which can be cleared by the **Clear-3** macro, yielding:

Here the top row is a **“Center-Hole”** pattern, which can be cleared by the **Clear-Center-Hole** operator to leave:

Dropping a T-piece with stem up into the middle of this pattern transforms it into:

Filling the 2 holes with 2 T-pieces using T2-Stems-Out, reduces the pattern to 2 cells in just a single row:

Almost there! A simple **T1-Stem-Down** fills the center hole, and yields 2 rows of “3-in-the-middle”:

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)**