Nokia Rotation puzzle
Kevin Buzzard
I looked and looked through past posts but couldn't find one that
mentioned it---on the other hand, it's a game that so many people in
Europe are currently carrying around in their pockets that it seems
very surprising that no-one has asked about it here. Perhaps it's
because most people in this NG seem to be American, and I hear
that in the USA, the reason for
carrying the game around in your pocket hasn't really caught on yet.
I'm talking about the Rotation game that comes with the newest Nokia
mobile phones. It's, if you like, a variant of the 15 puzzle, or
the rubik cube, puzzles of that nature: you have a bunch of pieces
and a certain way you can move them and you have to sort them out.
You can actually play it on Nokia's web site at
and click on "play rotation".
For those of you who can't be bothered to do this, here's a description
of the puzzle. The integers from 1 to n^2 are arranged randomly in
an n x n grid---there are various levels that you can set the game
to, and n varies. For example, in the easiest game, n is 3.
The object of the game is to sort the integers out until they are
arranged in the obvious order, with the top row 1...n and the
bottom row finishing with n^2. So now all I have to do is to
tell you the moves you can do. This is the cute part. First
I'll explain the easier levels. Here, you can "rotate" (either
clockwise or anticlockwise, for what it's worth) any four
integers that sit in a small 2x2 square (i.e. the four points
where two consecutive rows meet two consecutive columns). So for example,
from the position
123
456
798
you could, for example, rotate the 1245 square clockwise to get
413
526
798
or any one of seven other things (four 2x2 squares, two
choices of rotation direction).
This is a cute puzzle but is rather easy to solve. All one
really has to do is to work out how to switch two numbers
and you're home. So I played the first few levels of this
game, where the grid got bigger but the rules remained the same.
n went from 3 to 6. The 6x6 game is really no harder than the 3x3
one, it just takes a lot longer. There are 25 choices of square
in the 6x6 game but basically if you can switch two numbers you're home,
and switching two numbers is clearly at least as easy in the 6x6
case as in the 3x3 case.
Not particularly hard so far. Then the bomb hit. Moving up to level 5
I was presented with a 4x4 grid again but this time I could only
rotate the eight numbers on the boundary of a 3x3 square
(where by a 3x3 square I mean where 3 consecutive rows meet
3 consecutive columns). So for example, the eight valid moves from
the position
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
would be to cycle round either (1,2,3,7,11,10,9,5),(2,3,4,8,12,11,10,6),
(5,6,7,11,15,14,13,9) or (6,7,8,12,16,15,14,10). Of course, if you've
got the numbers into this position you wouldn't make any moves because
you would have won, but the phone presents you with a random arrangement
of 1-16 at the beginning, so e.g. the position I'm looking at now is
15 2 11 13
1 14 16 3
6 8 4 12
9 10 7 5
and I could, for example, cycle 15->2->11->16->4->8->6->1->15.3
I played with this for a while and got nowhere. Being essentially
lazy, and also having my laptop to hand which contains a computer
algebra program which is very good at solving this sort of thing
("magma", in case anyone is interested), I wrote a few lines of
code in its language to see what it thought of the problem.
The first question I asked it was whether there were any restrictions
on the positions one could get to from the final position, or
whether any position was "legal". I was told that any position was
legal:
> G:=PermutationGroup<16|(1,2,3,7,11,10,9,5),(2,3,4,8,12,11,10,6),
> (5,6,7,11,15,14,13,9),(6,7,8,12,16,15,14,10)>;
> #G;
20922789888000
> Factorial(16);
20922789888000
Next I asked it to solve the position gotten by switching 15 and 16:
> f:=InverseWordMap(G);
> g:=G!(15,16);
> sol:=f(g);
> #sol;
847
That's rather bigger than I was expecting. The solution it found
is 847 moves long. I won't include it here.
I should stress right now that the computer
is *certainly* not claiming it's the shortest solution---finding
the shortest solution is a very hard computational problem,
as far as I know. But 847 moves is too many for my brain :-)
So that leaves me with the question: is the game at level 5
or above (higher than 5 is just bigger boards with the same
3x3 square rotations) actually possible to solve without a computer?
I thought some folks here could try :-)
Finally, apologies if this is all common knowledge, I deserve the
flaming if it is.
Kevin
Carl G.
http://www.microprizes.com/mp52.htm
When I wrote this puzzle, I was concerned with the puzzle becoming too
difficult. I investigated several different sizes, shuffling methods, and
goals. In my original puzzle, I had the bear on each square wearing a shirt
with a different color. Each square also had a different color. The
objective was to get the matching bears onto the right squares using the
allowed moves (analogous to placing the digits 1 to n^2 in order). While
not impossible, I decided that the puzzle was much too difficult for the
average visitor to solve. I reduced the colors to just two (blue for boy
bears, pink for girl bears), and the puzzle became much easier (although
still challenging enough for many people). With two colors, every pattern
on the 4 by 4 grid can be changed into any other pattern in 10 moves or less
(see my web page for a definition of "move"). If I recall correctly, using
all 16 colors required less than 50 moves to solve.
The "level 5" puzzle you described seems like it would be the same as the 16
color case, except that my puzzle also allowed certain 2x2 squares to
rotate. I would guess that your puzzle can also be solved in less than 50
moves. A computer solution can be found rather quickly. The game on my web
site actually finds the shortest solution every time the "hint" button is
pressed. I suppose that determined individuals could solve the puzzle using
the same algorithm (without the computer), but I would guess they would
solve them using a process similar to the way they solve a Rubik's cube. My
guess is that the puzzle is no harder to solve than a Rubik's cube.
Carl G.
Kevin Buzzard wrote in message <8p62po$78a$1...@newstest.cc.ic.ac.uk>...
Kevin Buzzard
> The game reminds me of my "Square Dance" puzzle at:
> http://www.microprizes.com/mp52.htm
Yes!
> The "level 5" puzzle you described seems like it would be the same as the 16
> color case, except that my puzzle also allowed certain 2x2 squares to
> rotate. I would guess that your puzzle can also be solved in less than 50
> moves.
I think that this would sit much more happily in my brain if someone
were to actually show me how to do a transposition in fewer than 50 moves.
> A computer solution can be found rather quickly.
Either I'm misunderstanding something, or this should say
something like "assuming it _is_ possible to do a transposition in
fewer than 50 moves, a computer solution can be found rather quickly".
As I mentioned in my original post, the only method I know to
transpose two pieces takes over 800 moves. Perhaps your idea of
how easy the game is has been skewed by the fact that you are
allowed to rotate some 2x2 squares in your game? Why not try the
java version on the nokia site for a while and then re-evaluate
your opinion? If you could show me how to swap 1 and 2 whilst
leaving the other 14 numbers fixed, in a reasonable amount of
moves, then you're right, it's no more difficult than a rubik cube.
But all the "moves" I knew on the cube when I was a kid were
20 moves or less, as I recall. If there is an easy method of
switching two numbers in this game then I shall re-evaluate
my opinions of it, but I'm not sure I could commit a string
of 800 moves to memory :-)
Kevin
Tom Collins
:-)
--
Tom Collins
tcol...@america.net
"Kevin Buzzard" <buz...@ic.PUZZLE.ac.ELZZUP.uk> wrote in message
news:8p62po$78a$1...@newstest.cc.ic.ac.uk...
: First of all, deepest apologies if this question is asked week in, week
Carl G.
Kevin Buzzard wrote in message <8p6h5j$b92$1...@newstest.cc.ic.ac.uk>...
>Carl G. <cgi...@microprizes.com> wrote:
>> The game reminds me of my "Square Dance" puzzle at:
>
>> http://www.microprizes.com/mp52.htm
>
>Yes!
>
>> The "level 5" puzzle you described seems like it would be the same as the
16
>> color case, except that my puzzle also allowed certain 2x2 squares to
>> rotate. I would guess that your puzzle can also be solved in less than
50
>> moves.
>
>I think that this would sit much more happily in my brain if someone
>were to actually show me how to do a transposition in fewer than 50 moves.
>
>> A computer solution can be found rather quickly.
The solution is found quickly for the two color puzzles (the "hint" button
on my puzzle proves that), but I am probably mistaken about solving 16 color
(number) puzzles quickly using a "brute force" algorithm.
>
>Either I'm misunderstanding something, or this should say
>something like "assuming it _is_ possible to do a transposition in
>fewer than 50 moves, a computer solution can be found rather quickly".
>As I mentioned in my original post, the only method I know to
>transpose two pieces takes over 800 moves. Perhaps your idea of
>how easy the game is has been skewed by the fact that you are
>allowed to rotate some 2x2 squares in your game?
Partly, but a much larger time increase is due to the number of colors (my
puzzle has only two, while the Nokia puzzle has 16). Even if the 2x2
rotations were not used, the two-color puzzles could be solved in less than
a dozen or so moves. I couldn't find the program that I used to solve the
16 color puzzle, so I can't confirm that the solutions were always less than
50 moves. It is quite possible that the program took a long time to solve
the 16 color puzzles (one reason why I decided to simplify the puzzle).
There are 16! (about 20 trillion) possible puzzle patterns in a 16 color
puzzle. Since each move can create around 7 new patterns (there are eight
moves at each step, one move returns to the previous pattern). I would
guess that the number of patterns that can be reached after n moves to be on
the order of 7^n. This would mean that any solution should take around
log(16!)/log(7), or about 16 moves. I think that it is unlikely that 800
moves would be required. Even if the number of patterns that can be
reached only grows as 2^n, the number of moves would still be under 50. The
actual number of patterns that can be reached is less than 7^n since several
series of moves will return you to a previous pattern.
Dennis Yelle
>
> Carl G. <cgi...@microprizes.com> wrote:
> > The game reminds me of my "Square Dance" puzzle at:
>
> > http://www.microprizes.com/mp52.htm
>
> Yes!
>
> > The "level 5" puzzle you described seems like it would be the same as the 16
> > color case, except that my puzzle also allowed certain 2x2 squares to
> > rotate. I would guess that your puzzle can also be solved in less than 50
> > moves.
>
> I think that this would sit much more happily in my brain if someone
> were to actually show me how to do a transposition in fewer than 50 moves.
Have you found any useful primitives?
I found a way to solve this in 8 moves:
0 1 2 3
9 5 11 7
8 4 10 6
12 13 14 15
Thus it is possible to do 2 swaps in 8 moves.
A single move can be seen as 7 swaps (not 8), so if we can
undo 6 of them in a total of about 24 moves, we can
do a single swap in about 25 moves.
Here are the 8 moves to do 2 swaps:
0 1 2 3
9 5 11 7
8 4 10 6
12 13 14 15
0 1 2 3
9 11 7 6
8 5 10 15
12 4 13 14
0 1 2 3
9 7 6 15
8 11 10 14
12 5 4 13
1 2 6 3
0 7 10 15
9 8 11 14
12 5 4 13
2 6 10 3
1 7 11 15
0 9 8 14
12 5 4 13
2 6 10 3
1 9 7 11
0 5 8 15
12 4 13 14
2 6 10 3
1 5 9 7
0 4 8 11
12 13 14 15
1 2 6 3
0 5 10 7
4 8 9 11
12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/
Kevin Buzzard
> Have you found any useful primitives?
> I found a way to solve this in 8 moves:
> 0 1 2 3
> 9 5 11 7
> 8 4 10 6
> 12 13 14 15
> Thus it is possible to do 2 swaps in 8 moves.
Having posted to rec.puzzles I thought I'd have another go at it. There's a
16-mover which does two 3-cycles (if A,B,C,D are the 4 moves labelled
sensibly then the sequence is A^4D^4A^4D^4). It's easy to
solve the first 2 rows of the game, so the moves I can make without
using a computer must be 8-transitive :-) In other words, given that
I can do one 8-cycle, I can
do any 8-cycle. As a result I can now prove that I can solve any
position with pencil and paper but no computer,
because an 8-cycle and two 3-cycles
gives me a 4-cycle; then using the two 3-cycles again I get a 3-cycle and
a 2-cycle; finally I get a 2-cycle. This would all be hundreds of not
thousands of moves! So I'm not sure I can solve the game in real time :-)
But at least I have my transposition.
> A single move can be seen as 7 swaps (not 8), so if we can
> undo 6 of them in a total of about 24 moves, we can
> do a single swap in about 25 moves.
As I'm sure you know, it's a few more than that because you can only do
the 2-cycles in those specific
positions, so you'll have to do some faffing around in between.
But yes, this is definitely a candidate for a reasonable 2-cycle.
Nice one :-) So maybe it is like the cube: gradually you discover
more tricks to make your life easier. Unlike the cube it's not
clear what order you should attempt to correctly position
the pieces :-) (for a complete solution understandable to a human)
> Here are the 8 moves to do 2 swaps:
D^{-2}A^{-2}D^2A^2, as we experts say :-) Very nice!
Kevin
Kevin Buzzard
Carl G. <cgi...@microprizes.com> wrote:
[amongst other things]
> My guess is that the puzzle is no harder to solve than a Rubik's cube.
Yeah, I now think I believe this. Dennis Yelle pointed out
that he could do 2 transpositions easily; a minor modification
of his method is (if A,B,C,D are the 4 clockwise 8-cycles and a,b,c,d the
anticlockwise ones)
AAddaaDD
which swaps the x's and y's below:
0x00
00y0
0y0x
0000
and this has the advantage that now moves only one of these
pieces, so something like
AAddaaDDCCAAddaaDDcc cycles around the three pieces below:
0000
x0x0
0x00
0000
and C puts these pieces into very nice places on the bottom
2 rows. So basically if you solve the first 2 rows and you're
left with an even permutation then repeated applications of this
does it. One can actually apply this algorithm in "real time".
I suspect that if people found other useful "primitives" the
solutions would get much slicker though :-)
Out of interest, my computer checked that A and B generated all
12! arrangements of the first three rows :-) Now _there_ is a fierce
puzzle! (the 3x4 case)
Kevin
Carl G.
Kevin Buzzard wrote in message <8pb26q$mo2$1...@agate.berkeley.edu>...
>Out of interest, my computer checked that A and B generated all
>12! arrangements of the first three rows :-) Now _there_ is a fierce
>puzzle! (the 3x4 case)
>
>Kevin
I am surprised that the 3x4 case can be rearranged into every pattern. Did
your program find an upper bound on the number of moves required to change
one arrangement into any other? I suspect that some people will try to
solve the puzzle in a manner similar to the way they solve the Rubik's cube,
but instead of starting by getting one face solved, they start by solving a
column or row along the side, reducing the problem to the 3x4 case. Your
choice of the adjective "fierce", makes me suspect that this would be a poor
way to solve the Nokia puzzle.
Carl G.
Geoff Bailey
In article <8patl1$m86$1...@agate.berkeley.edu>,
Kevin Buzzard <buz...@ic.ACK.ac.UCK.uk> wrote:
> Having posted to rec.puzzles I thought I'd have another go at it.
> There's a 16-mover which does two 3-cycles (if A,B,C,D are the 4
> moves labelled sensibly then the sequence is A^4D^4A^4D^4).
I found ABA^-1B^-1A^-1B^-1AB which induces two 3-cycles. I don't
believe that the game has the inverse moves as primitives, so this
is actually more moves, but it may be of some use.
>> A single move can be seen as 7 swaps (not 8), so if we can
>> undo 6 of them in a total of about 24 moves, we can
>> do a single swap in about 25 moves.
>
> As I'm sure you know, it's a few more than that because you can only
> do the 2-cycles in those specific positions, so you'll have to do some
> faffing around in between. But yes, this is definitely a candidate for
> a reasonable 2-cycle.
I used your Magma fragment and ran it on every 2-cycle. The best it found
was a length 20 solution for (7, 12). This actually turns into a length
29 expression in A,B,C,D. Simplifying the result (since each A,B,C,D is
of order 8) gives:
X1 := D C D C^-2;
X2 := D^2 C^2 D^-1 C^-1;
and then (7,12) equals X1 X2 X2 X1 X2 X2 X1.
Hopefully this is easy enough to remember. Also note that only C and D
are used, so this yields a solution method for the 3 by 4 as well.
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@cs.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
Dennis Yelle
swaps these 2 numbers:
**00
0000
0000
0000
Dennis Yelle
>
> This 13 move sequence: AbaacAbCBaCBc
> swaps these 2 numbers:
>
> **00
> 0000
> 0000
> 0000
I number the board this way:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Here are some 13 move sequences that swap 2 numbers:
swap( 0, 1) 13 moves: AbaacAbCBaCBc
swap( 0, 4) 13 moves: AbcBaCAABaCbc
swap( 0, 5) 13 moves: cBaCAABaCbcAb
swap( 1, 2) 13 moves: ABBDbAdaBdaDb
swap( 1, 5) 13 moves: bDcbCDCddBDBc
swap( 1, 6) 13 moves: bdbDDcdcBCdBC
swap( 5, 6) 13 moves: CadACAccDCDad
swap( 5, 8) 13 moves: abaBBdbdADbAD
swap( 5, 9) 13 moves: bdADbADabaBBd
swap( 5, 10) 13 moves: dBDBcbDcbCDCd
Dennis Yelle
>
> I finally managed to solve level 5 :-)
>
> Carl G. <cgi...@microprizes.com> wrote:
> [amongst other things]
>
> > My guess is that the puzzle is no harder to solve than a Rubik's cube.
>
> Yeah, I now think I believe this. Dennis Yelle pointed out
> that he could do 2 transpositions easily; a minor modification
> of his method is (if A,B,C,D are the 4 clockwise 8-cycles and a,b,c,d the
> anticlockwise ones)
I number the board like this:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
I can now do all 21 of the distinct single transpositions:
swap( 0, 1) 13 moves: AbaacAbCBaCBc
swap( 0, 2) 15 moves: AbdbDDcdcBCdBCa
swap( 0, 3) 17 moves: bAbdbDDcdcBCdBCaB
swap( 0, 5) 13 moves: cBaCAABaCbcAb
swap( 0, 6) 15 moves: dcBaCAABaCbcAbD
swap( 0, 7) 17 moves: ddcBaCAABaCbcAbDD
swap( 0, 10) 17 moves: aCdBDBcbDcbCDCdcA
swap( 0, 11) 19 moves: BaCdBDBcbDcbCDCdcAb
swap( 0, 15) 21 moves: aCdBdBDBcbDcbCDCdbDcA
swap( 1, 2) 13 moves: ABBDbAdaBdaDb
swap( 1, 4) 15 moves: CbDcbCDCddBDBcc
swap( 1, 5) 13 moves: bDcbCDCddBDBc
swap( 1, 6) 13 moves: bdbDDcdcBCdBC
swap( 1, 7) 15 moves: dbdbDDcdcBCdBCD
swap( 1, 9) 15 moves: DbDcbCDCddBDBcd
swap( 1, 10) 15 moves: cbdbDDcdcBCdBCC
swap( 1, 11) 17 moves: ddbdbDDcdcBCdBCDD
swap( 1, 13) 17 moves: DDbDcbCDCddBDBcdd
swap( 1, 14) 17 moves: ccbdbDDcdcBCdBCCC
swap( 5, 6) 13 moves: CadACAccDCDad
Bob Harris
> ... I was presented with a 4x4 grid again but this time I could only rotate
> the eight numbers on the boundary of a 3x3 square (where by a 3x3 square I
> mean where 3 consecutive rows meet 3 consecutive columns). So for example, the
> eight valid moves from the position
>
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
> 13 14 15 16
>
> would be to cycle round either (1,2,3,7,11,10,9,5),(2,3,4,8,12,11,10,6),
> (5,6,7,11,15,14,13,9) or (6,7,8,12,16,15,14,10).
>
> also having my laptop to hand which contains a computer algebra program which
> is very good at solving this sort of thing ("magma", in case anyone is
> interested), I wrote a few lines of code in its language to see what it
> thought of the problem. The first question I asked it was whether there were
> any restrictions on the positions one could get to from the final position, or
> whether any position was "legal". I was told that any position was legal:
>
>> G:=PermutationGroup<16|(1,2,3,7,11,10,9,5),(2,3,4,8,12,11,10,6),
>> (5,6,7,11,15,14,13,9),(6,7,8,12,16,15,14,10)>;
>> #G;
> 20922789888000
>> Factorial(16);
> 20922789888000
>
> Next I asked it to solve the position gotten by switching 15 and 16:
>
>> f:=InverseWordMap(G);
>> g:=G!(15,16);
>> sol:=f(g);
>> #sol;
> 847
I don't have magma, but I have GAP, which it would appear does the same sort
of things (find it at http://mirrors.ccs.neu.edu/GAP/NEU/gap.html). I'd
like to perform the same sort of computation in GAP, but I hit a stumbling
block. After defining the puzzle with
puzzle := Group ((1,2,3,7,11,10,9,5),
(2,3,4,8,12,11,10,6),
(5,6,7,11,15,14,13,9),
(6,7,8,12,16,15,14,10));;
and counting the size of the group with
Size (puzzle);
I don't see any corresponding operation to magma's InverseWordMap and sol.
Anyone out there familiar with GAP?
Thanks in any case,
Bob
Kevin Buzzard
> **00
> 0000
> 0000
> 0000
I'm a believer! So any two pieces can be swapped in probably under 20 or so
moves. How did you find this? Brute force search?
Kevin
Kevin Buzzard
> I number the board like this:
> 0 1 2 3
> 4 5 6 7
> 8 9 10 11
> 12 13 14 15
Quite why, when millions of mobile phones don't, is beyond me :-)
> I can now do all 21 of the distinct single transpositions:
> swap( 0, 1) 13 moves: AbaacAbCBaCBc
> swap( 0, 2) 15 moves: AbdbDDcdcBCdBCa
> swap( 0, 3) 17 moves: bAbdbDDcdcBCdBCaB
[snip] Things like (0,2) and (0,3) are easy from (0,1) if you
are happy with these move lengths: to do (0,2) just do b
and then swap (0,1) and then do B. As I'm sure you're aware.
A human solver might not remember all these moves anyway,
just one or two, and then recreate the rest using the trick
above. How did you find these solutions? Brute force and intelligence?
Do you know that no sequence of 11 moves induces a transposition?
Kevin
Kevin Buzzard
> Kevin Buzzard wrote in message <8pb26q$mo2$1...@agate.berkeley.edu>...
>>Out of interest, my computer checked that A and B generated all
>>12! arrangements of the first three rows :-) Now _there_ is a fierce
>>puzzle! (the 3x4 case)
>>
>>Kevin
> I am surprised that the 3x4 case can be rearranged into every pattern. Did
> your program find an upper bound on the number of moves required to change
> one arrangement into any other?
No---I just computed the group and it was the full symmetric group on
12 letters. But Geoff Bailey's post pretty much solves the 3x4 case I guess.
Wonder why Nokia didn't include this case? :-)
> I suspect that some people will try to
> solve the puzzle in a manner similar to the way they solve the Rubik's cube,
> but instead of starting by getting one face solved, they start by solving a
> column or row along the side, reducing the problem to the 3x4 case. Your
> choice of the adjective "fierce", makes me suspect that this would be a poor
> way to solve the Nokia puzzle.
Well, even after you've got one row (say the top one) completely solved,
it doesn't stop you from using the A and B rotations :-) So maybe this
would be the way to proceed anyway.
Kevin
Dennis Yelle
>
> Dennis Yelle <denn...@jps.net> wrote:
>
> > I number the board like this:
> > 0 1 2 3
> > 4 5 6 7
> > 8 9 10 11
> > 12 13 14 15
>
> Quite why, when millions of mobile phones don't, is beyond me :-)
So each number fits in 4 bits.
> > I can now do all 21 of the distinct single transpositions:
> > swap( 0, 1) 13 moves: AbaacAbCBaCBc
> > swap( 0, 2) 15 moves: AbdbDDcdcBCdBCa
> > swap( 0, 3) 17 moves: bAbdbDDcdcBCdBCaB
>
> [snip] Things like (0,2) and (0,3) are easy from (0,1) if you
> are happy with these move lengths: to do (0,2) just do b
> and then swap (0,1) and then do B. As I'm sure you're aware.
> A human solver might not remember all these moves anyway,
> just one or two, and then recreate the rest using the trick
> above. How did you find these solutions? Brute force and intelligence?
First I generated all 1065529 positions that can be reached
in 7 or fewer moves. Then, for each of the 21 single swaps, I
generated the 22101 positions reached in 5 or fewer moves.
There were no matches with the first set, so no sequence of
12 or fewer moves is a transposition.
Then I generated the 153469 positions reached in 6 or fewer moves, and
checked for any matches with the first group. This gave
me all of the 13 move solutions. Then I added each 13 move solution
as a primitive and generated sequences of 3 moves, this gave me the
15 move solutions, then I tried 5, 7, and 9 moves to get the
17, 19, and 21 move solutions.
> Do you know that no sequence of 11 moves induces a transposition?
Yes.