On Aug 26, 2004, at 6:15 PM, Boris Glawe wrote:

> Hi,
>
> I am implementing one and the same algorithm in different programming 
> languages, in order to compare their performance. It's a backtracking 
> algorithm, which takes over 115mio recursions to terminate, where the 
> recursion depth isn't deeper then 49.

[snip description and code]

One of the problems for me hunting through your code is that it's kind 
of lengthy.  Any chance we could simplify it down to something a little 
easier to swallow?

Playing around a little on my own, I've come up with:

#!/usr/bin/ruby -w

class KnightsTour
	def KnightsTour.square_to_indices( square )
		return (square[0] - ?a), (square[1, 1].to_i - 1)
	end
	
	def KnightsTour.indices_to_square( rank, file )
		return (?a + rank).chr + (file + 1).to_s
	end
	
	def initialize( size, square )
		@size = size

		@rank, @file = KnightsTour.square_to_indices square
	end
	
	def find( *path )
		path = [ [ @rank, @file ] ] unless path.length > 0
	
		j = jumps path[-1][0], path[-1][1]
		j.delete_if do |a|
			path.find { |b| a == b }
		end
		
		if j.length > 0 and path.length + 1 == @size * @size
			path << j[0]
			return path
		end
		
		result = nil
		
		j.each do |jump|
			to = path.dup
			to << jump
			
			result = find( *to )

			break if result
		end
		
		return result
	end
	
	private
	
	def jumps( rank, file )
		pos = [ [ rank - 1, file - 2 ], [ rank - 1, file + 2 ],
				[ rank - 2, file - 1 ], [ rank - 2, file + 1 ],
				[ rank + 1, file - 2 ], [ rank + 1, file + 2 ],
				[ rank + 2, file - 1 ], [ rank + 2, file + 1 ] ]
		pos.delete_if do |jump|
			jump[0] < 0 or jump[1] < 0 or
			jump[0] >= @size or jump[1] >= @size
		end
		return pos
	end
end

unless ARGV.length == 2 and ARGV[0] =~ /^[3-8]+$/ and ARGV[1] =~ 
/^[a-h][1-8]$/
	puts "Usage:  tour.rb BOARD_SIZE STARTING_SQUARE\n" +
		 "\tBOARD_SIZE is a digit between 1 and 8\n" +
		 "\tSTARTING_SQUARE is a square in algerbraic notation\n"
	exit
end

tour = KnightsTour.new(ARGV[0].to_i, ARGV[1]).find()
if tour
	tour.each { |e| puts KnightsTour.indices_to_square(e[0], e[1]) }
else
	puts "No tour found."
end

__END__

My version isn't identical to yours and I doubt it's much faster, if at 
all.  It is though easier to troubleshoot, for me at least.

Just a thought.  Sorry I wasn't more help.

James Edward Gray II