5
$\begingroup$

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.

enter image description here

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

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ nicely done there! $\endgroup$
    – Dmitry Kamenetsky
    Sep 26, 2020 at 0:01
5
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Bass
    Sep 24, 2020 at 3:15
  • $\begingroup$ Well done! You are good at these puzzles. I wonder how this method works on larger grids? $\endgroup$
    – Dmitry Kamenetsky
    Sep 24, 2020 at 3:58
  • $\begingroup$ @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. $\endgroup$
    – Alaiko
    Sep 24, 2020 at 4:05
  • 1
    $\begingroup$ @Alaiko This works because you don't actually need to swap the queens pairwise, any queen of the opposing colour will do. $\endgroup$
    – Bass
    Sep 24, 2020 at 4:31
  • 1
    $\begingroup$ 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... $\endgroup$
    – Alaiko
    Sep 24, 2020 at 4:48
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice! What language are you using? $\endgroup$
    – Dr Xorile
    Sep 25, 2020 at 21:10
  • $\begingroup$ @DrXorile I'm using Python/NumPy. How did you find your solution? $\endgroup$
    – Albert.Lang
    Sep 25, 2020 at 21:12
  • $\begingroup$ Python also. Mine takes more than a minute, but I haven't optimized it too much. $\endgroup$
    – Dr Xorile
    Sep 25, 2020 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.