Transpositions are Easy
Building on the toy games introduced here.
I figured the easiest tile-game move to analyze is transpositions. Only two tiles are affected by any move, and they have to be opposite colors in any minimal solution. My earlier code showed, for example, that it takes 8 tile swaps (orthogonal moves only) to convert:
1101
0110
0100
1010
to
1111
1111
0000
0000
and it's pretty easy to find such a sequence of moves. To do so you sort of eyeball where the "gaps" are and which other pieces are closest to those gaps. Can this idea be formalized into a (non-brute-force) algorithm for finding minimal move counts? I think so.
Let's start with the algorithm, then argue that its results make sense. Transform the problem into a minimum-cost bipartite matching problem. The two sets are the goal positions and the pieces, and the edge costs are the distance (in moves) between each pair. So the matrix representation of the transformed problem looks like this:
pieces -->
goals 0 1 3 2 3 3 3 5
| 1 0 2 1 2 2 4 4
V 2 1 1 2 1 3 5 3
3 2 0 3 2 4 6 4
1 2 4 1 2 2 2 4
2 1 3 0 1 1 3 3
3 2 2 1 0 2 4 2
4 3 1 2 1 3 5 3
The minimum selection of 8 elements from this matrix, which share no row or column in common, gives the number of moves in the solution. It's obvious that no fewer number of moves will work. But can we show that this number is achievable?
Now, alas, you can't just read off the matching to get the sequence of moves. For example, in the case
1101
1161
0080
0000
moving "piece 8 to position 3" has cost 2, as does "piece 6 to position 3 and piece 8 to position 6", so both are solutions to the matching, but only the latter is feasible. If we tried to move piece 8 twice we'd need an additional move to put 6 back into place. We need to show that any infeasible plan can be transformed into one which is feasible with the same number of moves.
Fortunately, this is pretty easy. Suppose the plan calls for moving piece A onto the square currently occupied by piece B. This move is a no-op since the pieces are identical in this puzzle. We can remove that transposition from the move sequence by "swapping the identities" of A and B instead of making the no-op move. That is, whenever we would move A to a non-empty space occupied by B, instead swap the labels and continue moving the new "A-prime" (previously "B"). This will leave "B-prime" one space away from its initial starting point, so after A-prime has moved on, use one move to put B-prime back into its starting point (or its goal point). This exactly balances out the move we removed because it was a no-op.
Puzzle: * *
A 0 0 B 0
Plan: A --> --> --> --> (4 transpositions)
B (0 transpositions)
Execution: A --> --> rename
A'--> (3 transpositions)
B'--> (1 transposition)
The transformation can be applied multiple times to move through multiple pieces as well, just move the renamed pieces back in reverse order (first-in-last-out). As a check, I ran the minimum-matching algorithm across all 4x4 positions and it agreed with the previously computed values.
Using this algorithm, we can both solve individual large instances as well as perform parallel counts of move distances without using a large amount of memory. The best minimal matching algorithms are O(N^3), though, so this is a significantly more compute-intensive method of finding all minimal word distances than the brute force approach.
This example of a random 12x12 matrix
001101011000
011100000011
011001011111
011010111111
000000101110
000110001010
000100101101
010001110001
111100100011
001011100001
110010100101
010111111101
requires 267 moves to restore to the sorted state, according to this algorithm, with one possible plan (goal, piece) = (0, 0), (1, 5), (2, 62), (3, 1), (4, 2), (5, 67), (6, 60), (7, 3), (8, 4), (9, 56), (10, 8), (11, 9), (12, 70), (13, 71), (14, 6), (15, 7), (16, 65), (17, 12), (18, 49), (19, 13), (20, 14), (21, 15), (22, 50), (23, 51), (24, 10), (25, 63), (26, 11), (27, 64), (28, 20), (29, 66), (30, 21), (31, 69), (32, 28), (33, 61), (34, 16), (35, 17), (36, 18), (37, 58), (38, 19), (39, 48), (40, 59), (41, 54), (42, 55), (43, 22), (44, 23), (45, 24), (46, 25), (47, 26), (48, 57), (49, 46), (50, 52), (51, 31), (52, 32), (53, 27), (54, 42), (55, 68), (56, 37), (57, 29), (58, 30), (59, 44), (60, 45), (61, 40), (62, 47), (63, 35), (64, 53), (65, 41), (66, 36), (67, 43), (68, 33), (69, 38), (70, 34), (71, 39). That is, piece 0 moves left twice into position 0, piece 5 moves left seven times into position 1, position 2 is filled from below, position 3 is filled with the piece "1" already in it. But following the procedure above we can see that piece "5" and "1" will be renamed if we carry out this sequence. (I haven't written the code to actually simulate playing all 267 moves to verify, so there may be an error lurking here but I'm pretty confident in the proof above.)
There might be some way to tighten up the matching to prefer non-crossing moves, for example by increasing "1" to "1.001", "2" to "2.003", "3" to "3.006", etc., to introduce a bias for plans which perform two "real" moves instead of a longer one which will get broken up.
Unfortunately this practical algorithm doesn't seem to provide any hints toward enumerating the distribution of minimal distances for various sizes of board.
I figured the easiest tile-game move to analyze is transpositions. Only two tiles are affected by any move, and they have to be opposite colors in any minimal solution. My earlier code showed, for example, that it takes 8 tile swaps (orthogonal moves only) to convert:
1101
0110
0100
1010
to
1111
1111
0000
0000
and it's pretty easy to find such a sequence of moves. To do so you sort of eyeball where the "gaps" are and which other pieces are closest to those gaps. Can this idea be formalized into a (non-brute-force) algorithm for finding minimal move counts? I think so.
Let's start with the algorithm, then argue that its results make sense. Transform the problem into a minimum-cost bipartite matching problem. The two sets are the goal positions and the pieces, and the edge costs are the distance (in moves) between each pair. So the matrix representation of the transformed problem looks like this:
pieces -->
goals 0 1 3 2 3 3 3 5
| 1 0 2 1 2 2 4 4
V 2 1 1 2 1 3 5 3
3 2 0 3 2 4 6 4
1 2 4 1 2 2 2 4
2 1 3 0 1 1 3 3
3 2 2 1 0 2 4 2
4 3 1 2 1 3 5 3
The minimum selection of 8 elements from this matrix, which share no row or column in common, gives the number of moves in the solution. It's obvious that no fewer number of moves will work. But can we show that this number is achievable?
Now, alas, you can't just read off the matching to get the sequence of moves. For example, in the case
1101
1161
0080
0000
moving "piece 8 to position 3" has cost 2, as does "piece 6 to position 3 and piece 8 to position 6", so both are solutions to the matching, but only the latter is feasible. If we tried to move piece 8 twice we'd need an additional move to put 6 back into place. We need to show that any infeasible plan can be transformed into one which is feasible with the same number of moves.
Fortunately, this is pretty easy. Suppose the plan calls for moving piece A onto the square currently occupied by piece B. This move is a no-op since the pieces are identical in this puzzle. We can remove that transposition from the move sequence by "swapping the identities" of A and B instead of making the no-op move. That is, whenever we would move A to a non-empty space occupied by B, instead swap the labels and continue moving the new "A-prime" (previously "B"). This will leave "B-prime" one space away from its initial starting point, so after A-prime has moved on, use one move to put B-prime back into its starting point (or its goal point). This exactly balances out the move we removed because it was a no-op.
Puzzle: * *
A 0 0 B 0
Plan: A --> --> --> --> (4 transpositions)
B (0 transpositions)
Execution: A --> --> rename
A'--> (3 transpositions)
B'--> (1 transposition)
The transformation can be applied multiple times to move through multiple pieces as well, just move the renamed pieces back in reverse order (first-in-last-out). As a check, I ran the minimum-matching algorithm across all 4x4 positions and it agreed with the previously computed values.
Using this algorithm, we can both solve individual large instances as well as perform parallel counts of move distances without using a large amount of memory. The best minimal matching algorithms are O(N^3), though, so this is a significantly more compute-intensive method of finding all minimal word distances than the brute force approach.
This example of a random 12x12 matrix
001101011000
011100000011
011001011111
011010111111
000000101110
000110001010
000100101101
010001110001
111100100011
001011100001
110010100101
010111111101
requires 267 moves to restore to the sorted state, according to this algorithm, with one possible plan (goal, piece) = (0, 0), (1, 5), (2, 62), (3, 1), (4, 2), (5, 67), (6, 60), (7, 3), (8, 4), (9, 56), (10, 8), (11, 9), (12, 70), (13, 71), (14, 6), (15, 7), (16, 65), (17, 12), (18, 49), (19, 13), (20, 14), (21, 15), (22, 50), (23, 51), (24, 10), (25, 63), (26, 11), (27, 64), (28, 20), (29, 66), (30, 21), (31, 69), (32, 28), (33, 61), (34, 16), (35, 17), (36, 18), (37, 58), (38, 19), (39, 48), (40, 59), (41, 54), (42, 55), (43, 22), (44, 23), (45, 24), (46, 25), (47, 26), (48, 57), (49, 46), (50, 52), (51, 31), (52, 32), (53, 27), (54, 42), (55, 68), (56, 37), (57, 29), (58, 30), (59, 44), (60, 45), (61, 40), (62, 47), (63, 35), (64, 53), (65, 41), (66, 36), (67, 43), (68, 33), (69, 38), (70, 34), (71, 39). That is, piece 0 moves left twice into position 0, piece 5 moves left seven times into position 1, position 2 is filled from below, position 3 is filled with the piece "1" already in it. But following the procedure above we can see that piece "5" and "1" will be renamed if we carry out this sequence. (I haven't written the code to actually simulate playing all 267 moves to verify, so there may be an error lurking here but I'm pretty confident in the proof above.)
There might be some way to tighten up the matching to prefer non-crossing moves, for example by increasing "1" to "1.001", "2" to "2.003", "3" to "3.006", etc., to introduce a bias for plans which perform two "real" moves instead of a longer one which will get broken up.
Unfortunately this practical algorithm doesn't seem to provide any hints toward enumerating the distribution of minimal distances for various sizes of board.