In how many ways can a king( as in chess ) move from one square to another diagonal square at the end of six moves?

Question

I was able to solve a variant of this in which the king could not move diagonally, but I feel that the method I used for that is not the most efficient one. So, how do I approach this prob?

Answer 1

Brute force is one way:

Let's write, on the chessboard, how many ways there are for a king to get to each square within a specific number of moves. For $0$ moves, we get $$ \begin{array}{|c|c|c|} \hline 0&0&0\\ \hline 0&\color{red}1&0\\ \hline 0&0&0\\ \hline \end{array} $$ because there is only one square the king can get to, and that's the square he starts at. Now, the way we are going to go from one step to the next is that we are going to pass a "filter" over all these cells. We will draw a new board, and for each cell in this new board, we will look at the corresponding cell in the previous board and add together all the numbers in its $8$ neighboring cells. So, for 1 move we get $$ \begin{array}{|c|c|c|c|c|} \hline 0&0&0&0&0\\ \hline 0&1&1&1&0\\ \hline 0&1&\color{red}0&1&0\\ \hline 0&1&1&1&0\\ \hline 0&0&0&0&0\\ \hline \end{array} $$ Then for 2 moves we get $$ \begin{array}{|c|c|c|c|c|c|c|} \hline 0&0&0&0&0&0&0\\ \hline 0&1&2&3&2&1&0\\ \hline 0&2&2&4&2&2&0\\ \hline 0&3&4&\color{red}8&4&3&0\\ \hline 0&2&2&4&2&2&0\\ \hline 0&1&2&3&2&1&0\\ \hline 0&0&0&0&0&0&0\\ \hline \end{array} $$ And finally, for $3$ moves, we get $$ \begin{array}{|c|c|c|c|c|c|c|} \hline 1&3&6&7&6&3&1\\ \hline 3&6&12&12&12&6&3\\ \hline 6&12&27&27&27&12&6\\ \hline 7&12&27&\color{red}{24}&27&12&7\\ \hline 6&12&27&27&27&12&6\\ \hline 3&6&12&12&12&6&3\\ \hline 1&3&6&7&6&3&1\\ \hline \end{array} $$ I said "finally" because we could keeep going, but it is at this point that I would like to stop. Because we have now spent 3 moves, and must use the remaining 3 moves to get to the goal square. And if we want to count up the number of ways to get from each square to the goal square using $3$ moves, we get the exact same pattern of numbers, only moved one square up and one to the right.

So what we have here is a simple way to calculate the number of ways to spend $3$ moves to get to any specific cell, and then spend $3$ moves to get to our goal square diagonally above our starting square: We take the number in any of the squares above, which represents the number of ways to get there, then multiply with the square diagonally below it, which represents the number of ways to get to the goal square.

Doing this for our entire grid gives us $$ \begin{array}{|c|c|c|c|c|c|c|} \hline 1\cdot 0&3\cdot 3&6\cdot 6&7\cdot 12&6\cdot 12&3\cdot 12&1\cdot 6\\ \hline 3\cdot 0&6\cdot 6&12\cdot 12&12\cdot 27&12\cdot 27&6\cdot 27&3\cdot 12\\ \hline 6\cdot 0&12\cdot 7&27\cdot 12&27\cdot 27&27\cdot 24&12\cdot 27&6\cdot 12\\ \hline 7\cdot 0&12\cdot 6&27\cdot 12&\color{red}{24}\cdot 27&27\cdot 27&12\cdot 27&7\cdot 12\\ \hline 6\cdot 0&12\cdot 3&27\cdot 6&27\cdot 12&27\cdot 12&12\cdot 12&6\cdot 6\\ \hline 3\cdot 0&6\cdot 1&12\cdot 3&12\cdot 6&12\cdot 7&6\cdot 6&3\cdot 3\\ \hline 1\cdot 0&3\cdot 0&6\cdot 0&7\cdot 0&6\cdot 0&3\cdot 0&1\cdot 0\\ \hline \end{array}\\ = \begin{array}{|c|c|c|c|c|c|c|} \hline 0&9&36&84&72&36&6\\ \hline 0&36&144&314&314&157&36\\ \hline 0&84&314&729&648&314&72\\ \hline 0&72&314&\color{red}{648}&729&314&84\\ \hline 0&36&157&314&314&144&36\\ \hline 0&6&36&72&84&36&9\\ \hline 0&0&0&0&0&0&0\\ \hline \end{array} $$ Now we "just" add up all these numbers, and we get our answer. If I haven't made any mistakes, the result is $6180$.

Answer 2

Let's say the king starts at $(0,0)$ and ends at $(1,1)$. If at the $i$th move he moves a signed distance $x_i$ in the $X$ direction and $y_i$ in the $Y$ direction, then we want the number of solutions in integers to $$x_1+x_2+x_3+x_4+x_5+x_6 = 1 \tag{1}\\ y_1+y_2+y_3+y_4+y_5+y_6 = 1 $$ subject to $-1 \le x_i, y_i \le 1$ and excluding any cases where $x_i=y_i=0$ for some $i$. (The king must actually move and not remain stationary at any step.) We will find the number of acceptable solutions via the Principle of Inclusion / Exclusion (PIE).

But first, let's consider the related problem of finding the number of solutions in integers of $$x_1+x_2+x_3+ \dots +x_n = 1 \tag{2}$$ subject to $-1 \le x_i \le 1$ for $1 \le i \le n$. We might think of this as finding the number of strings of $n$ symbols, where each symbol is a plus, a minus, or zero, and in which there is one more plus than the number of minuses. If there are $i$ pluses, then there must be $i-1$ minuses and $n-2i+1$ zeroes, so the number of such strings is the multinomial coefficient $$\binom{n}{i, i-1, n-2i+1} = \frac{n!}{i! (i-1)! (n-2i+1)!}$$ Then the total number of solutions of $(2)$ is $$a_n = \sum_{i=1}^{\lfloor (n+1)/2 \rfloor} \binom{n}{i, i-1, n-2i+1}$$

Now back to the problem of determining the number of paths from $(0,0)$ to $(1,1)$. If we were to disregard the requirement that we can never have $x_i=y_i=0$, the number of paths would be $N = a_6^2$. To find the acceptable number of paths, let's say a solution of $(1)$ has "property $i$" if $x_i=y_i=0$ for $1 \le i \le 6$, and let $S_j$ be the number of solutions with $j$ of the properties, for $1 \le j \le 5$. If we have $x_i=y_i=0$ for $j$ choices of $i$, then the remaining $(6-j)$ $x_i$'s must still sum to $1$, as must the remaining $(6-j)$ $y_i$'s. Since there are $\binom{6}{j}$ ways to select the set of "bad" indicies, $$S_j = \binom{6}{j} a_{6-j}^2$$ By PIE, the number of solutions of $(1)$ with none of the properties, i.e. the number of solutions in which there is no $i$ with $x_i=y_i=0$, is $$N + \sum_{j=1}^5 (-1)^j S_j = a_6^2 + \sum_{j=1}^5 (-1)^j \binom{6}{j} a_{6-j}^2 = \boxed{6900}$$