• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

NxN corner rotation puzzle

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

Lucas Garron

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,557
Likes
92
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#2
I have definitely played a few computer games that act like this, but only have rotating 2x2 parts, if I can remember correctly.

By the way, could we use notation for describing these? For example: You're proposing n|n-1, my last paragraph was referring to n|2.

Can someone group theory this in Mathematica or Sage? :p

Edit: Here's a 4|3 with only four colors.
 
Last edited:
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #3
Thanks for the link, Lucas. I think n|2 puzzles are more commonly considered because they're more practical for physical implementation - you can't make 6x6 turnstiles very easily. By the way, Gripple and Circle Puzzle/Whirligig also appear to be closely related games, although not actually n|m puzzles.

Anyway, I lowered the upper bound for God's Algorithm on 7|6 to 56,701 moves, roughly 1/198 of the original one. This now sounds like something that a human could plausibly solve without macros, if he/she were crazy enough. Which I suppose I am. The main factor that reduced the number was that I replaced my original 121,876-move 3-cycle with a 784-move one. Who said 784-move algs are bad?

The lower bound for God's Algorithm is 70 moves, since (8^69 + 8^68 + ... + 8^0) < 49! < 8^70. (I decided to use QTM on this puzzle; it would be 59 moves HTM.)
 
Last edited:
Joined
Dec 18, 2007
Messages
7,830
Likes
33
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
#4
Simon Tatham has an implementation of this that will let you play with any n|m, with the squares numbered 1 through n^2. (It's "twiddle".) You can also play with orientation, which adds a whole new level of complexity to the puzzle.

I haven't a clue about 7|6 but here's an alg to solve 3|2 with orientation: [dr ur dr' ur' dr, ul]. (This flips two corners in ul by 180 degrees. It seems that a number in a given position can only take on two possible orientations - is this always true? It also seems that there are always an even number of thusly flipped pieces when the numbers are correctly permuted - is this always true?)
 

Lucas Garron

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,557
Likes
92
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#5
It seems that a number in a given position can only take on two possible orientations - is this always true?
On 3|2, yes, because orientation parity for a piece will be its checkerboard parity.
(Should hold for general n|even, right?)

However, note that for 4|3, some pieces can stay in place and achieve any orientation (and all pieces can be moved into such a location).

It also seems that there are always an even number of thusly flipped pieces when the numbers are correctly permuted - is this always true?)
Yes. Take the sum of the piece rotations mod 4. That's invariant after every turn on n|even.

Fun, trivial tidbit: 5|3 has the permutation group of 2-gen (3x3x3 <U, R>) as a sub-group. Quite straightforward, but for some reason it amuses me.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #6
It seems that a number in a given position can only take on two possible orientations - is this always true?
This is true on an n|m puzzle with m even. Proof: If the square is colored like a checkerboard, each piece toggles between white squares and black squares every time it's moved, and it rotates 90 degrees every time as well. So the parity of color is the same as the parity of 90° rotations, and any piece must be off by a multiple of 180° whenever it is in place (or, in fact, on its own color.)
If m is odd, of course, every move rotates a piece in place.

Great program, by the way, but orientable squares on 7|6 are beyond me.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #7
here's an alg to solve 3|2 with orientation: [dr ur dr' ur' dr, ul]. (This flips two corners in ul by 180 degrees.)
Am I misreading this? It seems to me that this alg does a non-identity permutation.

