Art of Knight Graph on MxN grids
- Few Knight Graphs
  - 3 x 3
  - 2 x 10
  - 4 x 4
  - 5 x 5
  - 3 x 5, 4 x 5
  - 12 x 12
- On Edges
- The Code

Art of Knight Graph on MxN grids

Problem of Chess have fascinated the human race for decades/centuries together. Im no escape! Here again, we would like to discuss the knight tour and the so called knight graph from which the tour is derieved. The knight graph is again an interesting one, artistically! Here are few snapshots of the knight graph and the code snippet to generate them.

Few Knight Graphs

3 x 3

Simple case is this 3×3 for less than this, no square could have a knight moving! The central cell is unvisited (trivially).

2 x 10

Since 2xN (N>2) is literally a place where knight could gallop! Just a specific value of N=10 is choosen. This has a special property, its also the optimal way how three strings could be used to weave so that they dont unwind so easily. (But tough to prove indeed :)

4 x 4

The graphs are increasingly good and symmetrical. As we go up higher, we find that the pattern repeats and we could see that centrally, the pattern remains invariant. We could see the square formation in this graph.

5 x 5

No words to describe! Just enjoy the beauty of the interlinks! May be one can try to count the number of squares.

3 x 5, 4 x 5

Just to check how rectangular knight graphs look.

12 x 12

This time, for a big one. As we have said before, we could see the central invariant pattern. Borders bear a different pattern. Aesthetic indeed!

On Edges

One immediate question that pop to us is that, how many edges would this graph contain? The question indeed is not very trivial till we observe this pattern on the graph:

For 3 x 3 here is the incidence edge count matrix.

$\Large A_{\small{3,3}}\ =\ \large\left(\begin{array}{ccc}&2&2&2\\&2&0&2\\&2&2&2\end{array}\right)$

For 4 x 4:

$\Large A_{\small{4,4}}\ =\ \large\left(\begin{array}{cccc} &2&3&3&2\\&3&4&4&3\\&3&4&4&3\\&2&3&3&2 \end{array}\right)$

For an N x N, we have:

$\Large A_{\small{N,N}}\ =\ \large\left( \begin{array}{ccccccccc} &2&3&4&4&\cdots&4&4&3&2\\ &3&4&6&6&\cdots&6&6&4&3\\ &4&6&8&8&\cdots&8&8&6&4\\ &\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\ &4&6&8&8&\cdots&8&8&6&4\\ &3&4&6&6&\cdots&6&6&4&3\\ &2&3&4&4&\cdots&4&4&3&2\\ \end{array}\right)$

The pattern should be trivial by now. And we find the reason why the central pattern is invariant! Afterall if we see how the knight could move, its immediately trivial that it has a maximum stretch of 8 cells symmetrically from its standing cell. So, counting the above pattern, with some algebra and some spicy chips by your side, the following simple relation could be obtained.

$E(M, N) = (2*M - 3)*(2*N - 3) - 1$

And for NxN it should be an easy substitution:

$E(N, N) = 4*(N-2)*(N-1) = 8 * \Large\Delta_{\small{N-2}}, \\ \small\text{where,} \Large{\Delta}_{\small{N}} = \frac{N*(N+1)}{2}, \small\text{N-th triangular number.}$

The Code

The code to produce above knight graphs could be found here: Code Snippets