From: David Tran <email55555@...>
Date: 2006-08-16T04:49:17+09:00
Subject: [Solution] [QUIZ] Pen and Paper (#90)

#
# 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.