11

This puzzle was inspired by this one: Swapping rooks in a 4x4 board

What is the least number of moves required to swap black and white rooks? Rooks move using standard chess rules - any number of empty cells vertically or horizontally. You do not need to alternate players.

enter image description here

Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276

1 Answers1

7

Using the same notation that @Deepthinker came up with, (i.e. x = black rook, o = white rook, - = empty space), I came up with the following series of steps:

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

1:

x - x
x - o
- o o

2:

x - x
- - o
x o o

3:

- - x
x - o
x o o

4:

- o x
x - o
x - o

5:

o - x
x - o
x - o

6:

o - x
x - o
x o -

7:

o o x
x - o
x - -

8:

o o x
x - o
- - x

9:

o o x
- - o
x - x

10:

o o x
o - -
x - x

11:

o o -
o - x
x - x

12:

o o -
o - x
- x x

I do not know whether or not this is the optimal strategy though. Still working on that.

Alaiko
  • 6,667
  • 2
  • 25
  • 52
  • 1
    Nice solution! I checked with a computer program, and this is optimal. My code – isaacg Sep 23 '20 at 06:10
  • 2
    well done you got it! Now can you (or anyone else) prove that this is optimal without a computer? – Dmitry Kamenetsky Sep 23 '20 at 07:27
  • 2
    Maybe I am missing something, but it seems almost obvious. the 12 and 32 as well as 21 and 23 rook pairs (positions : first nb horizontal, second nb vertical) cannot swap in 2 moves altogether because then they would "meet". That simply means the final positions for each rook won't be in its original row/column (obv. if we are not looking for the optimal case, they can be..) each rook needs at least 2 steps to reach their final position, so 6*2=12. So this number is the theoretical minimum – FIreCase Sep 23 '20 at 12:16
  • @FireCase that's correct well done! – Dmitry Kamenetsky Sep 23 '20 at 12:43
  • 2
    @FIreCase, in this solution not all rooks made at least 2 steps though. the rook that moved in step 10 only made one step in total. one rook made 3 steps (the rook that moved in step 3,9 and 12). I agree that 12 is the theoretical minimum, but I'm not sure how to prove it – Ivo Sep 23 '20 at 13:12
  • @Ivo yes, I see it. Maybe we could try to prove the following : it is possible for one rook to remain in its original row/column, but then another has to make at least 3 steps :P It looks difficult at the moment... – FIreCase Sep 23 '20 at 13:50