This week the #puzzle is: Can You Hop Around the Chessboard? #chess #combinations #coding

A frog is hopping around a chessboard, always from the center of one square to the center of another square. Each square has side length 1, but the board itself is not necessarily 8-by-8. Instead, it’s N-by-N, where N is some large whole number.

Every jump the frog makes must be the same distance, which we’ll call L. The frog wants to make four jumps such that:

– After the fourth jump, the frog has returned to its starting square. – The frog visits a total of four distinct squares along the way, including the square on which it starts (and also stops). – The path the frog takes is not a square loop. – The frog is never on a square that is diagonal (i.e., a bishop’s move away) or horizontal/vertical (i.e., a rook’s move away) from the starting square.

What is the smallest jumping distance L for which this is possible?

And for extra credit:

The frog is jumping around the board with the same minimum distance L you just found.

But this time, the frog also wants to be able to hop to every location on the chessboard. What is the minimum value of N for which this is possible?

Can You Hop Around the Chessboard?

Solution, possibly incorrect:

Program ProofWiki

Method 1. I write a program to go through all the options. Increase L until all requirements are met. Actually, let’s write out those requirements:

1. The frog jumps distance L every time. Each jump goes integer lengths in the x and y directions. E.g. a jump of length √10 could go 3 in the x direction and 1 in the y direction. Describe this jump as (3,1).
2. The frog makes 4 jumps, returning to the starting point, describing some sort of loop.
   • Let’s call these jumps (x₁,y₁), (x₂,y₂), (x₃,y₃) and (x₄,y₄). E.g., the first jump (assume a standard coordinate system) is from (0,0) to the first landing point (x₁,y₁). The next jump will go to (x₁ + x₂,y₁ + y₂). Etc. All 4 jumps will lead back to (0,0).
3. The 4 landing points, (0,0), (x₁,y₁) etc. are different.
4. The loop is not a square.
5. None of the landing points are on a horizontal or vertical line from the starting point.
   1. No (0,y) or (x,0) points.
   2. No (x,x) or (x,-x) points.

Also, let’s look at a few examples below. All of these violate 1 or more requirements. (G is just a doodle, an inspiration for H.)

---

All of these examples of doing it wrong tells us something. But we’ll come back to that.

In my code I focus on finding 2 different ways to combine 2 jumps to reach the same point (x,y). I assume the point has 0 < x, y, WLOG. I assume x < y, again WLOG. I test whether my 4 jumps describe a square (then the jumps would be something like (x₁,y₁), (-y₁,x₁), (-x₁,-y₁) and (y₁,-x₁) like in illustration C above). And I’m done:

( 1, 3) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> (-7, 4) -> ( 8,-1)
		(0,0) -> ( 8,-1) -> (-7, 4)
( 1, 5) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> (-7, 4) -> ( 8, 1)
		(0,0) -> ( 8, 1) -> (-7, 4)
( 3,15) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> (-1, 8) -> ( 4, 7)
		(0,0) -> ( 4, 7) -> (-1, 8)
( 4, 6) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> (-4, 7) -> ( 8,-1)
		(0,0) -> ( 8,-1) -> (-4, 7)
( 4, 8) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> (-4, 7) -> ( 8, 1)
		(0,0) -> ( 8, 1) -> (-4, 7)
( 6,12) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> (-1, 8) -> ( 7, 4)
		(0,0) -> ( 7, 4) -> (-1, 8)
( 5,15) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> ( 1, 8) -> ( 4, 7)
		(0,0) -> ( 4, 7) -> ( 1, 8)
( 8,12) can be reached in 2+ ways. (L^2 = 65.)
		(0,0) -> ( 1, 8) -> ( 7, 4)
		(0,0) -> ( 7, 4) -> ( 1, 8)

The illustrations below show each of these solutions.

K and P are the same. L and M are the same. N, O and Q are the same.

These solutions correspond to L = √65.

Method 2: All the illustrations above show loops, where (x₁,y₁), (x₂,y₂), (x₃,y₃) and (x₄,y₄) are strongly related. There are 2 variants:

• G and H are actually impossible. 2 jumps would be equal in every way, (x₁,y₁) = (x₃,y₃). But then at least 1 other jump would be too long.
• The rest have (x₁,y₁), (x₂,y₂), (-x₁,-y₁) and (-x₂,-y₂).

The loop is a parallelogram. There are 2 pairs of parallel sides. Everything reduces to 4 variables: x₁, y₁, x₂, and y₂. We know x₁² + y₁² = x₂² + y₂² = L². Also x₁ != y₁ and x₂ != y₂. So we’re looking for 2 different ways to write a number as the sum of 2 squares. And yes, this has already been investigated. ProofWiki points me towards a list. The first candidate can be thrown out, as one of the sums is 5² + 5². But the next is the same result I have already found.

And for extra credit:

I expand my program to look for “knight’s tour” paths. (Warnsdorff’s Algorithm for the win.) I easily find one for a 15×15 board:

  0  39   2  43   4 159 214  55 196 175 100 115  78  19  30 
135 212 127 204  77  18  29  14  67  74  21 138 143 184 189 
 62  73  22  95 142 133 210 145 136 207 128 205  26  59  28 
131 208 149 162 151 106 103  24 109  84  57  96  33  98  35 
108 193 178 101 114  81  36  31  40 153  44 155 158 215  86 
 13  70  47 140 169 220 187 190 217 192 203 122 119   8  15 
222 171 200 123 198  11  90  63  52  93  50 141 168 219 146 
  5 112  83  56 167 174  99 116 223 160 163  54 197 104  89 
 38   1  42   3 156 213  88 195 180 185 176  79  68  75  20 
181 134 211 126 121  76  17  66  71  60 139 144 137 188 183 
 72  61  94  23 132 209 148 165 172 129 206  25 110  27  58 
117 130 161 150 107 152 105 102 113  82  85  32  97  34  45 
194 179 186 177  80  69  46  37 118  41 154 157 216  87 202 
 65  12  91  48 221 170 201 182 191 218 125 120   7  16   9 
166 173 124 199   6 111  10  53  64  51  92  49 224 147 164 

This makes sense, as 15 = 8 + 7, the 2 largest numbers involved in the jumps. (ETA: Should probably be 8 + 7 + 1 = 16.) I randomly assume, that I begin at (0,0). So N <= 15.

Video:

I modify my program to look at all connected boards. When all cells can be reached from (0,0). (Because then all cells can reach each other.) 14×14 works, 13×13 does not. N = 14. Apparently all cells can be reached in 6 jumps or less.

ETA: The N/O/Q type loop is also possible on this board, as it requires 13 x 9 cells.

ETA: A frog’s tour is easy to find on a 14×14 board, when beginning at (1,1).