Let me compile a list of which n|m puzzles are and aren't solvable from all permutations (ignoring orientations):
Not solvable: n|m for m = 0, 1, 3 mod 4 (by my earlier arguments on n|n-1.)
Solvable: n|2 for n>2; 7|6; n+k|m whenever n|m is solvable and k is nonnegative (provable by induction, assuming that 1|m doesn't count.)

I also have one more puzzle to add to the list of solvable ones: 11|10. My 7|6 method works fine on 11|10 (and presumably 15|14, 19|18, etc., but I don't feel up to proving that rigorously right now.) I got an upper bound of 406,909 moves for solving 11|10.

Assuming that my method works for all (4k+3)|(4k+2), it looks like we know exactly which n|m can attain every permutation: n|m (for n>m>1) can be solved from every permutation if and only if m is congruent to 2 (mod 4).
 
Joined
Dec 18, 2007
Messages
7,830
Likes
33
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
#8
Ah, I mistyped it, it should be [dr ur dr' ur' dr', ul].

I think it'd be a bit more interesting to think about, rather than which n|m puzzles are solvable from every state, what conditions must hold on the solvable positions for various n|m's.

A little 7|6 stuff:
(ul ur)17 on the 7|6 seems to flip a 5x5 square of numbers upside down.
(ul ur2)26 seems to flip a 4x4 square of numbers upside down.
(dr' ur' (ul ur2)26 ur dr ul' dl' (dr dl2)26 dl ul)2 is a 220-move (htm) 3-cycle between the top-left, midde, and bottom-right numbers.
I don't think this strategy will work quite as nicely on higher orders, though, since on 11|10 the sequence (ul ur2) must be repeated 46 times and flips an 8x8 square. (Also, (ul ur) requires 29 repetitions and flips a 9x9 square.)
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #9
(ul ur)17 on the 7|6 seems to flip a 5x5 square of numbers upside down.
(ul ur2)26 seems to flip a 4x4 square of numbers upside down.
(dr' ur' (ul ur2)26 ur dr ul' dl' (dr dl2)26 dl ul)2 is a 220-move (htm) 3-cycle between the top-left, midde, and bottom-right numbers.
I don't think this strategy will work quite as nicely on higher orders, though, since on 11|10 the sequence (ul ur2) must be repeated 46 times and flips an 8x8 square. (Also, (ul ur) requires 29 repetitions and flips a 9x9 square.)
Looks right. I found the first and last of these algorithms... I didn't try (ul ur2) because it looked too messy. I'm currently too lazy to try out the 3-cycle, but am I correct in assuming it to be a commutator of 180-degree rotations of the top-left and bottom-right 4x4s?

My 7|6 method uses a somewhat more complicated 3-cycle, which can readily be generalized to 11|10 and presumably larger (4n+3)|(4n+2):

Let A, B, and C be rotations of the three 5x5 blocks along the bottom of the 7x7 square, labeled from left to right. Then (AB)^3 is a reflection (not a rotation) of the bottom-left 5x6 rectangle across a vertical axis (ie. it flips each column in place.) Similarly, (BC)^3 reflects the bottom-right 5x6 vertically. So, combining the two, (AB^3)(BC^3) = ABABABBCBCBC = ABABACBCBC, which I will call H, is a flip of only the 5x1 columns in the bottom left and bottom right corners of the 7x7. Then H(ur2)C(ur2)H(ur2)C(ur2) is a 784-move three-cycle.

In my 7|6 method, I used three-cycles to solve all positions of even permutation (if the starting position is an odd permutation, an even one can be reached with one move.) I used setup moves to generate algorithms for all three-cycles of the form (1, 2, i), for i=3...49. This takes at most 13 setup moves, so each three-cycle takes at most 13+784+13 = 810 moves. 70 of these three-cycles suffice to solve the worst-case scenario, in which positions 1 and 2 are correct and the other 47 squares are deranged with 22 swaps and a three-cycle. It's probably justified to assume that 69 3-cycles suffice due to the possibility of choosing different "1" and "2," but I wasn't confident enough about that to include it in my upper bound.

Total number of moves = 1 (parity fixer) + 70*810 (three-cycles) = 56,701. Obviously, your 220-move htm/328 qtm 3-cycle would cut that upper bound quite a bit.
I think it'd be a bit more interesting to think about, rather than which n|m puzzles are solvable from every state, what conditions must hold on the solvable positions for various n|m's.
Conjecture: my conditions for m=0, 1, 3 mod 4 (ie. parity and checkerboard orbits) are sufficient.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #10
Fun, trivial tidbit: 5|3 has the permutation group of 2-gen (3x3x3 <U, R>) as a sub-group. Quite straightforward, but for some reason it amuses me.
I actually just used this to solve a Twiddle 5|3. With a bit of practice, I got a pb single solve of 1:48. (Other than solving the first two rows, there are only two errors to be fixed in the 2-gen solve, both of them easily remedied.)
 
Joined
Dec 18, 2007
Messages
7,830
Likes
33
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
#11
I'm currently too lazy to try out the 3-cycle, but am I correct in assuming it to be a commutator of 180-degree rotations of the top-left and bottom-right 4x4s?
Yes.

My 7|6 method uses a somewhat more complicated 3-cycle, which can readily be generalized to 11|10 and presumably larger (4n+3)|(4n+2):

Let A, B, and C be rotations of the three 5x5 blocks along the bottom of the 7x7 square, labeled from left to right. Then (AB)^3 is a reflection (not a rotation) of the bottom-left 5x6 rectangle across a vertical axis (ie. it flips each column in place.) Similarly, (BC)^3 reflects the bottom-right 5x6 vertically. So, combining the two, (AB^3)(BC^3) = ABABABBCBCBC = ABABACBCBC, which I will call H, is a flip of only the 5x1 columns in the bottom left and bottom right corners of the 7x7. Then H(ur2)C(ur2)H(ur2)C(ur2) is a 784-move three-cycle.
Aha. B seems to cost 34 moves and A/C seem to cost 35 (36 qtm).

In my 7|6 method, I used three-cycles to solve all positions of even permutation (if the starting position is an odd permutation, an even one can be reached with one move.) I used setup moves to generate algorithms for all three-cycles of the form (1, 2, i), for i=3...49. This takes at most 13 setup moves, so each three-cycle takes at most 13+784+13 = 810 moves. 70 of these three-cycles suffice to solve the worst-case scenario, in which positions 1 and 2 are correct and the other 47 squares are deranged with 22 swaps and a three-cycle. It's probably justified to assume that 69 3-cycles suffice due to the possibility of choosing different "1" and "2," but I wasn't confident enough about that to include it in my upper bound.

Total number of moves = 1 (parity fixer) + 70*810 (three-cycles) = 56,701. Obviously, your 220-move htm/328 qtm 3-cycle would cut that upper bound quite a bit.
I expected a method like this. Would it be reasonable to write a computer program to search for (1, i, j) cycle setups for my 220-move cycle? I think this could vastly decrease the number of moves required because then a 3-cycle could be done in just two operations and a 2-2-cycle could be done in three. The worst case (I think) would be a 2-cycle and a 46-cycle of the remaining pieces with 1 fixed, which would take 47 operations.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #12
Would it be reasonable to write a computer program to search for (1, i, j) cycle setups for my 220-move cycle? I think this could vastly decrease the number of moves required because then a 3-cycle could be done in just two operations and a 2-2-cycle could be done in three. The worst case (I think) would be a 2-cycle and a 46-cycle of the remaining pieces with 1 fixed, which would take 47 operations.
Wait, I think you can get a better upper bound here. A 3-cycle that includes the "1" can be done in one operation, a 5-cycle in two, a 7-cycle in three, etc. Your postulated worst-case scenario could be converted into a 49-cycle in one operation. That could be solved in 24 additional operations, for a total of 25.
But what about twenty-four swaps with 1 fixed? I think that would, in fact, take 36 operations.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #13
(dr' ur' (ul ur2)26 ur dr ul' dl' (dr dl2)26 dl ul)2 is a 220-move (htm) 3-cycle between the top-left, midde, and bottom-right numbers.
Wouldn't (ur' (ur' ul2)26 ur dl' (dl' dr2)26 dl)2 work? (It's the mirror image of your alg, with some setup move changes.) That's 212htm/320qtm. A trivial improvement.

I've also been thinking about extending this puzzle idea to infinite sizes. The only moves on an "(aleph_0)|(aleph_0)-1" puzzle, though, would be rotations of the entire plane about (+/-0.5, +/-0.5). So that wouldn't do much. Better idea: with pieces lying on lattice points, define a move as any rotation of one of the "center" squares; that is, a 2k-by-2k square around (+/-0.5, +/-0.5). (Or you could additionally allow rotating (2k-1)-by-(2k-1) squares around (0,0).) Then any finite set of pieces (such as a square around the origin) can be solved by finding whatever necessary piece is/needs to be farthest from the origin, and doing the necessary permutations on a (4k+3)|(4k+2) puzzle which includes all needed pieces.
 
Joined
Dec 18, 2007
Messages
7,830
Likes
33
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
#14
Wait, I think you can get a better upper bound here. A 3-cycle that includes the "1" can be done in one operation, a 5-cycle in two, a 7-cycle in three, etc.
Good point, this implies that a (2n+1)-cycle which does not involve the 1 can be done in n+1 operations (not 2n). If there is a 1 in there it saves one operation. Similarly a pair of cycles of length 2n and 2m, neither of which involve the 1, can be done in a total of n+m+1 operations, or n+m if there is a 1 in either cycle.

Actually, since if we have all (1,i,j) cycles we also have all (7,i,j) cycles, (43,i,j) cycles, and (49,i,j) cycles, these numbers actually apply to any cycles with any of the four corners - so for instance a (2n+1)-cycle can be done in n operations if it includes at least one corner piece, and n+1 otherwise. So the worst case I can think of would be 22 2-cycles not involving corners (this is no worse than 20 2-cycles and a 5-cycle) and two 2-cycles of corners only, which would take 35 operations.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #15
Okay, I found a better 3-cycle. Here's my line of thinking:

Note that (ur ul' ur' ul) moves the center-right 5x5 block two spots to the left (ie., to the center left.) So by rotating this alg 180 degrees and composing the two, we can return the center-right block to its original place. This eight-move alg, ur ul' ur' ul dl dr' dl' dr, actually fixes everything but the 5x1 blocks {2, 3, 4, 5, 6}, {48, 47, 46, 45, 44}, and {37, 30, 23, 16, 9} (where the pieces are numbered left to right, top to bottom.) Those three blocks of five are 3-cycled in that order. Then the same 8-move alg can be rotated 90 degrees (say, clockwise) to affect a different set of fifteen pieces. Only one piece is affected by both algs, so conjugating the two produces a three-cycle.

(ur ul' ur' ul dl dr' dl' dr) (dr ur' dr' ur ul dl' ul' dl) (dr' dl dr dl' ul' ur ul ur') (dl' ul dl ul' ur' dr ur dr') cycles pieces 9, 36, and 44, using 32 moves QTM or 31 HTM.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #16
By the way, that 31/32-move 3-cycle works on larger puzzles too. I just executed it on a 15|14 Twiddle using exactly 32 clicks. It appears that, on large puzzles, setup moves will be far more expensive than actual cycles.

Another point to consider: If the concentric squares of a (2k)|(2k-1) or (2k-1)|(2k-2) puzzle are numbered 1 through n, from the outside to the center, then any given turn will move any given piece at most one ring in or out. Since two adjacent pieces can only be separated by a single move if one is in ring 1 and the other is either in ring 1 or 2, this implies that pieces near the center need to be moved (at least) roughly n times in order to reach the outside and be separated from each other. For example, the center 3x3 block of a 7|6 cannot be broken up in less than three moves.

EDIT: (ur ul' ur' ul dl dr' dl' dr) dr ur' dr' dl' ul' dr' (dr' dl dr dl' ul' ur ul ur') dr ul dl dr ur dr' (28 QTM/26 HTM) cycles 9, 14, and 44. It conjugates the 8-move permutation alg with six setup moves instead of a rotated version of itself.
 
Last edited:
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
Thread starter #17
Inspired partly by the recent paper on asymptotics for God's Number on the NxNxN Rubik's Cube (see Demaine, Demaine, Eisenstat, Lubiw, and Winslow), and partly by an "on this day in 2009" update from facebook, I took a second look at the (4k+3)|(4k+2) puzzle from the standpoint of looking for bounds on God's Number. I ended up finding a lower bound of floor[ln(7(n^2)!)/ln(8)] ~ (2/ln 8) n^2 ln(n) using the standard counting trick, and an upper bound of 6n^3 + 45n^2 - 14n - 104 using a generalization of my 3-cycle method from the 7|6 method discussed previously. Details:

Lower bound:
Let n = 4k+3, so we are considering the n|(n-1) puzzle. We first recall that there are (n^2)! possible positions, all reachable by the method below. So if, for some integer m, we have 1 + 8 + ... + 8^(m-1) < (n^2)!, then God's Number is at least m. In particular, since 1 + 8 + ... + 8^(m-1) < 1/7 + (1 + 8 + ... + 8^(m-1)) = (8^m)/7, we can set m = floor[ln(7(n^2)!)/ln(8)]. Asymptotically, this is just ln((n^2)!)/ln(8), and by Stirling's formula, this is asymptotic to n^2 ln(n^2)/ln 8 = (2/ln 8) n^2 ln(n).

Upper bound:
We begin our solution by applying any single move if we have been given an odd permutation; since each move consists of ((n-1)/2)^2 = (2k+1)^2 four-cycles, this is an odd permutation and will leave us with an even one.

In post #15 above, I gave a 32-move algorithm that, on a general n|(n-1) puzzle for n>2, cycles the pieces at positions (2,2), (n-1,1), and (n,2). Conjugating this by ul' dr, we can cycle (n,2), (1,1), and (n,n) in 36 moves. We denote the (1,1) position as A and (n,n) as B. We will now demonstrate how to perform any three-cycle containing both A and B. The idea here is to move an arbitrary piece (other than A and B) to the (n,2) position using only ur's and dl's, which both fix A and B. We can then conjugate the resulting algorithm with our 36-move cycle to perform the desired cycle.

In order to move an arbitrary piece to (n,2) with only ur's and dl's, it is rather unexpectedly useful to show how to move arbitrary pieces to the center position, ((n+1)/2,(n+1)/2), which we denote O. This is relatively easy to do: in fact, given any piece P (not located at A, B, or O), we can reduce the taxicab distance from piece P to position O in a single move. There's a nice trick to show this. If P is in any column to the right of center (and not in the bottom row), then we perform ur, but stay in the frame of reference of piece P. Then we will see position O moving one spot to the right, and therefore strictly closer to P. Similarly, if P is above O but not in the leftmost column, we do ur'; if to the left of O but not in the top column, dl; and if below O but not in the rightmost column, dl'. Repeating this, we can continue bringing P closer to O in the taxicab metric until it is at O, after no more than n-1 moves. (This upper bound is reached only if P begins in the top-right or bottom-left corner.) In particular, we can move P = (n,2) to O in n-2 moves. Thus, for any P' not at A or B, we can move P' to (n,2) in at most (n-1) + (n-2) = 2n-3 moves, still without affecting A or B. Thus, any 3-cycle including both A and B can be performed in at most (2n-3) + 36 + (2n-3) = 4n+30 moves.

Now we consider how many such 3-cycles are needed to solve the puzzle--again, assuming that we've forced an even permutation using a one-move parity alg if necessary. Suppose, at the outset, that some piece that does not belong at A or B is in one of those two spots. Then we can simply cycle A and B with that piece's destination and solve the piece in one cycle. Thus, we can solve one piece (not including A or B) using only one cycle. The only time this cannot be done is if A and B are either in their correct positions or swapped with each other. If, in such a situation, the puzzle is still not solved, then we will need to cycle with some incorrect piece to displace A or B. Then we may continue solving one piece at a time as before. We continue this until every piece other than A and B is solved, and by parity, this will force A and B to be solved as well. The number of 3-cycles needed is the number of unsolved pieces not including A and B plus the number of nontrivial cycles in the cycle structure of the original position (after fixing parity) that do not contain A or B. Thus, the maximum is (n^2 - 2) + (n^2 - 3)/2 = (3n^2 - 7)/2 three-cycles.

Finally, we multiply the number of three-cycles by the maximum move count of each and add one move for the parity fixer to get the upper bound: 1 + (4n + 30)*(3n^2 - 7)/2 = 6n^3 + 45n^2 - 14n - 104 moves.

Analysis:
Unlike the Rubik's Cube paper, I've only managed to show here that God's Number for the (4k+3)|(4k+2) puzzle is bounded below by a constant times n^2 ln(n) and above by a constant times n^3. I think it would be fairly straightforward to lower the latter constant a bit by showing that the "hardest" cycles can be avoided a positive fraction of the time. But can the upper bound be reduced to something sub-cubic? Better yet, something less than n^c for all c>2?

My hunch is still that God's Number will be asymptotically a constant times the lower bound, as it was found to be in the case of NxNxN Rubik's Cubes. Admittedly, though, this hunch is mostly based on the existing results for cubes, and there are some significant differences between the NxNxN cube and the n|(n-1) puzzle. For example:

- On the NxNxN cube, the number of pieces increases quadratically, and the number of moves increases linearly. On the n|(n-1) puzzle, the number of pieces still increases quadratically, but the number of moves remains constant.
- On the NxNxN cube, the size of an orbit is bounded above by 24. On the n|(n-1) puzzle, however, the size of an orbit increases quadratically: for even n>2, there are two orbits of equal size, and for odd n there is only a single orbit.
- On the NxNxN cube, any piece can be moved to any position within its orbit in O(1) moves. On the n|(n-1) puzzle, O(n) moves are needed. For example, I'll leave it for the reader to check that my taxicab geometry method of moving pieces to the center (see above) is optimal.
- On the NxNxN cube, face turns affect roughly 1/6 of the cube, and slice turns affect almost none of it. On the n|(n-1) puzzle, every move affects (n-1)^2 pieces (or (n-1)^2 - 1 if n-1 is odd), and for large n this is nearly all of the puzzle.

The last two items strongly suggest that a piece-by-piece method is far from optimal, even more so than on a cube. This is reflected by the fact that nearly all of the moves in my method are setup moves. Perhaps some better method could be constructed by combining the setup moves in a manner somewhat analogous to the trick of Demaine et al. Does anyone else have thoughts on this, or other ideas for improving my bounds?
 
Joined
Jun 17, 2006
Messages
654
Likes
1
#18
Simon Tatham has an implementation of this that will let you play with any n|m, with the squares numbered 1 through n^2. (It's "twiddle".) You can also play with orientation, which adds a whole new level of complexity to the puzzle.

I haven't a clue about 7|6 but here's an alg to solve 3|2 with orientation: [dr ur dr' ur' dr, ul]. (This flips two corners in ul by 180 degrees. It seems that a number in a given position can only take on two possible orientations - is this always true? It also seems that there are always an even number of thusly flipped pieces when the numbers are correctly permuted - is this always true?)
Great link!! The cube puzzle is also nice (pick up the blue squares).

Per
 
Joined
Oct 31, 2008
Messages
269
Likes
14
#19
Simon's puzzles

There's an app for Android (and possibly one for Apple devices, don't know) that has this puzzle collection in it.

It's excellent.
 
Joined
Jun 17, 2006
Messages
654
Likes
1
#20
I came to think of a 3D extension. A 3D cube (NxNxN) with (N-1)x(N-1) rotatable corners. But im not just letting it be 6 similar puzzles on the 6 faces of a cube. Instead there would be "bands" on neighbouring faces that cycle and "wrap around" also. A bit like NxN corner rotation and gelatinbrain 10.1 combined ... if that makes sense to anyone :)

Colors or numbers would be fun ...

Per
 
Top