Sliding blocks group has a new paper!

 One of our lab groups has recently submitted a paper to the arXiv!  The paper, written by Patrick Garcia, Angela Hanson, Dave Jensen, and Noah Owen, can be found here:

https://arxiv.org/abs/2210.16930

 The paper focuses on puzzles like the one designed by Henry Segerman, pictured below:

 

Segerman's 15+4 puzzle is similar to the classic 15-puzzle, pictured below. There are tiles labeled with numbers and 1 empty spot. You can move the tiles around by sliding an adjacent tile into the empty spot, and your goal is to get the tiles in order by a sequence of these moves.

  

The twist is that, in Segerman's puzzle, moving the tiles around can cause them to rotate. For example, here's a solvable state of the 15+4 puzzle in which every tile is in its original position, but some of them are rotated.  

  

Here are some other puzzles designed by Henry Segerman.  Each one is a sliding block puzzle in which sliding the blocks around can cause them to change orientations.

 

In 1891, Sam Loyd offered $1000 to anyone who could produce this configuration of the 15 puzzle, in which all the tiles are in order except 14 and 15, which are switched.

  

Loyd probably knew that this was impossible. 12 years earlier, Johnson and Story had proven that the only achievable permutations, with the empty spot in the bottom right, were even permutations.  To see this, note that when you slide a tile into the empty spot, you transpose that tile and the empty tile. The graph corresponding to the 15-puzzle is bipartite, so every cycle has an even number of edges. Thus, sliding tiles around a cycle produces a composition of an even number of transpositions. 

 In 1974, Wilson considered sliding block puzzles on arbitrary graphs. He showed that if the graph is bipartite, the group of solvable permutations is always A_n. Otherwise, it's S_n, except for 1 exceptional case, where it's PGL(2,5).

 The main result of our paper is the analogous result for sliding block puzzles where the tiles can rotate.  Aside from 2 exceptional cases, the group of solvable states is 1 of 3 possibilities.  If the graph is bipartite, you get the generalized alternating group.  If it's something we call "twist bipartite", you get the Coxeter group of type D, and otherwise you get the full generalized symmetric group S(m,n).