Ruby script to solve Knight plight

knight.rb

#Slight modification from https://github.com/tkareine/knights_tour
#To generate solution for http://adityatj.github.io/knight/

#modified by soulchild
#original by tkareine (https://github.com/tkareine/knights_tour)

class KnightTour

  def initialize(board_size_array, start_pos_array, forbidden_block_array = [])
    @board_size = board_size_array
    @knight_starts_at = start_pos_array
    @forbidden_block = forbidden_block_array

  end 

  def solve
    @solution ||= StringResult.new(traverse(
                      Knight.new(@board_size, @knight_starts_at, @forbidden_block)))
  end

  def traverse(knight)
    unless knight.traversed?
      next_positions = knight.find_next_positions
      next_positions.each do |next_position|
        knight = traverse(knight.dup.traverse_to(next_position))
        unless knight.nil?
          return knight   # return the first solution found
        end
      end
    end

    knight  # no solutions found, or already found one
  end
end

 class StringResult
  def initialize(result)
    if result.is_a?(Knight)
      @result = board_to_s(result.board, result.steps_taken)
    else
      @result = "No solution found."
    end
  end

  def to_s
    @result
  end

  private

  def board_to_s(board, steps_taken)
    square_width = steps_taken.to_s.length + 1
    separator_str = separator(square_width, board[0].size)

    output = ""

    board.each do |row|
      output << separator_str
      row_output = row.map { |step| "%#{square_width}s" % step }.join("|")
      output << "|#{row_output}|\n"
    end

   output << separator_str
  end

  def separator(board_width, cols)
    ("+" << "-" * board_width) * cols << "+\n"
  end
end

class Knight
  ## as [x, y] pairs
  LEGAL_STEPS = [ [-2,  1], [-1,  2], [ 1,  2], [ 2,  1],[ 2, -1], [ 1, -2], [-1, -2], [-2, -1] ]
  attr_reader :board, :steps_taken, :current_position, :forbidden_block

  def initialize(board_size, start_at , forbidden_block)
    @board = Array.new(board_size[0]){ Array.new(board_size[1], 0) }
    @forbidden_block = forbidden_block

    @forbidden_block.each do |forb|
      @board[forb[0]][forb[1]] = 99
    end

    @steps_taken = 0
    traverse_to(start_at)
  end

  def initialize_copy(other)
     @board = Marshal.load(Marshal.dump(other.board))
     @forbidden_block = other.forbidden_block
     @forbidden_block.each do |forb|
      @board[forb[0]][forb[1]] = 99
    end
    @steps_taken = other.steps_taken
  end

  #finished traversing
  def traversed?
    last_step = @board.size * @board[0].size
    @steps_taken == last_step
  end

  def traverse_to(new_position)
    @steps_taken += 1
    @current_position = new_position
    @board[@current_position[0]][@current_position[1]] = @steps_taken

    #return current instance of knight
    self
  end

  def find_next_positions
    sort_by_warnsdorffs_heuristics(find_next_positions_at(@current_position))
  end

  private

  # Optimization by applying Warnsdorff's heuristics: attempt to avoid
  # dead ends by favoring positions with the lowest number of next
  # available positions (thus, isolated positions become visited first).
  #
  # References:
  #   <http://mathworld.wolfram.com/KnightsTour.html>
  #   <http://web.telia.com/~u85905224/knight/eWarnsd.htm>
  def sort_by_warnsdorffs_heuristics(positions)
    positions.sort_by do |position|
      find_next_positions_at(position).size
    end
  end

  def find_next_positions_at(position)
    positions = LEGAL_STEPS.map do |step|
      position_after_step(position, step)
    end
    positions.reject { |pos| pos.nil? || (@board[pos[0]][pos[1]] > 0) }
  end

  def position_after_step(from, step)
    x_pos = from[0] + step[0]
    y_pos = from[1] + step[1]

    if (0...@board.size).include?(x_pos) && (0...@board[0].size).include?(y_pos)
      [x_pos, y_pos]
    else
      nil
    end
  end

end

#5x5 size
boardsize = [5,5]

#start position in [y,x] format, from top left (0,0) to bottom right (4,4)
#change this to the starting position you desire
startpos = [0,1]

#forbidden blocks, no need change this
forbidblock = [ [0,0], [0,4], [4,0], [4,4] ]

kt = KnightTour.new(boardsize, startpos, forbidblock)
puts kt.solve