# Some observations on Pen and Paper (#90) or to make it fast, **URL:** \ **Category:** Ruby\ **Created:** [August 16, 2006, 6:48pm UTC](https://www.ruby-forum.com/t/some-observations-on-pen-and-paper-90-or-to-make-it-fast/65188 "2006-08-16T18:48:31Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [August 16, 2006, 6:48pm UTC](https://www.ruby-forum.com/t/some-observations-on-pen-and-paper-90-or-to-make-it-fast/65188/1 "2006-08-16T18:48:31Z")
Looking at the solutions posted so far, it seems: 1. Those who have done best have recognized the relation between this problem and the well-known Knight’s Tour problem first posed by Leonhard Euler in 1758. 2. Some, like me, solved the problem with a straightforward backtracking approach. This approach is well known to get slow quickly with increasing board sizes. At least this approach provably will find a solution if it exists, or announce correctly that it doesn’t. So this is a point for us 18th century types. 3. The fast ones seem to be based on Warnsdorff’s algorithm for the Knight’s tour which was published in 1823. So those guys are at least in the 19th century. However, sometime after the advent of computers, it was shown that Warnsdorff’s approach runs into blind alleys for boards bigger than 76x76. > **[Knight's Tour -- from Wolfram MathWorld](https://mathworld.wolfram.com/KnightsTour.html)** I’m not sure if anyone has gotten into the 20th century. In 1992, Conrad, et al. found an algorithm which subdivides the board into smaller pieces of 8x8 or less, finds a path for each sub-piece which links from one sub-piece to another in an order which covers the board. Because solving the small boards is very quick, this divide-and-conquer approach works really well. I don’t think that anyone has attempted to solve the quiz using Conrad’s approach. The complications seem to be correctly carving up the board, stringing the sub-boards together in some sequence, and finding paths which allow movement from one sub-board to another in that sequence. I thought I saw someone say that his solution sub-divided the board up, but I can’t seem to find it now. The key observation is that the key to making a program fast is to find the right algorithm. P.S. Axel Conrad’s page on the 1992 algorithm is at [http://www.axel-conrad.de/springer/springer.html](http://www.axel-conrad.de/springer/springer.html) This page is in German. The google translation is somewhat readable, and enhances the humor on Conrad’s informal report on the algorithm. ‘It was invented long ago, more than 200 years ago, more exactly in the year 1758, by a Swiss. This Swiss was not smaller than Leonhard an Euler, who sat in Berlin and a beautiful evening to these like today too does not tiefst at that time provinzielle city thought, but to something larger, to a chessboard: “An empty chessboard is given. Is there a Zugfolge, with that Springer all (black and white) fields of the board exactly once been visiting?”’ I’m guessing that “not smaller than” really should be “no less than”. I know that a Springer is the German word for a chess knight, and I guess Zugfolge is something like “path.” Then after introducing the notion of solving the problem for boards bigger than the standard 8x8 chess board: ‘As said, Euler was Swiss, and Swiss are considered generally as very conscientious and just as slow. Perhaps this applies also to the solution of Swiss problems, anyhow could the Springer problem in the next 200 years not be solved.’ – Rick DeNatale My blog on Ruby [http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/) ---
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [August 16, 2006, 7:09pm UTC](https://www.ruby-forum.com/t/some-observations-on-pen-and-paper-90-or-to-make-it-fast/65188/2 "2006-08-16T19:09:33Z")
Rick DeNatale wrote: > finding paths which allow movement from one sub-board to another in > that sequence. > > I thought I saw someone say that his solution sub-divided the board > up, but I can’t seem to find it now. It’s right here: [http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/208187](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/208187) Elliot’s solution uses 5x5 ‘pre-solved’ solutions to fill the board. -Justin ---
**Author:** ![rykkers](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e5b9ba/32.png) [@rykkers](https://www.ruby-forum.com/u/rykkers)\ **Post date:** [August 16, 2006, 7:39pm UTC](https://www.ruby-forum.com/t/some-observations-on-pen-and-paper-90-or-to-make-it-fast/65188/3 "2006-08-16T19:39:36Z")
“Rick DeNatale” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes: > However, sometime after the advent of computers, it was shown that > Warnsdorff’s approach runs into blind alleys for boards bigger than > 76x76. > [http://mathworld.wolfram.com/KnightsTour.html](http://mathworld.wolfram.com/KnightsTour.html) Yeah, I ran across that while working on an algorithm. Empirical results here would suggest that this isn’t the case for this particular set of move conditions. > I’m not sure if anyone has gotten into the 20th century. In 1992, > Conrad, et al. found an algorithm which subdivides the board into > smaller pieces of 8x8 or less, finds a path for each sub-piece which > links from one sub-piece to another in an order which covers the > board. Because solving the small boards is very quick, this > divide-and-conquer approach works really well. One of the approaches used (Elliot T.'s second solution) took this 5-by-5 solution: 17, 9, 2, 18, 24 4, 14, 22, 7, 13 1, 19, 25, 10, 20 16, 8, 3, 15, 23 5, 11, 21, 6, 12 And then replicated it over and over to cover the board. Note that this solution begins in the middle of a side and ends in the center - this means that you can jump from the end of one subsolution to the beginning of the next, and can therefore cover the entire board in an S pattern like this: -------------------- | /-------------------/ | ------------------- | /-------------------/ Of course, this only works for boards whose sizes are a multiple of five, a major disadvantage. To handle boards of arbitrary size, you’d probably have to give up on using a canned 5-by-5 solution or at the very least you’d need to have composeable solutions for 5-by-X, for X in (5…9) as well as a solution for X-by-Y for X and Y in (5…9). (But that last solution could end anywhere, since you wouldn’t need to jump away from it) Note that for boards whose sides are a multiple of 10, you could use a different pattern for where the subboards went, and as a result even get a circular solution: /--------- | /-\ /-\ | | | | | | | | | | | | | | | | | | | -/ -/ -/