# Swapping 6 queens in a 4x4 grid

What is the least number of moves required to swap black and white queens? Queens move using standard chess rules - any number of empty cells vertically, horizontally or diagonally in a straight line. You do not need to alternate players.

Here is a similar question for rooks: Swapping 3 rooks in a 3x3 grid

It can actually be done in 17 moves.

Step 0
Q Q Q *
Q Q * q
Q * q q
* q q q

Step 1
Q Q * Q
Q Q * q
Q * q q
* q q q

Step 2
Q Q q Q
Q Q * q
Q * * q
* q q q

Step 3
Q Q q Q
Q Q q q
Q * * *
* q q q

Step 4
Q Q q Q
Q Q q q
* * * Q
* q q q

Step 5
Q Q q Q
Q Q q q
* * q Q
* q q *

Step 6
Q Q q Q
* Q q q
* * q Q
Q q q *

Step 7
Q Q q Q
q Q q q
* * q Q
Q q * *

Step 8
Q Q q Q
q Q q q
q * * Q
Q q * *

Step 9
Q Q q Q
q * q q
q * * Q
Q q * Q

Step 10
* Q q Q
q * q q
q * Q Q
Q q * Q

Step 11
* Q q Q
q q q q
q * Q Q
Q * * Q

Step 12
* Q q Q
q q q q
q * Q Q
* * Q Q

Step 13
q Q q Q
q * q q
q * Q Q
* * Q Q

Step 14
q * q Q
q * q q
q * Q Q
* Q Q Q

Step 15
q q q Q
q * * q
q * Q Q
* Q Q Q

Step 16
q q q Q
q q * *
q * Q Q
* Q Q Q

Step 17
q q q *
q q * Q
q * Q Q
* Q Q Q

• nicely done there! Sep 26 '20 at 0:01

Using the notation, (x = black queen, o = white queen, - = empty space), I came up with the following series of steps:

Starting Position:
x x x -
x x - o
x - o o
- o o o

1:

x x - x
x x - o
x - o o
- o o o

2:

x x o x
x x - o
x - - o
- o o o

3:

x x o x
x x - o
- - - o
x o o o

4:

x x o x
x x - o
- - o o
x o o -

5:

x x o x
x x - o
o - - o
x o o -

6:

x x o x
x - - o
o - - o
x o o x

7:

x x o x
x - o o
o - - o
x o - x

8:

x x o x
- - o o
o - - o
x o x x

9:

- x o x
- x o o
o - - o
x o x x

10:

o x o x
- x o o
- - - o
x o x x

11:

o x o x
- x o o
o - - -
x o x x

12:

o x o x
- - o o
o - x -
x o x x

13:

o x o x
o - - o
o - x -
x o x x

14:

o - o x
o - - o
o - x x
x o x x

15:

o o o x
o - - o
o - x x
x - x x

16:

o o o x
o o - -
o - x x
x - x x

17:

o o o -
o o - x
o - x x
x - x x

18:

o o o -
o o - x
o - x x
- x x x

This is also the solution with the least number of steps.

To understand why, consider a 2 x 2 board with 1 black queen and 1 white queen in opposite corners.

x -
- o

To move these queens into opposite corners, you will need to:
1) Move one queen into an unoccupied square.
2) Move the other queen into the recently vacated square.
3) Move the first queen into the recently vacated square by the other queen.

In essence, you need 3 moves per pair of queen. For 6 pairs of queen, you need 6 x 3 = 18 moves.

EDIT: As noted by @Bass below, the above explanation does not always hold true. So, there could theoretically be a lower limit than the one I explained.

• The minimality argument doesn't scale linearly. For example, 4 queens on the sides of a 3x3 square can be colour swapped in 5 moves.
– Bass
Sep 24 '20 at 3:15
• Well done! You are good at these puzzles. I wonder how this method works on larger grids? Sep 24 '20 at 3:58
• @Bass Could I ask you for the configuration you used for your example? Is it - x -, x - o, - o - (from row 1 to 3)? Because this seems to require 6 steps for me. Sep 24 '20 at 4:05
• @Alaiko This works because you don't actually need to swap the queens pairwise, any queen of the opposing colour will do.
– Bass
Sep 24 '20 at 4:31
• In fact, I just repeated this for 6 queens in a 3 x 3 board: x x -, x - o, - o o. Turns out you can do that one in 8 moves. I'm starting to think this solution is not optimal after all... Sep 24 '20 at 4:48

Here is another optimal one.

$$\begin{matrix} \_&O&O&O&&\_&O&O&O&&\_&O&O&O&&\_&O&O&O\\X&\_&O&O&&X&\_&O&O&&X&\_&O&O&&X&\_&O&O\\X&X&\_&O&&X&X&\_&\_&&X&\_&\_&X&&X&\_&X&X\\X&X&X&\_&&X&X&X&O&&X&X&X&O&&X&\_&X&O \end{matrix}$$

$$\begin{matrix} \_&\_&O&O&&\_&X&O&O&&\_&X&O&O&&\_&X&O&O\\X&\_&O&O&&\_&\_&O&O&&O&\_&\_&O&&O&O&\_&\_\\X&\_&X&X&&X&\_&X&X&&X&\_&X&X&&X&\_&X&X\\X&O&X&O&&X&O&X&O&&X&O&X&O&&X&O&X&O \end{matrix}$$

$$\begin{matrix} \_&X&O&O&&\_&X&O&O&&\_&X&O&\_&&\_&X&O&\_\\O&O&X&\_&&O&O&\_&X&&O&O&\_&X&&O&O&\_&X\\X&\_&X&X&&X&\_&X&X&&X&\_&X&X&&\_&X&X&X\\\_&O&X&O&&\_&O&X&O&&O&O&X&O&&O&O&X&O \end{matrix}$$

$$\begin{matrix} \_&X&O&X&&\_&X&O&X&&\_&X&\_&X&&\_&X&X&X\\O&O&\_&X&&O&\_&\_&X&&O&\_&\_&X&&O&\_&\_&X\\\_&\_&X&X&&\_&O&X&X&&O&O&X&X&&O&O&\_&X\\O&O&X&O&&O&O&X&O&&O&O&X&O&&O&O&X&O \end{matrix}$$

$$\begin{matrix} \_&X&X&X&&\_&X&X&X\\O&\_&X&X&&O&\_&X&X\\O&O&\_&X&&O&O&\_&X\\O&O&\_&O&&O&O&O&\_ \end{matrix}$$

Not correcting for symmetries there are

48 optimal (17 move) solutions.

A brute force program finds all of them in less than a minute.

• Nice! What language are you using? Sep 25 '20 at 21:10
• @DrXorile I'm using Python/NumPy. How did you find your solution? Sep 25 '20 at 21:12
• Python also. Mine takes more than a minute, but I haven't optimized it too much. Sep 25 '20 at 21:15