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?
In general, we want to find the equivalent of a knight's tour, a path taken by a knight that visits all of the squares on the chess board exactly once. The frog doesn't specify that it wants to start and end his tour of the board at the same spot, so this is known as an ``open'' tour, as opposed to a closed tour that starts and ends on the same square. In particular, if we hadn't added the extra condition of not being a rook's move away from the starting spot and could stick with knight moves for the frog, then the smallest possible board that has a knight's tour is a $5\times 5$ board. One heuristic method for finding knight's tour is known by Warnsdorf's rule: Move from the current square to the neighbor that has the fewest remaining viable moves.
Ok, so we found $L = \sqrt{65},$ which means any of the 16 possible steps: $(\pm 1, \pm 8),$ $(\pm 8, \pm 1),$ $(\pm 4, \pm 7),$ $(\pm 7, \pm 4).$ For $N\leq 13,$ there are inaccessible squares, e.g. on a $13\times 13$ board, the center square $g7$ has no adjacent squares, since each of the borders are only $6$ squares away from the center, so any frog jump away from the center square will end up off the board.
For $N=14,$ using a modified Warnsdorf's rule heuristi, we can find an open frog’s tour of all squares on a $14 \times 14$ board, see below using algebraic notation:
| 1. | a1 | 29. | j14 | 57. | g7 | 85. | e5 | 113. | n2 | 141. | d14 | 169. | l2 |
| 2. | h5 | 30. | k6 | 58. | n11 | 86. | d13 | 114. | j9 | 142. | e6 | 170. | d1 |
| 3. | g13 | 31. | l14 | 59. | m3 | 87. | k9 | 115. | f2 | 143. | f14 | 171. | k5 |
| 4. | n9 | 32. | h7 | 60. | f7 | 88. | d5 | 116. | m6 | 144. | m10 | 172. | c6 |
| 5. | m1 | 33. | a11 | 61. | b14 | 89. | l6 | 117. | e7 | 145. | f6 | 173. | j2 |
| 6. | i8 | 34. | e4 | 62. | i10 | 90. | k14 | 118. | i14 | 146. | m2 | 174. | k10 |
| 7. | a9 | 35. | d12 | 63. | e3 | 91. | d10 | 119. | j6 | 147. | e1 | 175. | c11 |
| 8. | b1 | 36. | c4 | 64. | a10 | 92. | e2 | 120. | n13 | 148. | l5 | 176. | k12 |
| 9. | f8 | 37. | b12 | 65. | b2 | 93. | i9 | 121. | f12 | 149. | e9 | 177. | j4 |
| 10. | n7 | 38. | f5 | 66. | j1 | 94. | b13 | 122. | m8 | 150. | i2 | 178. | b3 |
| 11. | g3 | 39. | n4 | 67. | n8 | 95. | c5 | 123. | i1 | 151. | h10 | 179. | i7 |
| 12. | h11 | 40. | m12 | 68. | g4 | 96. | g12 | 124. | a2 | 152. | a14 | 180. | b11 |
| 13. | a7 | 41. | l4 | 69. | h12 | 97. | f4 | 125. | h6 | 153. | i13 | 181. | j10 |
| 14. | h3 | 42. | e8 | 70. | a8 | 98. | e12 | 126. | g14 | 154. | b9 | 182. | k2 |
| 15. | g11 | 43. | l12 | 71. | h4 | 99. | a5 | 127. | n10 | 155. | i5 | 183. | c3 |
| 16. | k4 | 44. | m4 | 72. | l11 | 100. | i6 | 128. | g6 | 156. | a6 | 184. | j7 |
| 17. | d8 | 45. | i11 | 73. | k3 | 101. | e13 | 129. | c13 | 157. | h2 | 185. | b6 |
| 18. | h1 | 46. | a12 | 74. | j11 | 102. | l9 | 130. | b5 | 158. | g10 | 186. | c14 |
| 19. | l8 | 47. | b4 | 75. | i3 | 103. | k1 | 131. | a13 | 159. | n14 | 187. | k13 |
| 20. | d7 | 48. | j3 | 76. | b7 | 104. | g8 | 132. | h9 | 160. | f13 | 188. | d9 |
| 21. | h14 | 49. | c7 | 77. | j8 | 105. | n12 | 133. | g1 | 161. | g5 | 189. | c1 |
| 22. | l7 | 50. | k8 | 78. | n1 | 106. | f11 | 134. | c8 | 162. | h13 | 190. | j5 |
| 23. | e11 | 51. | d4 | 79. | m9 | 107. | m7 | 135. | j12 | 163. | d6 | 191. | c9 |
| 24. | a4 | 52. | c12 | 80. | e10 | 108. | f3 | 136. | n5 | 164. | e14 | 192. | j13 |
| 25. | h8 | 53. | k11 | 81. | a3 | 109. | b10 | 137. | m13 | 165. | l10 | 193. | n6 |
| 26. | l1 | 54. | l3 | 82. | i4 | 110. | c2 | 138. | f9 | 166. | d11 | 194. | g2 |
| 27. | d2 | 55. | m11 | 83. | b8 | 111. | g9 | 139. | m5 | 167. | k7 | 195. | f10 |
| 28. | c10 | 56. | n3 | 84. | i12 | 112. | f1 | 140. | l13 | 168. | d3 | 196. | m14 |
So, we have shown that if all the frog wanted was to make jumps of size $L=\sqrt{65}$ and have an open tour of the entire board, then $N=14$ would be the minimal size of the chess board.
However, covering bases and doing a deep grammatical scrub of the prompt, since it says the frog “also wants to be able to hop to every location on the chessboard", it means that the frog must still want to be able to do its rhomboidal path from the Classic problem. Since the path goes from $(-4,-7)$ to $(1,8),$ we need to have at least $N=16$ squares, that is, $\{-7, -6, \dots, -1, 0, 1, \dots, 8\}.$ This would rule out our $14 \times 14$ frog's path. However, we can again use Warnsdorf's rule to find a frog’s tour of all squares on a $16\times 16$ board, see below:
| 1. | a1 | 33. | m11 | 65. | j12 | 97. | f8 | 129. | l6 | 161. | c13 | 193. | i15 | 225. | d12 |
| 2. | i2 | 34. | e10 | 66. | b13 | 98. | b15 | 130. | d5 | 162. | k12 | 194. | j7 | 226. | k8 |
| 3. | a3 | 35. | m9 | 67. | j14 | 99. | a7 | 131. | k1 | 163. | l4 | 195. | b8 | 227. | j16 |
| 4. | b11 | 36. | n1 | 68. | c10 | 100. | h11 | 132. | l9 | 164. | e8 | 196. | f1 | 228. | f9 |
| 5. | c3 | 37. | f2 | 69. | g3 | 101. | a15 | 133. | p16 | 165. | i1 | 197. | e9 | 229. | m5 |
| 6. | d11 | 38. | n3 | 70. | n7 | 102. | i14 | 134. | o8 | 166. | h9 | 198. | i16 | 230. | l13 |
| 7. | e3 | 39. | f4 | 71. | m15 | 103. | h6 | 135. | g9 | 167. | d16 | 199. | h8 | 231. | d14 |
| 8. | a10 | 40. | g12 | 72. | f11 | 104. | a2 | 136. | c16 | 168. | l15 | 200. | d1 | 232. | h7 |
| 9. | b2 | 41. | o11 | 73. | b4 | 105. | i3 | 137. | d8 | 169. | m7 | 201. | l2 | 233. | p6 |
| 10. | j1 | 42. | g10 | 74. | a12 | 106. | a4 | 138. | l7 | 170. | n15 | 202. | p9 | 234. | h5 |
| 11. | c5 | 43. | o9 | 75. | i13 | 107. | b12 | 139. | k15 | 171. | o7 | 203. | h10 | 235. | o1 |
| 12. | k4 | 44. | p1 | 76. | j5 | 108. | j11 | 140. | c14 | 172. | h3 | 204. | d3 | 236. | g2 |
| 13. | l12 | 45. | h2 | 77. | c1 | 109. | b10 | 141. | d6 | 173. | g11 | 205. | c11 | 237. | n6 |
| 14. | m4 | 46. | p3 | 78. | b9 | 110. | f3 | 142. | l5 | 174. | c4 | 206. | k10 | 238. | m14 |
| 15. | n12 | 47. | h4 | 79. | j10 | 111. | n4 | 143. | p12 | 175. | j8 | 207. | c9 | 239. | f10 |
| 16. | g16 | 48. | p5 | 80. | k2 | 112. | f5 | 144. | o4 | 176. | k16 | 208. | j13 | 240. | n9 |
| 17. | o15 | 49. | o13 | 81. | l10 | 113. | m1 | 145. | k11 | 177. | l8 | 209. | k5 | 241. | j2 |
| 18. | p7 | 50. | k6 | 82. | m2 | 114. | e2 | 146. | d7 | 178. | p15 | 210. | d9 | 242. | b3 |
| 19. | l14 | 51. | d2 | 83. | n10 | 115. | d10 | 147. | h14 | 179. | i11 | 211. | h16 | 243. | i7 |
| 20. | d13 | 52. | l1 | 84. | j3 | 116. | c2 | 148. | g6 | 180. | b7 | 212. | o12 | 244. | p11 |
| 21. | e5 | 53. | k9 | 85. | c7 | 117. | k3 | 149. | k13 | 181. | j6 | 213. | p4 | 245. | o3 |
| 22. | m6 | 54. | o16 | 86. | g14 | 118. | o10 | 150. | c12 | 182. | b5 | 214. | i8 | 246. | n11 |
| 23. | n14 | 55. | p8 | 87. | f6 | 119. | n2 | 151. | g5 | 183. | a13 | 215. | e1 | 247. | g15 |
| 24. | f13 | 56. | i4 | 88. | e14 | 120. | m10 | 152. | o6 | 184. | e6 | 216. | a8 | 248. | o14 |
| 25. | b6 | 57. | a5 | 89. | m13 | 121. | e11 | 153. | p14 | 185. | f14 | 217. | e15 | 249. | g13 |
| 26. | a14 | 58. | e12 | 90. | i6 | 122. | m12 | 154. | h15 | 186. | n13 | 218. | l11 | 250. | c6 |
| 27. | e7 | 59. | d4 | 91. | p2 | 123. | e13 | 155. | g7 | 187. | f12 | 219. | m3 | 251. | k7 |
| 28. | d15 | 60. | l3 | 92. | h1 | 124. | a6 | 156. | k14 | 188. | m16 | 220. | f7 | 252. | j15 |
| 29. | l16 | 61. | p10 | 93. | o5 | 125. | i5 | 157. | c15 | 189. | n8 | 221. | b14 | 253. | b16 |
| 30. | m8 | 62. | o2 | 94. | p13 | 126. | b1 | 158. | g8 | 190. | g4 | 222. | i10 | 254. | c8 |
| 31. | n16 | 63. | g1 | 95. | i9 | 127. | a9 | 159. | f16 | 191. | h12 | 223. | a11 | 255. | j4 |
| 32. | f15 | 64. | n5 | 96. | e16 | 128. | h13 | 160. | j9 | 192. | a16 | 224. | e4 | 256. | i12 |
So, we have shown that if the frog wanted both to make jumps of size $L=\sqrt{65}$ in a rhombus pattern from the Classic problem and have an open tour of the entire board, then $N=16$ is the minimal size of the chess board.
No comments:
Post a Comment