Mathematically, the moves in a game of this sort are permutations, which serve as a generating set (not necessarily minimal!) for a subgroup of the permutation group. The number of moves is the "word length" of the permutation that maps the initial state to the goal state. That suffices if the goal state is fixed, like in the 15-puzzle:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
but usually in this sort of game you are not trying to put a picture back together, but instead achieve some grouping or pattern. This grouping can be defined as a permutation subgroup as well! Define it as the permutation subgroup generated by all permutations which flip two squares which are identical in the goal state. For example, suppose instead of the 15-puzzle we just have red squares and blue squares, and the goal is
R B R B B R B R R B R B B R B R
The corresponding subgroup is generated by { (1 3), (1 6), (1 8), (1 9), (1 11), (1 14), (1 16), (2 4), (2 5), ... }. The cosets of this subgroup are the states generated by moves.
To make things more concrete, my toy problem to get started is to divide a black-and-white tile grid into fixed regions of black tiles and white tiles. (The code permits multiple goal states if we wanted *any* separation of black and white into distinct regions.)
3x3 4x4
BBB BBBB
BBW BBBB
WWW WWWW
WWWW
The moves I'm considering are illustrated below:
"Slide" a row or column, wrapping around from top to bottom and left to right:
Rotate four tiles around a point, either in a fixed direction ("Bejeweled Twist" mechanic) or freely to any of the other three orientations ("RotX3" below):
Transpose two arbitrary tiles that are orthogonally adjacent ("Bejeweled" mechanic):
Rotate the outer "wheel" of tiles, or swap the top one with the center along the "axis":
So, what does the distribution of # of required moves look like for these sets of moves, and the goal states above?
3x3 Sliding Rot RotX3 Trans Wheel 0 1 1 1 1 1 1 8 2 8 4 7 2 32 6 37 12 4 3 55 15 60 21 20 4 29 23 20 30 11 5 1 32 27 45 6 31 20 17 7 13 8 15 8 3 3 3 9 3 Number of moves in each generating set: 12 4 12 12 8
The worst-case position for sliding (requiring 5 moves) is:
[001 001 111]
Interestingly, this also shows up as one of the worst-case situations for free rotation and for transpositions.
4x4 Sliding Rot Rot3X Trans Wheel 0 1 1 1 1 1 1 12 3 9 6 14 2 126 12 93 20 41 3 864 47 424 60 104 4 3737 142 1380 159 326 5 6196 329 2844 336 642 6 1934 666 3719 626 1240 7 1114 3048 992 1535 8 1616 1211 1406 2282 9 2043 141 1724 2377 10 2201 1888 2240 11 1939 1796 1379 12 1404 1515 569 13 828 1088 90 14 374 686 30 15 120 352 16 29 157 17 2 48 18 12 Number of moves in each generating set: 24 9 27 24 15
Obviously adding an extra move to a move set can only decrease the word length. But these examples show that doesn't imply more moves always beats fewer moves. Sliding appears to be much better for this specific puzzle than rotation or transposition, which have a similar number of base moves. That's what I expected to see but it's nice to have some confirmation.
The last nonzero number in each column is "God's number" for that particular instance of the game. For Rubik's Cube (also a permutation game, which could be represented by the appropriate grid!) this number was recently shown to be 20. But I'm not sure whether I'm interested in max hardness or median hardness here.
