Swapping Knights Puzzle

Logic Level 2

Above is a 3 × 3 3\times3 board with 4 knights two white knights and two black knights. As in a standard game of chess, the knight can move only two steps in the horizontal or vertical direction and then one step in the other direction for one move. Define an action as moving a knight of any color.

The objective of the game is to interchange the position of both the black and white knights while alternately moving a knight of different color. The final state of the board is:

Using only actions, what is the minimum number of actions required to complete the game?


The answer is 16.

View wiki
Naitik Sanghavi by naitik sanghavi , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Calvin Lin Staff
Apr 4, 2016

The difficulty of this problem is in clearly proving that you have indeed found the minimum number of actions. Let's rephrase this problem, so that we don't have to consider knight moves. Number the board in the following way:

Now, let's create a graph where the vertices are these squares, and the edges are the knigh-move adjacent squares that we can move to. We easily see that
1. The square 5 is not involved
2. We get a cycle (so simple!)

The original position is now expressed as such (where the 1 loops back on itself)

The final position that we want to get to, can be expressed as such:

Because we only have a cycle, and the knights do not "eat" each other, this implies that they can only move in one direction. As such, to minimize the number of actions, we must have each knight move 4 to the right (or left).

Thus, the minimal number of actions is 16.

10 Helpful 1 Interesting 0 Brilliant 0 Confused

I think you should add an assumption, because if the objective of the game is to interchange the position of both the black and white knights while alternately moving a knight of different color, I can do it in 0 0 actions defined an action as moving a knight of any colour. Do you know how can I do it?

Rotating 180º the chessboard... or rotating myself 180º...

Guillermo Templado - 4 years, 5 months ago

Log in to reply

Thanks. I will clarify what is allowed.

Calvin Lin Staff - 4 years, 5 months ago

Second picture is wrong, black and white should be interchanged!?

Andrej Jakobčič - 2 years, 7 months ago
Desmond Sheppard
Apr 2, 2016

It is possible to get two of the knights (opposite corners, not adjacent) onto their corresponding squares in 6 actions, but this creates an impossible circumstance for the others to achieve their positions.

The only solution that seems available is the "nonattacking squares" approach for knights, which involves all knights positioned on squares of the same color. This involves "rotating" the pieces on the board as a unit. It takes a single knight 4 actions minimum to traverse from one corner to the opposite corner, using all L-shapes or reverse-L shapes. Four knights would have the same restrictions, so to minimize collisions, all would need to move in either L or reverse-L formation.

4 knights * 4 action minimum = 16 minimum actions for all knights involved.

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Venkatachalam J
Apr 5, 2016

Each Knight require 4 moves. Move the knights (k1,k2,k3,k4) one by one cw (or) ccw(one cycle) in the cyclic order. (4 cycle, 4 times=16 moves)

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Yatin Khanna
Mar 7, 2016
  • After a lot of thinking, these are the 16 steps I deduced.
  • ( Assume that the columns are 1, 2 and 3 while the rows are A,B and C. White knight on top left is WK1 and top right one is BK1 and others I hope you understand.)
  • WK1- a1 to c2
  • WK2- c1 to b3
  • BK1- a3 to b1
  • BK2 - c3 to a2
  • WK1 - c2 to a3
  • BK1- b1 to c3
  • BK2- a2 to c1
  • BK1- c3 to a2
  • WK1- a3 to b1
  • WK1 - b1 to c3
  • WK2 - b3 to a1
  • WK2- a1 to c2
  • WK2- c2 to a3
  • BK2- c1 to b3
  • BK1- a2 to c1
  • BK2- b3 to a1

NOW ALL KNIGHTS ARE ON OPPOSITE SQUARES.

  • NOTE: THERE MAY BE OTHER POSSIBILITIES TOO AND MOREOVER I DONT HAVE ANY MATHEMATICAL PROOF TO WHY 16 IS THE LOWEST NUMBER OF MOVES BUT SINCE IT IS CORRECT ANSWER THUS I HAVE POSTED THE MOVES.
0 Helpful 0 Interesting 0 Brilliant 0 Confused

This is confusing since you've used the term "move" for what is thought of as a "ply." Altogether you could complete the game in 8 moves of 16 plies, which is difficult to reconcile since this game isn't competitive. Perhaps rewording the question would be helpful.

Desmond Sheppard - 5 years, 2 months ago

Log in to reply

The game given above is a single player game, not a 2 player game. Thus, one move is what u call one "ply". Nevertheless, I agree that for a regular chess player it is confusing.

Yatin Khanna - 5 years, 2 months ago

Your solution involves moving a knight of the same color twice in a row, which the original question doesn't allow. The following is the 8/16 move solution I came up with. Because I am a chess player I put the knights on a2, a4, c2, and c4 to start.

  1. Nb4 N2a3
  2. Nc3 Nb2
  3. Nc2 Nac4
  4. Na3 Na4 5 Na2 Ncb2
  5. Nb4 Nc3
  6. Nbc2 Nba4
  7. Nc4 Na2

Daniel Johnston - 5 years ago

Log in to reply

Was the question edited sometimes in the near past? I never noticed the condition of alternate movement of white and black knights. Either it has been edited, or else I have a very bad sight.

Yatin Khanna - 5 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...