1
$\begingroup$

On an $8$ by 8 chess board, how many possible ways are there to move from
square $d_1$ (1st row from bottom and 4th column from left ) to
square $d_8$ (8th row from bottom and 4th column from left)?

You can only use 7 king moves i.e. you can move one square per move, and there are 3 ways to do so: horizontally, vertically and diagonally.
For example - $d_1, d_2, d_3, d_4, d_5, d_6, d_7, d_8$

$\endgroup$
1
$\begingroup$

I accidentally interpreted letter as row and number as column. Just rotate and/or replace the corresponding words to match your interpretation of how letters/numbers correspond to directions)

You should be able to convince yourself that the king must always go to the right, to the up-right, or to the down-right on every turn in order to arrive at d8 by the seventh move. You can use more exciting techniques which generalize easily, but with how small the numbers here are, you can map out all possibilities using a grid and putting as numbers in the grid the number of distinct paths which led to that location.

Such a grid might begin as such:

$\begin{bmatrix} & & & 1 & 4\\ & & 1 & 3 & 10 & \cdots\\ & 1 & 2 & 6 & 16\\ 1 & 1 & 3 & 7 & 19\\ & 1 & 2 & 6 & 16 & \cdots\\ & & 1 & 3 & 10\\ & & & 1 & 4 \\ & & & & 1 & \cdots \end{bmatrix}$

Create the next number in the next column by adding the number directly to the left, to the left-down and to the left-up. for example the third row fifth column entry $16$ was formed by doing $3+6+7$ and shows there are $16$ different paths you can take from $d_1$ to $c_5$ using exactly four king-moves.

Keep in mind the physical boundaries of your board so that you don't move off the edge, i.e. keep your grid as an $8\times 8$. Any time you try to add a number outside of the grid or not filled in, treat it as a zero.

$\endgroup$
2
  • $\begingroup$ Note that the $1$ at the bottom can't be used as the king wouldn't be able to make it back to $d8$. $\endgroup$
    – Jens
    Oct 30 '18 at 18:38
  • $\begingroup$ @Jens with the approach I am proposing, that is largely irrelevant. Yes, we could have opted to leave it blank and we are keeping track of several more numbers than are strictly necessary. Having completed the grid, we will have not only found the number of paths from $d_1$ to $d_8$, but also from $d_1$ to $a_8$ etc... $\endgroup$
    – JMoravitz
    Oct 30 '18 at 18:44
1
$\begingroup$

Basically you can only make three types of moves: going up, up-left or up-right. Also, the steps of going up-left must be the same as that of going up-right.

Conditioned on the steps $k$ of going up, which can only be 1, 3, 5 and 7, we have the number of ways would be $\binom{7}{k} \binom{7-k}{(7-k)/2}$. I calculated the result to be 393.

$\endgroup$
3
  • $\begingroup$ You dont have an option to make all $3$ moves on every square. Say we are on a $b5$ (5th row second column), here if we go up-left we land on $a6$ and there is no path that leads to $d8$ from that point. Also, when you are at an edge square like $a5$, again you cant go up-left. I didn't really understand what calculations you have done (referring to "which can only be 1, 3, 5 and 7) but going by the simplicity I dont think you have taken the points I just mentioned above into consideration. $\endgroup$ Oct 30 '18 at 19:04
  • 1
    $\begingroup$ @Karan Abrol "which can only be 1, 3, 5 and 7" is because the number of up-left moves must be the same as the number of up-right moves. Let us denote this number to be $i$. When $i = 0$, we can only go straight up. When $i = 3$, we can have 3 up-left moves and 3 up-right moves and 1 up move. Now say we are at b5, then either you've already have 3 up-left moves or 2 up moves. Either case we are not allowed further up-left move by the classifications. $\endgroup$
    – Jingbo Liu
    Oct 30 '18 at 19:25
  • $\begingroup$ Ah, I see, here we are eliminating the possibility of ever reaching a square from which we can't reach the $d8$. $\endgroup$ Oct 30 '18 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.