R
Rick DeNatale
Here's my solution for the nonce <G>.
I've probably been focusing more on packaging this and less on
optimizing it than I should.
The approach is a recursive search.
0. Place the first number
1. Pick the best available direction and place the next number there.
2. Try to place the rest of the numbers (by recursive call to step 2)
3. If 2 fails , remove the number placed in step 1, pick the next
direction and try again.
4. If we run out of directions, report failure to the calling recursion.
Picking the best available direction is based on Eliott's suggested
heuristic of trying to use squares which have less available next
steps first.
I did this in two files. pen_and_paper.rb is the main program, it
does parameter parsing, and can benchmark or profile the code as
dictated by the parameters. Right now, it only searches for a
solution starting in row 0, column 1. This should be a parameter and
I should also try alternatives if the starting position doesn't work.
The second file ruby_quiz_90.rb is a module containing the classes
Board, Player and Move.
Most of the time actually still seems to be spent in checking whether
a square is occupied or not. My initial stab at this did bounds
checking since ruby Arrays just return nil for out of bounds indices.
The current iteration uses 0 instead of nil in empty cells and uses
guard rows above and below the board in order to avoid bounds
checking. I might next try eliminating the guard rows and just define
[] for NilClass to return nil.
Anyway, here's what I've got now
=== pen_and_paper.rb ===
require 'benchmark'
include Benchmark
require 'optparse'
require 'ruby_quiz_90'
board_size = 5
benchmark = false
profile = false
iterations = 1
opts = OptionParser.new
opts.on('-sBOARDSIZE',
'-s BOARDSIZE',
'--size=BOARDSIZE',
'--size BOARDSIZE',
'Height and width of board, default is 5x5',
Integer) {|val| board_size = val }
opts.on('--bench',
'Specifies that a benchmark will be done.'
) { | val | benchmark = true }
opts.on('--profile',
'Profile execution') { profile = true}
opts.on('--iterations=COUNT',
'--iterations COUNT',
'COUNT specifies the number of iterations',
'for benchmarking or profiling',
Integer) { | val | iterations = val }
opts.on('--help',
'produce this help text') { puts opts.to_s
exit }
begin
opts.parse(ARGV)
rescue
puts opts.to_s
exit
end
puts "board_size is #{board_size}x#{board_size}"
puts "benchmark=#{benchmark}, profile=#{profile}, iterations=#{iterations}"
player = nil
if benchmark
bm(iterations) do | test |
test.report("#{board_size}x#{board_size}:") do
player = RubyQuiz90:
layer.new(board_size)
player.play(0,1)
end
end
else
if profile
require 'profile'
end
iterations.times do
player = RubyQuiz90:layer.new(board_size)
player.play(0,1)
end
end
puts player.board
=== ruby_quiz_90.rb ===
module RubyQuiz90
class Board
# Changes:
# pad row with 3 guard rows above and below
# this allows available? to avoid having to catch
# nil not understanding []
def initialize(size)
@row = Array.new(size+6)
(0..2).each { | i | @row = Array.new(size) }
(3..size+2).each { | i | @row = Array.new(size, 0) }
(size+3..size+5).each { | i | @row = Array.new(size) }
@size = size
# @range = (0..size-1)
end
def take(row, col, value)
@row[row+3][col] = value
end
def available?(row, col)
@row[row+3][col] == 0 rescue false
end
def take_back(row, col)
@row[row+3][col] = 0
end
def value(row, col)
@row[row+3][col]
end
def to_s
elem_width = ((@size * @size).to_s.length) + 1
header = '+-' + ('-' *(@size * elem_width)) + '+'
result = header.dup
(0...@size).each do | i |
row = @row[i+3]
result << "\n|"
row.each do | elem |
result << ((elem == 0) ?
(" " * elem_width) :
sprintf("%#{elem_width}d", elem))
end
result << ' |'
end
result << "\n"
result << header
end
def self.testboard(s)
b = new(s)
(0..s-1).each do | r |
(0..s-1).each do | c |
b.take(r, c, c + 1 + (r*s))
end
end
b
end
end
class Player
Direction_vectors = [
[0, 3], #move east
[2, 2], #move southeast
[3, 0], #move south
[2, -2], #move southwest
[0, -3], #move west
[-2, -2], #move northwest
[-3, -3], #move north
[-2, 2], #move northeast
]
# No_more_moves = Direction_vectors.length
#
# Last_move = (No_more_moves) - 1
def initialize(size, debug = 2)
@board = RubyQuiz90::Board.new(size)
@last = size * size
@debug = debug
end
def play (start_row=nil, start_col=nil)
row = start_row || rand(@board.size)
col = start_col || rand(@board.size)
@board.take(row, col, 1)
fill_all_from(start_row, start_col)
end
def board
@board
end
# Fill the board after the last number was placed at r,c
# If the board can be filled return true
# If the board cannot be filled restore the board to its
# initial state at the time of this call and return false
def fill_all_from(r, c)
value = @board.value(r,c) + 1
puts "Trying to fill board starting with #{value}, from #{r},
#{c}}" if @debug > 2
puts @board if @debug >= 3
return true if value > @last # our work is done!
#now try to fill the next value
optimized_moves(r, c).each do | move |
row = move.row
col = move.col
puts "Trying to move placing #{value} at #{row}, #{col}" if @debug > 2
@board.take(row, col, value)
puts "Placed #{value} at #{row}, #{col}" if @debug > 2
if fill_all_from(row, col)
return true
else
@board.take_back(row, col)
end
end
# if we get here, it's time to back out
puts "All trials failed at #{value}" if @debug > 2
puts @board if @debug > 2
return false
end
# return a list of moves from row, col optimized so that
# squares with more possible further moves come first
def optimized_moves(row, col)
moves = []
Direction_vectors.each do | dx, dy |
r = row + dy
c = col + dx
if @board.available?(r,c)
moves << Move.new(r, c, availability_count(r, c))
end
end
moves.sort!
moves
end
# return the number of available squares from row, col
def availability_count(row, col)
Direction_vectors.inject(0) do | sum, (dx, dy)|
@board.available?(row+dy, col+dx) ? sum + 1 : sum
end
end
end
class Move
attr_accessor :row, :col, :count
def initialize(r, c, count)
@row = r
@col = c
@Count = count
end
# a move is greater (should come later) if it has a lower
# available move count than another
def <=>(move)
count - move.count
end
def to_s
"Count=#{@count}, row=#{@row}, col=#{@col}"
end
end
end
I've probably been focusing more on packaging this and less on
optimizing it than I should.
The approach is a recursive search.
0. Place the first number
1. Pick the best available direction and place the next number there.
2. Try to place the rest of the numbers (by recursive call to step 2)
3. If 2 fails , remove the number placed in step 1, pick the next
direction and try again.
4. If we run out of directions, report failure to the calling recursion.
Picking the best available direction is based on Eliott's suggested
heuristic of trying to use squares which have less available next
steps first.
I did this in two files. pen_and_paper.rb is the main program, it
does parameter parsing, and can benchmark or profile the code as
dictated by the parameters. Right now, it only searches for a
solution starting in row 0, column 1. This should be a parameter and
I should also try alternatives if the starting position doesn't work.
The second file ruby_quiz_90.rb is a module containing the classes
Board, Player and Move.
Most of the time actually still seems to be spent in checking whether
a square is occupied or not. My initial stab at this did bounds
checking since ruby Arrays just return nil for out of bounds indices.
The current iteration uses 0 instead of nil in empty cells and uses
guard rows above and below the board in order to avoid bounds
checking. I might next try eliminating the guard rows and just define
[] for NilClass to return nil.
Anyway, here's what I've got now
=== pen_and_paper.rb ===
require 'benchmark'
include Benchmark
require 'optparse'
require 'ruby_quiz_90'
board_size = 5
benchmark = false
profile = false
iterations = 1
opts = OptionParser.new
opts.on('-sBOARDSIZE',
'-s BOARDSIZE',
'--size=BOARDSIZE',
'--size BOARDSIZE',
'Height and width of board, default is 5x5',
Integer) {|val| board_size = val }
opts.on('--bench',
'Specifies that a benchmark will be done.'
) { | val | benchmark = true }
opts.on('--profile',
'Profile execution') { profile = true}
opts.on('--iterations=COUNT',
'--iterations COUNT',
'COUNT specifies the number of iterations',
'for benchmarking or profiling',
Integer) { | val | iterations = val }
opts.on('--help',
'produce this help text') { puts opts.to_s
exit }
begin
opts.parse(ARGV)
rescue
puts opts.to_s
exit
end
puts "board_size is #{board_size}x#{board_size}"
puts "benchmark=#{benchmark}, profile=#{profile}, iterations=#{iterations}"
player = nil
if benchmark
bm(iterations) do | test |
test.report("#{board_size}x#{board_size}:") do
player = RubyQuiz90:
layer.new(board_size)player.play(0,1)
end
end
else
if profile
require 'profile'
end
iterations.times do
player = RubyQuiz90:
layer.new(board_size)player.play(0,1)
end
end
puts player.board
=== ruby_quiz_90.rb ===
module RubyQuiz90
class Board
# Changes:
# pad row with 3 guard rows above and below
# this allows available? to avoid having to catch
# nil not understanding []
def initialize(size)
@row = Array.new(size+6)
(0..2).each { | i | @row = Array.new(size) }
(3..size+2).each { | i | @row = Array.new(size, 0) }
(size+3..size+5).each { | i | @row = Array.new(size) }
@size = size
# @range = (0..size-1)
end
def take(row, col, value)
@row[row+3][col] = value
end
def available?(row, col)
@row[row+3][col] == 0 rescue false
end
def take_back(row, col)
@row[row+3][col] = 0
end
def value(row, col)
@row[row+3][col]
end
def to_s
elem_width = ((@size * @size).to_s.length) + 1
header = '+-' + ('-' *(@size * elem_width)) + '+'
result = header.dup
(0...@size).each do | i |
row = @row[i+3]
result << "\n|"
row.each do | elem |
result << ((elem == 0) ?
(" " * elem_width) :
sprintf("%#{elem_width}d", elem))
end
result << ' |'
end
result << "\n"
result << header
end
def self.testboard(s)
b = new(s)
(0..s-1).each do | r |
(0..s-1).each do | c |
b.take(r, c, c + 1 + (r*s))
end
end
b
end
end
class Player
Direction_vectors = [
[0, 3], #move east
[2, 2], #move southeast
[3, 0], #move south
[2, -2], #move southwest
[0, -3], #move west
[-2, -2], #move northwest
[-3, -3], #move north
[-2, 2], #move northeast
]
# No_more_moves = Direction_vectors.length
#
# Last_move = (No_more_moves) - 1
def initialize(size, debug = 2)
@board = RubyQuiz90::Board.new(size)
@last = size * size
@debug = debug
end
def play (start_row=nil, start_col=nil)
row = start_row || rand(@board.size)
col = start_col || rand(@board.size)
@board.take(row, col, 1)
fill_all_from(start_row, start_col)
end
def board
@board
end
# Fill the board after the last number was placed at r,c
# If the board can be filled return true
# If the board cannot be filled restore the board to its
# initial state at the time of this call and return false
def fill_all_from(r, c)
value = @board.value(r,c) + 1
puts "Trying to fill board starting with #{value}, from #{r},
#{c}}" if @debug > 2
puts @board if @debug >= 3
return true if value > @last # our work is done!
#now try to fill the next value
optimized_moves(r, c).each do | move |
row = move.row
col = move.col
puts "Trying to move placing #{value} at #{row}, #{col}" if @debug > 2
@board.take(row, col, value)
puts "Placed #{value} at #{row}, #{col}" if @debug > 2
if fill_all_from(row, col)
return true
else
@board.take_back(row, col)
end
end
# if we get here, it's time to back out
puts "All trials failed at #{value}" if @debug > 2
puts @board if @debug > 2
return false
end
# return a list of moves from row, col optimized so that
# squares with more possible further moves come first
def optimized_moves(row, col)
moves = []
Direction_vectors.each do | dx, dy |
r = row + dy
c = col + dx
if @board.available?(r,c)
moves << Move.new(r, c, availability_count(r, c))
end
end
moves.sort!
moves
end
# return the number of available squares from row, col
def availability_count(row, col)
Direction_vectors.inject(0) do | sum, (dx, dy)|
@board.available?(row+dy, col+dx) ? sum + 1 : sum
end
end
end
class Move
attr_accessor :row, :col, :count
def initialize(r, c, count)
@row = r
@col = c
@Count = count
end
# a move is greater (should come later) if it has a lower
# available move count than another
def <=>(move)
count - move.count
end
def to_s
"Count=#{@count}, row=#{@row}, col=#{@col}"
end
end
end