A* (A-star) Search and 8-puzzle - what is wrong with my algorithm?

Question

I am trying to solve an 8-puzzle using A star search.

This is the structure I am using which is from a textbook:

aStartFunction():   
  initialize the frontier with the root
  
  while frontier is not empty:
    current = frontier.pop
    if current is solution then return
    add current to explored

    for each child:
      if child not in frontier and not in explored:
        add child to frontier
      else if child is in frontier with a higher f(n) cost:
        frontier = child

It runs indefinitely on complex initial states, but solves simple ones that are 1 or 2 moves away from being solved. All of the states I am using are solvable. Can you see if something's wrong by looking at this pseudocode?