```My solution also uses the Warnsdorff heuristic (moving to the square
with the least amount of possible moves left).
It works very well for sizes under 100 or so, gets worse after that
and starts taking hundreds of tries at about n=175.

I also included an option to see how long tours are starting from each
square (give the script any second parameter to show this).
This shows how well (or poor) the algorithm works for that size, but
it's obviously quite slow for larger sizes as it runs the algorithm
for every square.

Code:

module Enumerable
def x(enum)  # Cartesian product
map{|a| enum.map{|b| [a,b].flatten }}.inject([]) {|a,b| a+b}
end
def **(n) #  Cartesian power
if n == 1
self
else
self.x(self**(n-1))
end
end
end

module OpenStructable
def method_missing(method,*args)
(class<<self;self;end).send(:attr_accessor, method.to_s.sub('=','') )
send(method,*args)
end
end

class Vertex < Array
include OpenStructable
def initialize(name)
self.name = name
end
end

class Graph
def initialize
@vertices = Hash.new{|h,k| h[k] = Vertex.new(k) }
end

@vertices[from] << @vertices[to]
end

def warnsdorff_tour(start)
@vertices.each_value{|v|
v.score = v.size
v.done = false
}
curr_node = @vertices[start]
tour = []
while curr_node
tour << curr_node
curr_node.done = true
curr_node.each{|v| v.score -= 1}
curr_node = curr_node.reject{|v| v.done}.sort_by{|v| v.score}.first
end
tour.map{|t| t.name}
end

end

n = (ARGV[0] || 5).to_i
graph = Graph.new

dirs = [2,-2]**2 + [[0,3],[3,0],[0,-3],[-3,0]]

valid = 0...n

(valid**2).each {|x,y|
dirs.each{|dx,dy|
to_x, to_y =  x + dx, y + dy
graph.add_edge([x,y] , [to_x,to_y]) if valid.include?(to_x) &&
valid.include?(to_y)
}
}
grid = Array.new(n){Array.new(n)}

# This shows how long a tour starting from each square is
if ARGV[1]
full_count = 0
(valid**2).each{|x,y|
grid[y][x] =  graph.warnsdorff_tour([x,y]).length
full_count += 1 if grid[y][x] == n*n
}
puts "#{full_count} / #{n*n} = #{'%.2f' %
[100*full_count.to_f/(n*n)]} % of the possible starting positions give
a full tour."
else

solution = []
try = 0
([0,n-1]**2 + [0].x(1..n-2) + (1..n-2)**2).each{|sx,sy|  # for
starting square, try corners first, then one edge, then inside
try += 1
solution = graph.warnsdorff_tour([sx,sy])
break if solution.length == n*n
}

if solution.length != n*n
puts "Failed to find tour."
exit!
end
puts "Found tour in #{try} tries."

solution.each_with_index{|(x,y),i| grid[y][x] = i+1 }
end

max_len = (n * n).to_s.length

sep = ('+' + '-' * (max_len+2) ) * n + '+'
puts sep, grid.map{|row| '| ' + row.map{|n| n.to_s.center(max_len)
}.join(' | ') + ' |' }.join("\n" + sep + "\n"), sep

```