Knight moves

[BMAD]

Put a knight on a 4x4 chessboard that is able to make standard moves only. How many moves must it take until it is able to land on every square? Does it matter where it begins? What if the board was 5x5?

[gavinksong]

A B C D

C D A B

B A D C

D C B A

 

From any lettered tile, you can visit all the other tiles with the same letter and finish on the same letter without visiting the same tile twice.

The "center/corner" tiles are the A's and D's. The "side" tiles are the B's and C's.

From any "side" tile, you can jump to a "center" tile, and vice versa. All optimal solutions go side, center/corner, side, center/corner.

 

For example, you can visit all the B's, then all the A's, then all the C's, then all the D's. Like this...

 

07 00 11 14

10 13 04 01

03 06 15 12

16 09 02 05

 

...visiting only the 04 tile twice, for a total of 16 jumps.

Edited February 13, 2015 by gavinksong

[bonanova]

Beginning in a corner, 15 squares can be visited without revisiting a square (14 moves.) Reaching the 16th square requires 3 additional moves. It matters that we start in a corner, since returning to the starting square (making a cycle) requires five additional moves. That is, moving between adjacent corners requires the maximum number of 5 moves. So starting and ending on adjacent corners is optimal (eliminating the longest move in a cycle) if a cycle is not required.

 

I don't yet have a solution for 5x5.

[gavinksong]

The smallest number of moves required for a 4x4 board is 16.

[bonanova]

@gs, your solution is better. Which square did you start on?

[gavinksong]

@gs, your solution is better. Which square did you start on?

 

the side.

[gavinksong]

Seeing as how I got a different result than bonanova, I will try to justify my response.

 

If the knight is on one of two corners (A), there are only two tiles (B) that it can go:

 

A X X X

X X B X

X B X X

X X X A

 

Conversely, a knight can only arrive at an A tile from a B tile.

These tiles form a "corner circuit" which the knight cannot escape without jumping to a side tile.

 

Let's suppose the knight wants to visit both A tiles without visiting the same tile more than once. Then, the knight must start or end on an A tile, from or to which it cannot move without visiting a visited tile. Thus, if we want to visit all four corners, the knight must start and end on a corner tile.

 

So the knight starts on a corner tile, runs the circuit, and finds itself on a center tile. To visit the other corner circuit, it must first go to a side tile.

 

A knight on a side tile has three options. It can jump to one of two other side tiles or a center tile.

If a knight is on a side tile, it is locked into one of two different "side circuits" that it cannot escape without jumping to a center tile.

 

X A X X        X X B X

X X X A        B X X X

A X X X        X X X B

X X A X        X B X X

 

Thus, the knight cannot visit all the side tiles without eventually visiting a center tile. In other words, it is unavoidable to land on the same tile at least once because if we follow our current plan of starting and ending with the corner circuits, we may visit a center tile more than once, and if we deviate from our plan, we must land on the same tile more than once anyways.

 

The lower bound is then 16 jumps, which is 1 more jump than if we could visit all the tiles just once. There are actually multiple similar ways to achieve 16 jumps as long as you don't start on a center tile. One way is to run a corner circuit, run a side circuit, jump to a center tile, run the other side circuit, and then run the other corner circuit.

Edited January 15, 2015 by gavinksong

[gavinksong]

 

Seeing as how I got a different result than bonanova, I will try to justify my response.

 

If the knight is on one of two corners (A), there are only two tiles (B) that it can go:

 

A X X X

X X B X

X B X X

X X X A

 

Conversely, a knight can only arrive at an A tile from a B tile.

These tiles form a "corner circuit" which the knight cannot escape without jumping to a side tile.

 

Let's suppose the knight wants to visit both A tiles without visiting the same tile more than once. Then, the knight must start or end on an A tile, from or to which it cannot move without visiting a visited tile. Thus, if we want to visit all four corners, the knight must start and end on a corner tile.

 

So the knight starts on a corner tile, runs the circuit, and finds itself on a center tile. To visit the other corner circuit, it must first go to a side tile.

 

A knight on a side tile has three options. It can jump to one of two other side tiles or a center tile.

If a knight is on a side tile, it is locked into one of two different "side circuits" that it cannot escape without jumping to a center tile.

 

X A X X        X X B X

X X X A        B X X X

A X X X        X X X B

X X A X        X B X X

 

Thus, the knight cannot visit all the side tiles without eventually visiting a center tile. In other words, it is unavoidable to land on the same tile at least once because if we follow our current plan of starting and ending with the corner circuits, we may visit a center tile more than once, and if we deviate from our plan, we must land on the same tile more than once anyways.

 

The lower bound is then 16 jumps, which is 1 more jump than if we could visit all the tiles just once. There are actually multiple similar ways to achieve 16 jumps as long as you don't start on a center tile. One way is to run a corner circuit, run a side circuit, jump to a center tile, run the other side circuit, and then run the other corner circuit.

 

 

The solution I described at the end does not work. Here is one that does: run a side circuit, run a corner circuit, revisit a center tile, run the other side circuit, and then run the other corner circuit.