Some preliminary goofing around on tile games

My vacation project has been putting together some Python code to systematically study various tile-permuting operations found in match-3 or sliding puzzle games. What I'm interested in is: given a particular goal on a square grid (like making a group of N tiles, or arriving at some other in a set of arrangements), how many moves does it take to reach the goal? Are certain types of moves better suited to particular types of goals?

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.
Tags:
• Post a new comment

Error

default userpic