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