Question

King in N moves. In chess, a king can move one space in any of the 8 directions (2 vertical, 2 horizontal, 4 diagonals). Suppose our chessboard is infinite in every direction, and a king starts on a particular square. (a) How many different squares are possible locations for the king after N or fewer moves? (b) Answer the same question for a “crippled king” that can only move horizontally and vertically (no diagonal moves allowed). For both parts, show how you get your answer.

Answer 1

a) Observe that, considering the present position, the king can move in any of the neighbour squares (even the diagonal ones). Hence in the 1st move, he can move in the 8 neighbouring squares. Now after that continuing this sequence, we can say that the king can be in a area surrounding a square of side (2N + 1) in N moves or lesser. Hence the number of different squares are possible locations for the king after N or fewer moves is

(2N+1

b) In this case observe that from the current position, the crippled king's possible moves create a plus sign. Hence continuing like this, we can see that the possible locations till Nth move creates a square rotated 45^o (though it would be a bit deformed) with width of the diagonal (2N + 1) units. Hence the number of different squares are possible locations for the crippled king after N or fewer moves is

(2N (2i + 1) (2N1)2((N 1) (N - 2)N) 1) i0