Solution: Knight's Tour

# Board (5 x 5), Start:[1, 0] No solution
@start_pos = [0, 0]
@chessboard = [5, 5]
@steps = 1
@squares = {}
@moves_log = []
@knight_moves  = [ 
                  [-2, -1], [-1, -2], [1, -2], [2, -1], 
                  [2, 1], [1, 2], [-1, 2], [-2, 1]
                ]
def print_chessboard( current_pos)
  puts "\nBoard (#{@chessboard[0]} x #{@chessboard[1]}), Start:[#{@start_pos[0]}, #{@start_pos[1]}]: Done in #{@steps} steps\n\n"
  @chessboard[0].times do |row|
    puts " #{@squares[row].join(" | ")}"
    puts "---- " * @squares[row].size
  end
end
def mark_as_visited(knight_pos, step)
  @squares[knight_pos[0]][knight_pos[1]] = step.to_s.rjust(2, " ")
  @moves_log << "Moving to: #{knight_pos}"
end
def mark_as_unvisited(knight_pos)
  @squares[knight_pos[0]][knight_pos[1]] = "."
  @moves_log << "Backtracking: #{knight_pos}"
end
def visited_every_square?  
  flattened_squares = @squares.values.flatten
  flattened_squares.all?{ |x| x.strip != '.' }
end
def tour(knight_pos, step = 1)
  if ( @steps == 1) 
    @chessboard[0].times do |row|
      @squares[row] = @chessboard[1].times.collect{|x| '.'}
    end
  end
    
  mark_as_visited(knight_pos, step) 
  
  if visited_every_square?    # end cause
    print_chessboard(knight_pos)
    exit
  end
  
  # checking constraints
  possible_moves = @knight_moves.select { |m|
    next_pos = [ knight_pos[0] + m[0],  knight_pos[1] + m[1] ]
    next_pos[0] >= 0 &&
    next_pos[1] >= 0 &&
    next_pos[0] < @chessboard[0] &&
    next_pos[1] < @chessboard[1] && 
    @squares[next_pos[0]][next_pos[1]] == "."
  }
  
  # trying all possible moves
  possible_moves.each do |next_move|      
    next_pos = [ knight_pos[0] + next_move[0],  knight_pos[1] + next_move[1] ] 
    @steps += 1
    tour(next_pos, step + 1)    # recursive call
    mark_as_unvisited(next_pos)   # back tracking the visited squares
  end
  return   # no more solutions
end
tour(@start_pos)
# only executes when no solution can be found
puts "No solution found showing log:"
puts @moves_log