The knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once.

knight.rb

class Game
  attr_accessor :board

  def initialize(size)
    @size = size
    @board = Array.new(size)
  end

  def start(start_row, start_column)
    first_move = Move.new(start_row, start_column, 0, @board)
    moves = [first_move]
    @board[first_move.position] = first_move

    while moves.size < @size
      # continue with last move
      move = moves.last
      next_move = move.get_moves_from_here.sort.first
      if next_move.nil?
        # there's no more from this position, so we need to reverse to last move ...
        pop_move = moves.pop
        last_move = moves.last
        # ... and remember not to repeat this move
        last_move.excluded_moves << pop_move.to_s  
        @board[pop_move.position] = nil 
      else   
        # there's a move from here, so let's continue
        moves << next_move
        @board[next_move.position] = next_move  
      end
    end
    @board
  end
end

class Move
  attr_accessor :parent, :row, :column, :sequence, :board, :excluded_moves

  def position
    @row + @column * 8
  end
  
  def <=>(other)
    self.get_moves_from_here.size < other.get_moves_from_here.size ? -1 : 1
  end

  def initialize(row, column, sequence, board)
    @row = row
    @column = column
    @sequence = sequence
    @board = board
    @excluded_moves = Array.new
  end

  def get_moves_from_here
    moves = Array.new 
    add_valid_move(@row - 2, @column - 1, moves)
    add_valid_move(@row - 2, @column + 1, moves) 
    add_valid_move(@row - 1, @column - 2, moves)
    add_valid_move(@row - 1, @column + 2, moves)
    add_valid_move(@row + 2, @column - 1, moves)
    add_valid_move(@row + 2, @column + 1, moves) 
    add_valid_move(@row + 1, @column - 2, moves)
    add_valid_move(@row + 1, @column + 2, moves)
    moves 
  end
  
  def add_valid_move(row, column, moves)
    move = Move.new(row, column, @sequence + 1, @board)
    if move.valid? and @board[move.position].nil? and @excluded_moves.index(move.to_s).nil?
      move.parent = self
      moves << move
    end
  end

  def valid?
    @row >= 0 and @row < 8 and @column >= 0 and @column < 8
  end

  def to_s
    @row.to_s + "." + @column.to_s
  end
end

def print_board(board)
  SIZE.times do |i|
    print "\n  |----|----|----|----|----|----|----|----|\n" + ROWS[(i/SIDE_LENGTH)] + " |" if i % SIDE_LENGTH == 0 
    print (board[i].nil? ? "" : board[i].sequence.to_s).ljust(4) + "|"
  end
  print "\n  |----|----|----|----|----|----|----|----|\n   "
  SIDE_LENGTH.times do |i|
    print COLUMNS[i].ljust(5)
  end
end

SIDE_LENGTH = 8
SIZE = SIDE_LENGTH * SIDE_LENGTH
ROWS = ["8", "7", "6", "5", "4", "3", "2", "1"]
COLUMNS = ["A", "B", "C", "D", "E", "F", "G", "H"]

SIDE_LENGTH.times do |r|
  SIDE_LENGTH.times do |c|    
    game = Game.new(SIZE)
    board = game.start(r, c)
    puts "\n\nrow: " + r.to_s + " column: " + c.to_s 
    print_board(board) 
  end
end

http://en.wikipedia.org/wiki/Knight's_tour