<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/grim-knight-a-riddle/"></div></div><div><a data-url="https://www.r-bloggers.com/grim-knight-a-riddle/" data-counturl="https://www.r-bloggers.com/grim-knight-a-riddle/" data-count="horizontal" data-text="grim knight [a riddle]" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2016/10/14/grim-knight-a-riddle/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><a target="_blank" href="https://i0.wp.com/xianblog.files.wordpress.com/2016/10/horsun-e1476260410583.jpg?ssl=1"><img alt="" class="wp-image-31736" src="https://i0.wp.com/xianblog.files.wordpress.com/2016/10/horsun-e1476260410583.jpg?resize=333%2C390&ssl=1" data-recalc-dims="1"></a><a target="_blank" href="http://fivethirtyeight.com/features/how-about-a-nice-game-of-chess/">The Riddler of this week</a> had a riddle that is a variation of the <a target="_blank" href="https://en.wikipedia.org/wiki/Knight%27s_tour">knight tour problem</a>, namely</p>
<blockquote><p><span><em>“…how long is the longest path a <a target="_blank" href="https://en.wikipedia.org/wiki/Knight_%28chess%29">knight</a> can travel on a standard 8-by-8 chessboard without letting the path intersect itself?”</em></span></p>
</blockquote>
<p>the riddle being then one of a self-avoiding random walk [kind]… As I could not get back to sleep last night, I spent a couple hours (!) on this riddle, programming a random walk [or more accurately, a random canter]. This is a brute-force approach in that I pick any acceptable move with the same probability and stop when there is no further move available. [The title refers to the recommendation <a target="_blank" href="https://en.wikipedia.org/wiki/Knight_%28chess%29">to avoid the rim of the chessboard with a knight</a>: “a knight on the rim is grim”…]</p>
<pre>
board=rep(1,64)
curr=sample(1:64,1)
board[curr]=0
cont=0
stop=TRUE
while (stop){
  mov=nexx(curr,board)
  curr=mov$mov;board=mov$boa
  stop=(curr>0);cont=cont+stop}
</pre>
<p>with my function <em>nexx</em> a rather clumsy 50 lines business of selecting one acceptable move from the current position <em>curr</em>. This function returns the proposed move as well as the updated board with zeros in squares already visited by the knight. Which highlights the ambiguity in the question, namely how one defines the path of a knight? For an acceptable knight move from A to B, there are two possible paths: either take two steps in one direction and one in the orthogonal direction or the opposite. I thus pick one of the two (at random) and prohibit further visits to those squares. An alternative meaning of the question could be that the line joining A to B cannot be crossed ever again, which excludes less moves (but is more cumbersome to code). Anyway, with the former interpretation of a <em>path</em>, repeating the self-avoiding moves led to a maximum of 19 moves, with one solution exhibited below. (Since (64-1)/3=21, it is conceivable that the true maximum is 20 or even 21. In the path representation below, it seems possible to include yet another move by going to (4,1) instead of (4,5). But this is apparently excluded by the square representation on the right. Why is why the path representation is somewhat confusing!)</p>
<p><a target="_blank" href="https://i2.wp.com/xianblog.files.wordpress.com/2016/10/riddlerchk1.jpg?ssl=1"><img alt="" class="wp-image-31741" src="https://i2.wp.com/xianblog.files.wordpress.com/2016/10/riddlerchk1.jpg?resize=200%2C200&ssl=1" data-recalc-dims="1"></a><a target="_blank" href="https://i2.wp.com/xianblog.files.wordpress.com/2016/10/riddlerchk2.jpg?ssl=1"><img alt="riddlerchk" class="wp-image-31742" src="https://i2.wp.com/xianblog.files.wordpress.com/2016/10/riddlerchk2.jpg?resize=201%2C201&ssl=1" data-recalc-dims="1"></a></p>
<p>Filed under: <a target="_blank" href="https://xianblog.wordpress.com/category/kids/">Kids</a>, <a target="_blank" href="https://xianblog.wordpress.com/category/pictures/">pictures</a>, <a target="_blank" href="https://xianblog.wordpress.com/category/statistics/r-statistics/">R</a> Tagged: <a target="_blank" href="https://xianblog.wordpress.com/tag/chess/">chess</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/r/">R</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/self-avoiding-random-walk/">self-avoiding random walk</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/the-riddler/">The Riddler</a> <a target="_blank" rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/31735/"><img alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/31735/" border="0"></a> <img alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" border="0" data-recalc-dims="1"></p>
<p><div><div><div><div data-width="55" data-show-faces="false" data-send="true" data-layout="box_count" data-height="62" data-href="https://www.r-bloggers.com/grim-knight-a-riddle/"></div></div><div><a data-url="https://www.r-bloggers.com/grim-knight-a-riddle/" data-counturl="https://www.r-bloggers.com/grim-knight-a-riddle/" data-count="vertical" data-text="grim knight [a riddle]" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2016/10/14/grim-knight-a-riddle/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/?s=data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/?s=Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/?s=map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/?s=animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/?s=RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/?s=sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/?s=LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/?s=SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/?s=eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/?s=git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/?s=hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/?s=Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/?s=PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/?s=time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/?s=trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/u7mnffuVn6I"></a></div>