logical deduction - Coloring the Chess Board

We have 8x8 Chess board like grid (8x8 2D matrix) and we are trying to color every single square/cell. But the rules are interesting;

• You may start from any square you want and color that square for the beginning.


• You can continue coloring another square in the grid which is $4$ or $5$ squares away from the square you started and colored from and so on (vertically or horizontally).


• You cannot color the same square you colored before or come back again on that.

What is the maximum amount of squares you can color with the given rule above?

Answer

The one-dimensional problem can be solved as follows:

|2|4|6|8|1|3|5|7|

Since we start and end at a central square, we can use the same strategy on the Y-axis and colour one row at a time. In the end we'll have coloured all 64 squares.

Using chessboard coordinates:

e5 a5 f5 b5 g5 c5 h5 d5
d1 h1 c1 g1 b1 f1 a1 e1

e6 a6 f6 b6 g6 c6 h6 d6
d2 h2 c2 g2 b2 f2 a2 e2
e7 a7 f7 b7 g7 c7 h7 d7
d3 h3 c3 g3 b3 f3 a3 e3
e8 a8 f8 b8 g8 c8 h8 d8
d4 h4 c4 g4 b4 f4 a4 e4