##
##     INPUT
##       4
##     OUTPUT
##   [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
##
def tsm(n)
  sqr = n * n

  ## construct the matrix
  arr, b, c = [], [], []
  for i in 1..sqr
    c << i
    if i % n == 0
      arr << c
      c = []
    end
  end

  ## Denotes indices to read the values at
  ## Also to determine if path exists
  i, j = 0, 0

  ## Provides direction
  r, d, l, u = true, false, false, false

  while true
    break if b.length == sqr - 1
    b << arr[i][j]
    arr[i][j] = nil ## mark as read
    case true
    when r
      ## right
      if j+1 < arr[i].length && arr[i][j+1] != nil
        j += 1
      else
        ## move down
        r, d, l, u = false, true, false, false
        i += 1
      end
    when d
      ## down
      if i+1 < arr.length && arr[i+1][j] != nil
        i += 1
      else
        ## move left
        r, d, l, u = false, false, true, false
        j -= 1
      end
    when l
      ## left
      if j > 0 && arr[i][j-1] != nil
        j -= 1
      else
        ## move up
        r, d, l, u = false, false, false, true
        i -= 1
      end
    when u
      if i > 0 && arr[i-1][j] != nil
        i -= 1
      else
        ## move right
        r, d, l, u = true, false, false, false
        j += 1
      end
    end
  end
  b << arr[i][j] unless arr[i][j].nil?
  b
end