From: Morton Goldberg <m_goldberg@...>
Date: 2006-08-17T22:46:11+09:00
Subject: Re: [Solution] [QUIZ] Pen and Paper (#90)

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...