[SUMMARY] Pen and Paper (#90)

Discussion in 'Ruby' started by Ruby Quiz, Aug 17, 2006.

  1. Ruby Quiz

    Ruby Quiz Guest

    I enjoyed this problem. It's fun to play with and gives you a little room to
    get creative with solving techniques.

    As many people pointed out, this is pretty much the Knight's Tour problem with
    some unusual Knight jumps. Most solutions will solve either problem, if you
    change their idea of neighbor squares. The good news about that is that we can
    take advantage of the shortcuts people use to solve that problem.

    The most straightforward solution to this problem is I can dream up is:

    1. Pick a random starting square
    2. Make a list of all the possible moves from the current square
    3. If there are no moves, undo the last move and try the next choice
    from that square
    4. Otherwise, make the first move in the list
    5. Goto step 2 until the grid is full

    That's a boring brute force approach, which is the computer science term for
    "try everything until something works." When it gets stuck somewhere, it
    backtracks and tries another jump. It may, at times, need to backtrack several
    steps to get back to a place where it could try another move.

    This approach has one major plus and one major minus. First, the good news: it
    will find a solution. The bad news: eventually. Because it has to check every
    possibility, it can take a good long while to find a path that works. The
    bigger the board gets, the more places it has to check. The waits get longer
    and longer.

    Now, when solving the Knight's Tour there is a common shortcut that often leads
    to a solution much faster. Luckily it works here too. The idea is that, you
    should visit the squares with the least choices first. Those are the places you
    are likely to run out of options, so getting them out of the way while you still
    have plenty of open squares increases your chances of making it around the
    board. This is called the JC Warnsdorff heuristic, because JC Warnsdorff made
    the suggestion all the way back in 1823.

    The downside of the JC Warnsdorff heuristic is that is doesn't always work.
    Depending on your starting position and which squares you visit first, it can
    paint itself into a corner. The problem is more common on certain board sizes,
    but it does happen. The upside is, it's so darn quick (because it doesn't
    backtrack), you can do multiple searches and still be quicker than the brute
    force approach. If one attempt fails, just try again. Most solutions used this
    approach.

    I found one more corner to cut. When the quiz mentioned circular solutions, it
    made me realize you could cheat a bit, if you had one. If you can go from the
    end of the line back to the beginning (the definition of a circular solution),
    you can start anywhere on that path and follow it for the entire length to get
    all the numbers out. In truth, these are all the same solution (in my opinion),
    but the numbers move around so they look different. It's also lightning quick
    to shift all the numbers by some offset. Sadly it can be pretty slow to find a
    circular solution in the first place. It's a trade off.

    Another technique, subdividing the grid and piecing together multiple smaller
    solutions, was used be Elliot Temple. See the later postings in the quiz thread
    for a good discussion of that approach.

    OK, let's get to the code already!

    I'm going to so show my solution, just because it takes both shortcuts and I'm
    very familiar with how it works. I do not think my solution came out the
    cleanest though, so definitely go through the others to find some pretty code.
    Here's the beginning of my solution:

    #!/usr/bin/env ruby -w

    require "enumerator"

    class PenAndPaperGame
    def self.circular_solutions
    @circular ||= if File.exist?("circular_solutions.dump")
    File.open("circular_solutions.dump") { |file| Marshal.load(file) }
    else
    Array.new
    end
    end

    def initialize(size)
    @size = size
    @largest = @size * @size

    @grid = Array.new(@largest)
    end

    # ...

    I pull in enumerator here, because I'm addicted. Can't wait until that library
    is in the core.

    The class method here is my persistent memory for circular solutions. It reads
    the data file, if it exists, and creates an Array of circular solutions at
    various sizes. If we don't have the file, a new Array is used. The ||= caching
    operator is used for the assignment so we only look the value up once.

    The constructor is trivial and almost every solution had one just like it. We
    record the size, figure out what the largest number needs to be, and build the
    grid Array.

    The Array was a dumb choice on my part. It somehow made me feel more manly to
    use a one dimensional Array and deal with the two dimensional indexing.
    However, looking at David Trans super clear 45 line solution that uses normal
    nested Arrays just made me feel dumb.

    Here's the cheat solver I described earlier:

    # ...

    def solve
    if self.class.circular_solutions[@size].nil?
    solve_manually
    else
    @grid = self.class.circular_solutions[@size]
    offset = @grid[rand(@grid.size)]
    @grid.map! { |n| (n + offset) % @largest + 1 }
    to_s
    end
    end

    # ...

    If we haven't yet found a circular solution for this size, a handoff is made to
    solve_manually(). If we do have one, the else clause is a full (cheating)
    solution. We set the grid to the complete solution, choose a random value from
    the grid (similar to picking a starting square), adjust all the values in the
    grid by the chosen starting point, and print the results.

    Now that we've looked at my super cheat, let's get to a real solution:

    # ...

    def solve_manually
    x, y = rand(@size), rand(@size)
    count = mark(x, y)

    loop do
    to = jumps(x, y)
    return self.class.new(@size).solve_manually if to.empty?

    scores = rate_jumps(to)
    low = scores.min
    next_jump = to.enum_for:)each_with_index).select do |jump|
    scores[jump.last] == low
    end.sort_by { rand }.first.first

    count = mark(*(next_jump + [count]))
    x, y = next_jump

    if count > @largest
    if circular?
    self.class.circular_solutions[@size] = @grid
    File.open("circular_solutions.dump", "w") do |file|
    Marshal.dump(self.class.circular_solutions, file)
    end
    return to_s
    else
    puts "Found this solution:"
    puts to_s
    puts "Continuing search for a circular solution..."
    return self.class.new(@size).solve_manually
    end
    end
    end
    end

    # ...

    This method looks big, but hopefully it's fairly high level and thus easy enough
    to read. First, we select a random starting x and y and mark() that square.
    Then we dive into the main solution loop.

    In the loop, we pull all possible jumps() from this square and make sure we have
    at least one choice. If we don't, we got stuck and can't find a solution so we
    just build a new solver, trigger the search for another attempt, and return the
    results of that.

    If we did get some jumps, we need to score them, based on how many moves we
    would have from there. The call to rate_jumps() does this. Then we pluck out
    the low score as our target move. The complicated ball of iterators right after
    that is just a lazy way to select a random move from all the choices matching
    the lowest score, which gets slotted into next_jump.

    With a jump selected we mark the new square and move.

    Before we loop(), we check to see if that was the final mark. When it is, we
    have a solution, but we want to check if it's a circular solution we could reuse
    for cheating. If it is circular, we add it to the collection and update our
    storage file. Then we show the solution. When it's not circular, we go ahead
    and show it, but trigger another search to see if we can hunt down a circular
    solution.

    Here's the printing code:

    # ...

    def to_s
    width = @largest.to_s.size
    border = " -" + (["-" * width] * @size).join("-") + "- \n"

    border +
    @grid.enum_for:)each_slice, @size).inject(String.new) do |grid, row|
    grid + "| " + row.map { |n| n.to_s.center(width) }.join(" ") + " |\n"
    end +
    border
    end

    # ...

    Nothing too tricky here. We find a cell size and build a border. Then we print
    a border, each row, and another border. The complicated row iteration is just
    another sign that I used the wrong Array.

    Here are the missing helper methods:

    # ...

    private

    def at(x, y)
    x + y * @size
    end

    def mark(current_x, current_y, mark = 1)
    @grid[at(current_x, current_y)] = mark
    mark + 1
    end

    def jumps(from_x, from_y, grid = @grid)
    [ [-3, 0],
    [3, 0],
    [0, -3],
    [0, 3],
    [2, 2],
    [-2, 2],
    [2, -2],
    [-2, -2] ].map do |jump|
    [from_x + jump.first, from_y + jump.last]
    end.select do |jump|
    jump.all? { |to| (0...@size).include? to } and grid[at(*jump)].nil?
    end
    end

    def rate_jumps(choices)
    choices.map { |jump| jumps(*jump).size }
    end

    def circular?
    grid = @grid.dup
    grid[grid.index(@largest)] = nil

    x, y = grid.index(1).divmod(@size).reverse

    not jumps(x, y, grid).empty?
    end
    end

    # ...

    The at() method is used to turn x and y coordinates into an index for the one
    dimensional grid I am using. mark() will place a number in the indicated square
    and return the next mark that should be placed. (This was another odd choice.
    I have no idea why I didn't use an instance variable here.)

    The jumps() method uses offset to locate all possible moves from the current
    location. It then filters those by removing any out-of-bound indices and any
    squares that aren't nil. rate_jumps() is just a thin shell over jumps to count
    the moves available at each step.

    The circular?() check duplicates the solved grid, knocks the last move back to
    nil, locates the starting square, and checks to see if the starting square now
    has one jump (to the only nil square).

    Using those pieces, here's the application code:

    # ...

    if __FILE__ == $PROGRAM_NAME
    size = ARGV.first && ARGV.first =~ /\A-s(?:ize)?\Z/ ? ARGV.last.to_i : 5
    puts PenAndPaperGame.new(size).solve
    end

    That just reads the size parameter or sets the default to 5 and kicks off the
    solver process.

    A big thank you to all those who were so creative with their solutions this time
    around. You guys taught me how to finish off my own solution.

    Tomorrow we will play around with interactively defining Ruby methods...
     
    Ruby Quiz, Aug 17, 2006
    #1
    1. Advertising

  2. On Aug 17, 2006, at 8:51 AM, Ruby Quiz wrote:

    > Now, when solving the Knight's Tour there is a common shortcut that
    > often leads
    > to a solution much faster. Luckily it works here too. The idea is
    > that, you
    > should visit the squares with the least choices first. Those are
    > the places you
    > are likely to run out of options, so getting them out of the way
    > while you still
    > have plenty of open squares increases your chances of making it
    > around the
    > board. This is called the JC Warnsdorff heuristic, because JC
    > Warnsdorff made
    > the suggestion all the way back in 1823.


    So what I was calling the one-step look-ahead is properly called the
    JC Warnsdorff heuristic. I'm glad to learn that.

    > The downside of the JC Warnsdorff heuristic is that is doesn't
    > always work.
    > Depending on your starting position and which squares you visit
    > first, it can
    > paint itself into a corner. The problem is more common on certain
    > board sizes,
    > but it does happen. The upside is, it's so darn quick (because it
    > doesn't
    > backtrack), you can do multiple searches and still be quicker than
    > the brute
    > force approach. If one attempt fails, just try again. Most
    > solutions used this
    > approach.


    Re: ... because it doesn't backtrack ...

    The heuristic can be used to improve a backtracking solver. The
    interesting question is whether backtracking is ever better than
    restarting. I think there are such situations. One might write a
    solver that tries backtracking a little first and then does a restart
    as Plan B. Of course, one would have to make a precise definition of
    what "a little" means ;)

    Regards, Morton
     
    Morton Goldberg, Aug 17, 2006
    #2
    1. Advertising

  3. On Aug 17, 2006, at 9:23 AM, Morton Goldberg wrote:

    >> The downside of the JC Warnsdorff heuristic is that is doesn't
    >> always work.
    >> Depending on your starting position and which squares you visit
    >> first, it can
    >> paint itself into a corner. The problem is more common on certain
    >> board sizes,
    >> but it does happen. The upside is, it's so darn quick (because it
    >> doesn't
    >> backtrack), you can do multiple searches and still be quicker than
    >> the brute
    >> force approach. If one attempt fails, just try again. Most
    >> solutions used this
    >> approach.

    >
    > Re: ... because it doesn't backtrack ...
    >
    > The heuristic can be used to improve a backtracking solver.


    That's a good point. David Tran's solution does both.

    James Edward Gray II
     
    James Edward Gray II, Aug 17, 2006
    #3
  4. Just one last minor point. A Google search on Warnsdorff revealed
    that it's HC Warnsdorff, not JC, and that its usually referred to as
    the Warnsdorff rule, not Warnsdorff heuristic. The latter is probably
    because "rule" is a lot easier to type than "heuristic" :D

    Regards, Morton

    On Aug 17, 2006, at 2:57 PM, James Edward Gray II wrote:

    > On Aug 17, 2006, at 9:23 AM, Morton Goldberg wrote:
    >
    >>> The downside of the JC Warnsdorff heuristic is that is doesn't
    >>> always work.
    >>> Depending on your starting position and which squares you visit
    >>> first, it can
    >>> paint itself into a corner. The problem is more common on
    >>> certain board sizes,
    >>> but it does happen. The upside is, it's so darn quick (because
    >>> it doesn't
    >>> backtrack), you can do multiple searches and still be quicker
    >>> than the brute
    >>> force approach. If one attempt fails, just try again. Most
    >>> solutions used this
    >>> approach.

    >>
    >> Re: ... because it doesn't backtrack ...
    >>
    >> The heuristic can be used to improve a backtracking solver.

    >
    > That's a good point. David Tran's solution does both.
     
    Morton Goldberg, Aug 18, 2006
    #4
  5. On Aug 17, 2006, at 8:05 PM, Morton Goldberg wrote:

    > Just one last minor point. A Google search on Warnsdorff revealed
    > that it's HC Warnsdorff, not JC


    Interesting. It seems to appear both ways:

    http://www.google.com/search?q=JC Warnsdorff

    > and that its usually referred to as the Warnsdorff rule, not
    > Warnsdorff heuristic. The latter is probably because "rule" is a
    > lot easier to type than "heuristic" :D


    I imagine it's because it was stated before computer's existed to
    make heuristic a popular term. ;)

    I choose to call it a heuristic because I defined those in last
    week's summary. I thought it would be good for the regular readership.

    James Edward Gray II
     
    James Edward Gray II, Aug 18, 2006
    #5
  6. On Aug 18, 2006, at 3:51 AM, Robert Dober wrote:

    > But just to tell you it is HC.


    Thanks for looking into this. I've updated the summary.

    James Edward Gray II
     
    James Edward Gray II, Aug 18, 2006
    #6
  7. On Aug 17, 2006, at 10:23 AM, Morton Goldberg wrote:
    > One might write a solver that tries backtracking a little first and
    > then does a restart as Plan B. Of course, one would have to make a
    > precise definition of what "a little" means ;)


    I have implemented such a program, one which applies the Warnsdorff
    rule starting from a random position and which allows backtracking to
    be turned on or off. I find the results convincing -- backtracking
    does have value even when the Warnsdorff rule is used, especially
    when a cyclic solution is wanted.

    17x17 grid -- cyclic solution required -- average of 5 runs for each
    case

    no backtracking: 10.2562504 sec
    with backtracking: 1.1582514 sec

    I appologize if I'm being a bore on this subject, but I hope at least
    a few people will be interested in this result.

    Regards, Morton
     
    Morton Goldberg, Aug 18, 2006
    #7
    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:
    498
    Manuel Graune
    Apr 10, 2010
  2. Ian Collins
    Replies:
    17
    Views:
    633
    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:
    525
    Morton Goldberg
    Aug 15, 2006
  4. David Tran
    Replies:
    6
    Views:
    183
    Morton Goldberg
    Aug 17, 2006
  5. Rick DeNatale
    Replies:
    2
    Views:
    290
    Daniel Martin
    Aug 16, 2006
Loading...

Share This Page