# King on chessboard

Suppose we have empty chessboard, and king on A1

King can move either up (a1-a2) or right (a1-b1), how many possible routes can king take to arrive at h8?

My thoughts are to retrace kings moves backward - ie king can arrive on h8 from either h7 or g8, king can arrive on b1 only from one square - a1.

However, when I try simplify/visualise route, it doesnt quite work that way, let me elaborate.

Lets take 2x3 board:

OO

OO

XO

There is distinctly 3 ways to arrive at

OX

OO

OO

By either moving to right, up, up

up, right, up

or up, up, right

However when i count possibilities to arrive:

12

12

11

2*2=4, not 3.. What am I missing here?

• ...Kings can move diagonally. For instance king to b2 would be a valid first move. Also, can the king only visit each square once? Because if not there are infinitely many routes. – miradulo Jan 20 '16 at 13:32
• Can king move backward? Or only right/up – Cloverr Jan 20 '16 at 13:37
• I am aware of that. King can move down and left too, but we leave this away, our king moves only to right or upwards. – Timo Junolainen Jan 20 '16 at 13:38
• @TimoJunolainen I see. You might want to edit your question to be more clear then. – miradulo Jan 20 '16 at 13:39

Starting from $\langle 0,0\rangle$ and going to $\langle n,m\rangle$ where $n,m$ are nonnegative integers, and under the condition that by each step one of the coordinates increases with $1$ you must make $n+m$ steps in total. Exactly $n$ steps must be elected to be one of the steps where the first coordinate grows.
There are:$$\binom{n+m}n$$ possible selections.
If your king can only move up and right, then you know that the king will take precisely $14$ moves to reach the end.
$7$ of those moves will be moves to the right, and $7$ will be moves upward. You only need to choose which seven moves out of the 14 possible moves will be moves to the right, and once you do that, the path of the king is set.