Learn Icelandic: Hann verður að leysa erfiðustu gátuna, annars tapa þeir. - He has to solve the hardest riddle, otherwise they lose.

Because of the V2 (verb-second) rule. Annars (otherwise) acts as an adverbial conjunction that takes up the first position in the second clause. To keep the verb in the second position, the verb tapa (lose) must come right after it, pushing the subject þeir (they) into the third spot.

Doesn't verður usually mean 'becomes' or 'will be'? Why does it mean 'has to' here?

You are right that verða on its own usually means 'to become'. However, when it is paired with the particle að and an infinitive verb (like leysa), the phrase verða að changes meaning to 'must' or 'to have to'. Therefore, hann verður að leysa means 'he has to solve'.

Why does the superlative adjective erfiðustu (hardest) end in '-u'?

Because it is describing a definite noun. Gátuna has the attached definite article '-na' (the riddle). When an adjective modifies a definite noun, it must use its weak declension. For a feminine noun in the accusative case like this one, the weak superlative ending is -u.

How does the conjunction annars relate to the word annar (other)?

Annars is literally the genitive (possessive) form of annar. Over time, it froze into a fixed adverb meaning 'otherwise' or 'else'. In sentences like this, it perfectly connects two main clauses by introducing the negative consequence that will happen if the first action isn't completed.