Thoughts and experiences on various topics: puzzles, games, AI, collaboration, music, politics, and whatever else is on my mind

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)

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-down

Symmetric placement of T-piece: in center with stem up

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:

2 Symmetric T-pieces, stems facing in

Placing 2 T-pieces symmetrically, stems facing in

Placing 2 T-pieces symmetrically, stems facing out

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 illustrating all 6 possible symmetric rows (except filled and empty)

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

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

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

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

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

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

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

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)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: