Starting on a tile edge
This is correct.  Tiles are normally placed during the exploration phase.  I haven't found a time when they are placed any other time.

With this scenario, the first turn is, basically, "skip your hero phase", then explore, battle monsters and possibly deal with an encounter.