[QUIZ] Some observations on Pen and Paper (#90) or to make it fast, choose your algorithm wisely

Discussion in 'Ruby' started by Rick DeNatale, Aug 16, 2006.

  1. 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.
    http://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

    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/
     
    Rick DeNatale, Aug 16, 2006
    #1
    1. Advertising

  2. Re: [QUIZ] Some observations on Pen and Paper (#90) or to make itfast, choose your algorithm wisely

    Rick DeNatale wrote:
    <snip>
    > 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.
    >

    <snip>


    It's right here:
    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
     
    Justin Collins, Aug 16, 2006
    #2
    1. Advertising

  3. Re: [QUIZ] Some observations on Pen and Paper (#90) or to make itfast, choose your algorithm wisely

    "Rick DeNatale" <> 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


    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 Temple'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:

    /---------\
    | /-\ /-\ |
    | | | | | |
    | | | | | |
    | | | | | |
    \-/ \-/ \-/
     
    Daniel Martin, Aug 16, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Manuel Graune

    python as pen and paper substitute

    Manuel Graune, Apr 6, 2010, in forum: Python
    Replies:
    18
    Views:
    490
    Manuel Graune
    Apr 10, 2010
  2. Ian Collins
    Replies:
    17
    Views:
    625
    Francesco S. Carta
    Aug 3, 2010
  3. Ruby Quiz

    [QUIZ] Pen and Paper (#90)

    Ruby Quiz, Aug 11, 2006, in forum: Ruby
    Replies:
    44
    Views:
    518
    Morton Goldberg
    Aug 15, 2006
  4. David Tran
    Replies:
    6
    Views:
    179
    Morton Goldberg
    Aug 17, 2006
  5. Ruby Quiz

    [SUMMARY] Pen and Paper (#90)

    Ruby Quiz, Aug 17, 2006, in forum: Ruby
    Replies:
    6
    Views:
    172
    Morton Goldberg
    Aug 18, 2006
Loading...

Share This Page