- Joined
- Mar 21, 2006

- Messages
- 113

- Likes
- 0

- Location
- Kirksville, MO, USA

- WCA
- 2005FERN01

- YouTube
- ravi12346

Thread starter
#1

I was thinking about a new (as far as I know; correct me if you've seen it before) type of flat puzzle yesterday, and it looks quite interesting after studying it for a while. Here's the simplest version of the puzzle: You have a 3x3 square, and the 2x2 ("postage stamp") corners of the square can be rotated through multiples of 90 degrees. The goal is to restore the original permutation of the 9 squares, ignoring the orientation of the individual pieces.

It's not hard to solve this puzzle from any of the 9! possible positions. One method is to solve two opposite corners, then 2-gen the remaining seven with a Sune for "PLL". That led me to consider larger versions of the puzzle. For example, you could try a 4x4 square whose 3x3 corners can be rotated or a 5x5 square whose 4x4 corners can be rotated. Unfortunately, not all permutations of those puzzles can be reached. This is for two reasons:

1) If n is even, an nxn square can be colored like a checkerboard such that every rotation of an (n-1)x(n-1) square takes white squares to white squares and black to black. Therefore, there are two orbits: a white square can't be moved to the place of a black one, and vice versa.

2) A rotation of any square consists of a certain number of 4-cycles (e.g. on the 3x3 puzzle, rotating a 2x2 corner is one 4-cycle of pieces,) and possibly a fixed piece in the center. If n is congruent to 0, 1, or 2 mod 4, then rotating an (n-1)x(n-1) block will do an even number of 4-cycles. That means that every move is an even permutation, and odd permutations cannot be achieved.

However, neither of these restrictions affect nxn puzzles where n = 3 (mod 4), so I started looking into the 7x7 puzzle as the next interesting example. Today I was delighted to confirm that

Open conjecture: for k = 0, 1, 2, ..., can a (4k+3)x(4k+3) puzzle always be solved from every position?

P.S. My apologies if my description of the puzzle is unclear. I can provide a picture if someone really needs one.

It's not hard to solve this puzzle from any of the 9! possible positions. One method is to solve two opposite corners, then 2-gen the remaining seven with a Sune for "PLL". That led me to consider larger versions of the puzzle. For example, you could try a 4x4 square whose 3x3 corners can be rotated or a 5x5 square whose 4x4 corners can be rotated. Unfortunately, not all permutations of those puzzles can be reached. This is for two reasons:

1) If n is even, an nxn square can be colored like a checkerboard such that every rotation of an (n-1)x(n-1) square takes white squares to white squares and black to black. Therefore, there are two orbits: a white square can't be moved to the place of a black one, and vice versa.

2) A rotation of any square consists of a certain number of 4-cycles (e.g. on the 3x3 puzzle, rotating a 2x2 corner is one 4-cycle of pieces,) and possibly a fixed piece in the center. If n is congruent to 0, 1, or 2 mod 4, then rotating an (n-1)x(n-1) block will do an even number of 4-cycles. That means that every move is an even permutation, and odd permutations cannot be achieved.

However, neither of these restrictions affect nxn puzzles where n = 3 (mod 4), so I started looking into the 7x7 puzzle as the next interesting example. Today I was delighted to confirm that

**every permutation of the 49 pieces of a 7x7 square can be reached by rotating its 6x6 corners**. I actually got an initial (constructive) upper bound of 11,228,417 moves (yes, eleven million - this can obviously be reduced by multiple orders of magnitude) in God's Algorithm for the 7x7 puzzle. In other words, the four moves allowed generate the symmetric group on 49 elements, with order 49! ~ 6*10^62. I can provide more details later, but I'll leave you to convince yourself of this for now.Open conjecture: for k = 0, 1, 2, ..., can a (4k+3)x(4k+3) puzzle always be solved from every position?

P.S. My apologies if my description of the puzzle is unclear. I can provide a picture if someone really needs one.

Last edited: Sep 17, 2009