[Solution] [QUIZ] Pen and Paper (#90)

Discussion in 'Ruby' started by David Tran, Aug 15, 2006.

  1. David Tran

    David Tran Guest

    #
    # This quiz reminds me about Knight Tour problem.
    # So, I solve this quiz using brute-forcing combine with JC Warnsdorff
    (1823) rule.
    # Move to the next case where has the minimum number of exits,
    # if it fail then backtracking and move to next minimum number of
    exits ... and so on.
    #

    (puts "#$0 n (n > 0)"; exit) unless (@n = ARGV[0].to_i) > 0
    MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]
    @board = Array.new(@n) { Array.new(@n) }

    def show_solution
    digits = (@n*@n).to_s.size
    print(" #{'-' * (digits+2) * @n}\n|")
    print(@board.map { |l| l.map{|e| " %#{digits}d " % e}.join }.join("|\n|"))
    print("|\n #{'-' * (digits+2) * @n}\n")
    exit
    end

    def nb_exit(x, y)
    return 0 if (x < 0 || x >= @n || y < 0 || y >= @n || @board[x][y])
    MOVES.inject(0) do |m, (i, j)|
    i += x; j += y
    (i < 0 || i >= @n || j < 0 || j >= @n || @board[j]) ? m : m+1
    end
    end

    def jump(v, x, y)
    return if (x < 0 || x >= @n || y < 0 || y >= @n || @board[x][y])
    @board[x][y] = v
    show_solution if v == @n*@n
    MOVES.sort_by { |i,j| nb_exit(x+i, y+j) }.each { |i,j| jump(v+1, x+i, y+j) }
    @board[x][y] = nil
    end

    @n.times { |x| @n.times { |y| jump(1, x, y) } }
    puts "No solution."


    __END__

    If fact, change the MOVES constant to
    MOVES = [[-1,2], [1,2], [-1,-2], [1,-2], [2,-1], [2,1], [-2,-1], [-2,1]]
    and ask for n = 8, than it becomes Knight Tour solver.
     
    David Tran, Aug 15, 2006
    #1
    1. Advertising

  2. David Tran

    David Tran Guest

    # Same logic as my first solution, simply make it more OO and clean up a bit.


    class PenAndPaperGame
    MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]

    def initialize(size)
    @size = size
    @largest = @size * @size
    @board = Array.new(@size) { Array.new(@size) }
    end

    def to_s
    return "No solution." unless @board[0][0]
    digits = @largest.to_s.size
    " #{'-' * (digits+2) * @size}\n|" +
    (@board.map { |l| l.map{|e| " %#{digits}d " % e}.join }.join("|\n|")) +
    "|\n #{'-' * (digits+2) * @size}\n"
    end

    def solve
    @size.times { |x| @size.times { |y| return self if jump(1, x, y) } }
    self
    end

    private

    def valid(x, y)
    x >= 0 && x < @size && y >= 0 && y < @size && !@board[x][y]
    end

    def nb_exit(x, y)
    MOVES.inject(0) { |m, (i, j)| valid(x+i, y+j) ? m+1 : m }
    end

    def jump(nb, x, y)
    @board[x][y] = nb
    return true if nb == @largest
    MOVES.map { |i,j| [x+i, y+j] }.select { |i,j| valid(i,j) }.
    sort_by { |i,j| nb_exit(i,j) }.each { |i,j| return true if
    jump(nb+1, i, j) }
    @board[x][y] = nil
    end
    end

    if __FILE__ == $0
    size = (ARGV[0] || 5).to_i
    puts PenAndPaperGame.new(size).solve
    end
     
    David Tran, Aug 15, 2006
    #2
    1. Advertising

  3. On Aug 15, 2006, at 4:00 PM, David Tran wrote:

    > # Same logic as my first solution, simply make it more OO and clean
    > up a bit.


    This is a clean and easy to follow solution. I really like it.

    Oddly, it has some super weird behavior on my box. It will do any
    size grid less than or equal to 17 in the blink of my eye. When I
    pass 18 or higher it seems to hang forever. It's not eating memory,
    but it does max out a CPU. It's very odd.

    James Edward Gray II
     
    James Edward Gray II, Aug 16, 2006
    #3
  4. David Tran

    David Tran Guest

    This one will "possible" find solution for "cycle pattern".
    It simply uses JC Warnsdorff (1823) rule,
    so, it may not always find solution.

    After my test, it does find cycle solutin for n = 5, 6, 15, 16, 22, 24, 25 ....
    (Of couse, I could try add brute-forcing, but don't have time to play
    with it now... )


    class PenAndPaperGame2
    MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]
    attr_reader :found

    def initialize(size)
    @size = size
    @board = Array.new(@size) { Array.new(@size) }
    @found = false
    end

    def to_s
    return "No soultion" unless @found
    digits = (@size * @size).to_s.size
    " #{'-' * (digits+2) * @size}\n|" +
    (@board.map { |l| l.map{|e| " %#{digits}d " % e}.join }.join("|\n|")) +
    "|\n #{'-' * (digits+2) * @size}\n"
    end

    def solve
    half = (@size - 1) / 2 + 1
    half.times do |x|
    half.times do |y|
    @head = 1
    @tail = @size * @size
    cc = head(nil, @head, x, y)
    if cc
    tail(cc, @tail, *next_pos(x, y))
    end
    return self if @found
    end
    end
    self
    end

    private

    def valid?(x, y)
    x >= 0 && x < @size && y >= 0 && y < @size && !@board[x][y]
    end

    def nb_exit(x, y)
    MOVES.inject(0) { |m, (i, j)| valid?(x+i, y+j) ? m+1 : m }
    end

    def next_pos(x, y)
    MOVES.map { |i,j| [x+i, y+j] }.
    select { |i,j| valid?(i, j) }.
    sort_by { |i,j| nb_exit(i, j)} [0]
    end

    def head(tail, nb, x, y=nil)
    @head = nb
    @found = true if @head >= @tail
    return if @found || !x
    @board[x][y] = nb
    tail = callcc { |cc|
    return cc if !tail
    tail.call cc
    }
    head(tail, nb+1, *next_pos(x, y))
    end

    def tail(head, nb, x, y=nil)
    @tail = nb
    @found = true if @head >= @tail
    return if @found || !x
    @board[x][y] = nb
    head = callcc { |cc|
    head.call cc
    }
    tail(head, nb-1, *next_pos(x, y))
    end

    end

    if __FILE__ == $0
    size = (ARGV[0] || 5).to_i
    puts PenAndPaperGame2.new(size).solve
    end
     
    David Tran, Aug 16, 2006
    #4
  5. On Aug 16, 2006, at 9:49 AM, James Edward Gray II wrote:

    > Oddly, it has some super weird behavior on my box. It will do any
    > size grid less than or equal to 17 in the blink of my eye. When I
    > pass 18 or higher it seems to hang forever. It's not eating
    > memory, but it does max out a CPU. It's very odd.
    >
    > James Edward Gray II


    I think it might be because the garbage collector is working extra
    hard. I have observed similar behavior with an improved version of my
    Pen and Paper program. Whereas the original version was brought down
    on its knees by a 7x7 grid, the new one can do a 9x9 in 0.1 sec or an
    11x11 in about 10 sec, but strangely had not completed a 10x10 when I
    killed it after running for 20 minutes. I have determined, in the
    10x10 case, that my algorithm produces a huge amount of garbage and
    that the GC is running constantly.

    The improvement in my program comes from incorporating Darren Kirby's
    look-ahead technique into the search algorithm. As he asserted, it
    really speeds things up. I'm at a loss as to why Kirby's technique
    doesn't work on a 10x10 grid. It has something to do with my
    requirement for a cyclic solution -- if I remove this requirement,
    the program finds a 10x10 solution in 0.1 sec, a 20x20 in 0.2 sec, a
    39x30 in 0.4 sec, and a 50x50 in 0.6 sec (close to O(n log n) behavior).

    Regards, Morton
     
    Morton Goldberg, Aug 17, 2006
    #5
  6. David Tran

    darren kirby Guest

    --nextPart1908664.2ia3vaFNi1
    Content-Type: text/plain;
    charset="iso-8859-1"
    Content-Transfer-Encoding: quoted-printable
    Content-Disposition: inline

    quoth the Morton Goldberg:

    > The improvement in my program comes from incorporating Darren Kirby's
    > look-ahead technique into the search algorithm. As he asserted, it
    > really speeds things up.=20


    In the interest of full-disclosure I want to point out is is certainly not =
    my=20
    technique, I got the idea (but not the implementation) from the earlier=20
    posted solutions...
    =20
    > I'm at a loss as to why Kirby's technique=20
    > doesn't work on a 10x10 grid. It has something to do with my
    > requirement for a cyclic solution -- if I remove this requirement,
    > the program finds a 10x10 solution in 0.1 sec, a 20x20 in 0.2 sec, a
    > 39x30 in 0.4 sec, and a 50x50 in 0.6 sec (close to O(n log n) behavior).


    Can you post your second solution? I would love to see it...

    > Regards, Morton


    =2Dd
    =2D-=20
    darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
    "...the number of UNIX installations has grown to 10, with more expected..."
    =2D Dennis Ritchie and Ken Thompson, June 1972

    --nextPart1908664.2ia3vaFNi1
    Content-Type: application/pgp-signature

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.4 (GNU/Linux)

    iD8DBQBE5C3rwPD5Cr/3CJgRAmflAJ0VF/7pL75rp3U60Nm0/PFFNshIgQCfeOO7
    URUNLoBkBASy7EQBSr+KEzg=
    =99mJ
    -----END PGP SIGNATURE-----

    --nextPart1908664.2ia3vaFNi1--
     
    darren kirby, Aug 17, 2006
    #6
  7. OK, here is my reworked solver. It's much faster than my first
    submission, but can still be slow for some grid sizes. It takes a -c
    flag to indicate a cyclic solution is required. Using -c will slow
    things down quite a bit more.

    Strangely, a 10x10 acyclic solution is arrived at faster than a 6x6
    one. Grids that are a multiple of 5x5 seem to be solved especially fast.

    <code>
    #! /usr/bin/ruby -w
    # Author: Morton Goldberg
    #
    # Date: August 17, 2006
    #
    # Ruby Quiz #90 -- Pen and Paper Game

    # A grid is a matrix of cells.
    class Grid

    def initialize(dims)
    @rows, @cols = dims
    @size = @rows * @cols
    @grid = Array.new(@rows) {|i| Array.new(@cols) {|j| Cell.new
    (i, j)}}
    end

    # Return a deep copy.
    def copy
    result = Grid.new(dimensions)
    result.grid.each_with_index do |row, i|
    row.each_with_index {|cell, j| cell.val = self[i, j].val}
    end
    result
    end

    # Shifts the values of the cells in the grid by <offset> under the
    # constraint that values are folded into the range 1..@size.
    def shift!(offset)
    @grid.each do |row|
    row.each do |cell|
    val = (cell.val + offset) % @size
    cell.val = (val == 0 ? @size : val)
    end
    end
    self
    end

    # Return the dimensions of the grid.
    def dimensions
    [@rows, @cols]
    end

    # Return the cell at positon [row, col].
    # Call as <grid-name>[row, col]
    def [](*args)
    row, col = args
    @grid[row][col]
    end

    # Assigns a cell to the positon [row, col].
    # Call as <grid-name>[row, col] = cell
    def []=(*args)
    row, col, cell = args
    @grid[row][col] = cell
    end

    # Format the grid as a bordered table.
    def to_s
    span = ('%d' % @size).size
    rule = '-' * ((span + 1) * @cols + 3) + "\n"
    grid_str = ""
    @grid.each do |row|
    grid_str << row.inject("| ") do |row_str, cell|
    row_str << ("%#{span}d " % cell.val)
    end
    grid_str << "|\n"
    end
    "" << rule << grid_str << rule
    end

    attr_reader :rows, :cols, :size, :grid

    end

    # A cell is a simple object that knows its value and its position in
    # a grid. It also encodes the game's movement rule.
    class Cell

    def initialize(row, col, val=0)
    @row, @col = row, col
    @val = val
    end

    # Return a list of targets -- an array containing all the
    unmarked cells
    # in the grid reachable from this cell in one step.
    def targets(grid)
    size = grid.rows
    result = []
    result << grid[@row, @col - 3] if @col - 3 >= 0 # north
    result << grid[@row + 2, @col - 2] \
    if @row + 2 < size && @col - 2 >= 0 # northeast
    result << grid[@row + 3, @col] if @row + 3 < size # east
    result << grid[@row + 2, @col + 2] \
    if @row + 2 < size && @col + 2 < size # southeast
    result << grid[@row, @col + 3] if @col + 3 < size # south
    result << grid[@row - 2, @col + 2] \
    if @row - 2 >= 0 && @col + 2 < size # southwest
    result << grid[@row - 3, @col] if @row - 3 >= 0 # west
    result << grid[@row - 2, @col - 2] \
    if @row - 2 >= 0 && @col - 2 >= 0 # northwest
    result.select {|c| c.val == 0}
    end

    attr_accessor :row, :col, :val

    end

    # A solver uses a depth-first search to find one, possibly cyclic,
    solution
    # for a square grid of a given size.
    class Solver

    def initialize(size)
    @size = size
    @grid = Grid.new([@size, @size])
    cell = @grid[0, 0]
    cell.val = 1
    targets = cell.targets(grid)
    goals = targets.dup # solution must finish with one of these
    cells
    @backtrack_chain = [[cell, targets, goals]]
    end

    # Return a new link for the backtrack chain if it can be extended;
    # otherwise, return nil. The <targets> array provides the one-step
    # look-ahead. The <goals> array is used to ensure the solution is
    # cyclic.
    def next_link
    cell, targets, goals = @backtrack_chain.last
    return nil if targets.empty? || ($cyclic && goals.empty?)
    next_cell = targets.shift
    next_cell.val = cell.val + 1
    next_targets = next_cell.targets(@grid)
    next_targets = next_targets.sort_by {|c| c.targets(@grid).size}
    next_goals = goals.dup
    next_goals.delete_if {|c| c == next_cell}
    [next_cell, next_targets, next_goals]
    end

    # The algorithm is a depth-first search with one-step look-ahead.
    def solve
    final_value = @size * @size
    loop do
    link = next_link
    if link then
    @backtrack_chain.push(link)
    else
    link = @backtrack_chain.pop
    if @backtrack_chain.empty? then
    puts link
    raise(RuntimeError,
    "No solution for #@size x #@size grid")
    end
    cell = link[0]
    break if cell.val == final_value
    cell.val = 0
    end
    end
    @grid
    end

    attr_reader :grid

    end

    USAGE = <<txt
    Usage: quiz_90.rb [-c] <size>
    \twhere -c indicates cyclic solution required
    \twhere <size> > 4
    txt

    def bad_arg
    puts USAGE
    exit
    end

    # Print current grid before exiting on control-C.
    Signal.trap('INT') do
    puts
    puts $solver.grid
    exit
    end

    $n = 0
    $cyclic = false
    ARGV.each do |arg|
    case arg
    when /-c/ then $cyclic = true
    when /\d+/ then $n = arg.to_i
    else bad_arg
    end
    end
    bad_arg if $n < 5
    $solver = Solver.new($n)
    puts $solver.solve
    </code>

    Regards, Morton

    On Aug 17, 2006, at 4:51 AM, darren kirby wrote:

    > quoth the Morton Goldberg:
    >
    >> The improvement in my program comes from incorporating Darren Kirby's
    >> look-ahead technique into the search algorithm. As he asserted, it
    >> really speeds things up.

    >
    > In the interest of full-disclosure I want to point out is is
    > certainly not my
    > technique, I got the idea (but not the implementation) from the
    > earlier
    > posted solutions...
    >
    >> I'm at a loss as to why Kirby's technique
    >> doesn't work on a 10x10 grid. It has something to do with my
    >> requirement for a cyclic solution -- if I remove this requirement,
    >> the program finds a 10x10 solution in 0.1 sec, a 20x20 in 0.2 sec, a
    >> 39x30 in 0.4 sec, and a 50x50 in 0.6 sec (close to O(n log n)
    >> behavior).

    >
    > Can you post your second solution? I would love to see it...
     
    Morton Goldberg, Aug 17, 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:
    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:
    517
    Morton Goldberg
    Aug 15, 2006
  4. Rick DeNatale
    Replies:
    2
    Views:
    281
    Daniel Martin
    Aug 16, 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