Bishop's Square

The "Bishop's Square" puzzle is similar in concept to the famous "Rubik's Cube" puzzle. However, instead of rotating the sections of a three dimensional cube, you "rotate" the sections of a two dimensional image by sliding them up, down, left, and right, in a "wrap-around" manner.

Nomenclature

The Rubik's Cube Puzzle uses a cube that is divided into smaller sections which are usually referred to as "cubies". The Bishop's Square Puzzle uses a picture that is divided into smaller sections which we will refer to as "pixies".

The number of rows and columns into which the picture is divided can be any amount. We have somewhat arbitrarily chosen to divide the picture into four columns by three rows. This 4x3 arrangement of pixies is displayed in a window, which we will call the "viewport". In the discussion that follows, the 12 pixies in the viewport will be indicated by the numbers 1 through 9 (and the letters A through C):

However, because the rows and columns wrap around when they slide, it is important to understand that the image in the viewport actually replicates (or tiles) itself in all directions outside the viewport:

Therefore, two separate pixies (such as pixie #1 and pixie #4) may actually be adjacent to each other even though they are on opposite sides of the display! In fact, no pixie is ever more than one row and two columns away from any other pixie.

The "L-Cycle"

Let's perform the following two moves:

          Slide column #2 Down
          Slide row #3 Left

This results in the following arrangement of pixies:

(We've indicated in red those pixies which are no longer in their proper locations.)

If we were to undo these two moves by performing the operations:

          Slide row #3 Right
          Slide column #2 Up

all the pixies would once again return to their initial positions. However, if we reverse these two operations (i.e. first Slide column #2 Up, and then Slide row #3 Right), we see the following result:

Notice that almost all the pixies have once again returned to their initial positions, except for three of them (#6, #A, and #B) which have been cyclicly permuted counter-clockwise in an "L"-shaped pattern. (Can you find the sequence of four moves that produces the clockwise permutation?)

The process of performing either of the following four sequential slide moves (on arbitrary column #i and arbitrary row #j):

          Slide column #i Up (or Down)
          Slide row #j Left (or Right)
          Slide column #i Down (or Up)
          Slide row #j Right (or Left)

        or

          Slide row #j Left (or Right)
          Slide column #i Up (or Down)
          Slide row #j Right (or Left)
          Slide column #i Down (or Up)

will always leave the image intact, except for three pixies whose positions form an "L"-shaped pattern. (The "L" may appear rotated depending on the specific sequence of moves performed.) These four sequential slide moves are therefore referred to as performing an "L-cycle" on three pixies.*

*(This "L-cycle" process works not only for the 4x3 configuration
that we are using here, but for any configuration 2x2 or larger.)

The moves for producing an "L-cycle" need not be only single slides. For example, the following set of moves (in which we slide a row more than once in succession):

          Slide column #2 Down
          Slide row #3 Left
          Slide row #3 Left
          Slide column #2 Up
          Slide row #3 Right
          Slide row #3 Right

will produce the following results:

Notice that the three displaced pixies still form an "L"-shaped pattern (with #C to #6 forming the vertical part of the "L", and #6 to #A forming the horizontal part), but the pixies are no longer necessarily contiguous with each other.

The concept of an "L-cycle" represents an important analytical tool in the solution of the Bishop's Square Puzzle. (In the discussion that follows, we will merely indicate the results of using "L-cycles" without explicitly showing the actual sequences of slide moves involved.)

Question: Is it possible to swap any two pixies in the viewport leaving all the other pixie positions undisturbed?

Answer: Yes!

If the two pixies to be swapped are in different rows and/or columns, first transform the puzzle (by utilizing appropriate "L-cycles") into one in which only two incorrect pixies are adjacent to each other. For example, consider the following initial configuration (in which we need to swap pixie #1 with pixie #7):

We first perform an "L-cycle" on pixies #7, #5, and #1:

Then we perform an "L-cycle" on pixies #5, #2, and #1:

This produces the desired interim configuration in which pixie #1 and pixie #2 are next to each other, but in the wrong order.

Next, we slide row #1 to the Right one position:

This puts pixies #1 and #2 into their correct positions, but leaves pixies #8, #3, and #4 out of order. So we simply perform an "L-cycle" on them and the picture is completely restored (with pixies #1 and #7 now in their proper locations).

Conclusion

We now have (at least in principle) all the tools necessary to solve any 4x3 Bishop's Square Puzzle - You could simply run through the set of pixies and swap the correct one into each position in the viewport (although that wouldn't be the most efficient way of solving the puzzle). However, being able to do so implies that:

Any initial arrangement of pixies in the 4x3 Bishop's Square Puzzle
has a solution (even if all the pixies were to be laid down randomly).

Other configurations (such as a 3x3 Bishop's Square Puzzle) may not necessarily have a solution for arbitrary initial arrangements of pixies. (Can you verify this claim?) Of course any arrangement that is produced by a sequence of row-column slides can always be solved for any size configuration.

Have fun solving Bishop's Square!