From: Rick DeNatale <rick.denatale@...>
Date: 2006-08-15T03:23:21+09:00
Subject: Re: [QUIZ]Pen and Paper (#90)

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::Player.new(board_size)
		player.play(0,1)
		end
	end
else
	if profile
		require 'profile'
	end
	iterations.times do
		player = RubyQuiz90::Player.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[i] = Array.new(size) }
			(3..size+2).each { | i | @row[i] = Array.new(size, 0) }
			(size+3..size+5).each { | i | @row[i] = 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
-- 
Rick DeNatale

http://talklikeaduck.denhaven2.com/