BrainDen.com - Brain Teasers
• 0

# Knight moves

## Question

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?

## Recommended Posts

• 0

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 by gavinksong
##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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

the side.

##### Share on other sites

• 0

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 by gavinksong
##### Share on other sites

• 0

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.