Time Event 10:24p 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.