10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is a "move" moving one space, or moving any number of spaces in one direction? $\endgroup$ – bobble Sep 23 at 1:11
  • $\begingroup$ Any number of spaces. I've clarified this in the problem. $\endgroup$ – Dmitry Kamenetsky Sep 23 at 1:13
  • $\begingroup$ Hi Dimitry can you please help me organise my answer $\endgroup$ – Deepthinker101 Sep 23 at 1:51
  • $\begingroup$ @Deepthinker101 use <pre> tags like I have done. Also please hide it using the >! syntax $\endgroup$ – Dmitry Kamenetsky Sep 23 at 1:54
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice solution! I checked with a computer program, and this is optimal. My code $\endgroup$ – isaacg Sep 23 at 6:10
  • 2
    $\begingroup$ well done you got it! Now can you (or anyone else) prove that this is optimal without a computer? $\endgroup$ – Dmitry Kamenetsky Sep 23 at 7:27
  • 2
    $\begingroup$ 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 $\endgroup$ – FIreCase Sep 23 at 12:16
  • $\begingroup$ @FireCase that's correct well done! $\endgroup$ – Dmitry Kamenetsky Sep 23 at 12:43
  • 2
    $\begingroup$ @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 $\endgroup$ – Ivo Beckers Sep 23 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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