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

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

1 Answer 1

Reset to default
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$
6
  • 1
    $\begingroup$ Nice solution! I checked with a computer program, and this is optimal. My code $\endgroup$
    – isaacg
    Sep 23, 2020 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, 2020 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, 2020 at 12:16
  • $\begingroup$ @FireCase that's correct well done! $\endgroup$
    – Dmitry Kamenetsky
    Sep 23, 2020 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
    Sep 23, 2020 at 13:12

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.