# This quiz reminds me about Knight Tour problem.

# So, I solve this quiz using brute-forcing combine with JC Warnsdorff

(1823) rule.

# Move to the next case where has the minimum number of exits,

# if it fail then backtracking and move to next minimum number of

exits … and so on.

(puts “#$0 n (n > 0)”; exit) unless (@n = ARGV[0].to_i) > 0

MOVES = [[3,0], [-3,0], [0,3], [0,-3], [2,2], [2,-2], [-2,2], [-2,-2]]

@board = Array.new(@n) { Array.new(@n) }

def show_solution

digits = (@n*@n).to_s.size

print(" #{’-’ * (digits+2) * @n}\n|")

print(@board.map { |l| l.map{|e| " %#{digits}d " % e}.join

}.join("|\n|"))

print("|\n #{’-’ * (digits+2) * @n}\n")

exit

end

def nb_exit(x, y)

return 0 if (x < 0 || x >= @n || y < 0 || y >= @n || @board[x][y])

MOVES.inject(0) do |m, (i, j)|

i += x; j += y

(i < 0 || i >= @n || j < 0 || j >= @n || @board[i][j]) ? m : m+1

end

end

def jump(v, x, y)

return if (x < 0 || x >= @n || y < 0 || y >= @n || @board[x][y])

@board[x][y] = v

show_solution if v == @n*@n

MOVES.sort_by { |i,j| nb_exit(x+i, y+j) }.each { |i,j| jump(v+1, x+i,

y+j) }

@board[x][y] = nil

end

@n.times { |x| @n.times { |y| jump(1, x, y) } }

puts “No solution.”

**END**

If fact, change the MOVES constant to

MOVES = [[-1,2], [1,2], [-1,-2], [1,-2], [2,-1], [2,1], [-2,-1], [-2,1]]

and ask for n = 8, than it becomes Knight Tour solver.