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.