Determining position and finding a route. For most of history the difficult part was not direction but position, and specifically longitude, which resisted solution for two centuries and was worth a fortune to whoever solved it.
Direction is the easiest. The sun, the pole star and, from around the eleventh century in Europe and earlier in China, the magnetic compass all indicate direction. Magnetic north differs from true north by an amount varying with location and time, which must be corrected for.
Latitude is also tractable. The angle of the pole star above the horizon, or of the sun at noon with a correction for the date, gives latitude directly. Instruments for measuring that angle progressed from the kamal and quadrant through the astrolabe to the sextant.

Longitude was the hard problem. The Earth turns fifteen degrees of longitude per hour, so longitude is equivalent to the difference between local time and the time at a reference place. Local time is easy to determine from the sun. Knowing the time elsewhere, simultaneously, is the difficulty.

Before longitude could be measured, navigators used dead reckoning: from a known starting point, track heading and speed over time and calculate the position reached.
Speed was measured with a log line, a weighted board on a knotted rope paid out for a timed interval, which is why speed at sea is measured in knots.
The method works and accumulates error continuously. Currents, leeway and inaccuracies in heading and speed compound, and after weeks out of sight of land a position could be wrong by hundreds of kilometres.
The consequences were severe. In 1707 a British fleet ran onto the Isles of Scilly with the loss of around two thousand men, an accident attributed to positional error, and it prompted the British government to offer a large prize for a practical method of determining longitude.

Two approaches competed.
The lunar distance method used the moon's motion against the stars as a clock. It required precise tables, a sextant, and about four hours of calculation per fix, and it worked.
The chronometer method carried the reference time aboard. This required a clock that kept time despite a ship's motion, temperature changes and humidity, which pendulum clocks could not do.
John Harrison, a carpenter and self-taught clockmaker, spent decades on the problem, producing a series of increasingly refined instruments. His fourth, completed in 1759, was a large watch rather than a clock and performed within the prize's requirements on trial. Obtaining the money involved prolonged dispute with the Board of Longitude, whose members favoured the astronomical method.
Chronometers were expensive initially and became standard as production improved, and ships carried several as a check against one drifting.
Radio time signals from the early twentieth century removed the need to carry time, since a ship could receive it.

Radio navigation systems from the 1930s onward used the timing of signals from fixed transmitters, and successive systems extended range and accuracy.
Inertial navigation measures acceleration and rotation continuously and integrates them to track position from a known start. It requires no external signal, which is why it is used in submarines, aircraft and missiles, and it drifts over time.
Satellite navigation, treated in its own capsule, made precise positioning universally available and effectively ended the problem for most purposes.
Traditional methods are nonetheless retained. Satellite signals are weak and can be jammed or spoofed, which has occurred in several regions, and maritime and aviation training continues to include celestial and dead reckoning methods for exactly that reason.
Navigation determined which voyages were possible, and the longitude problem constrained maritime trade and exploration for two centuries after the technology to cross oceans existed.
It is also a clear case of a scientific problem solved by an instrument rather than by a theory. The astronomy was well understood; what was missing was a clock that worked at sea, and the solution came from a craftsman rather than from the astronomers who expected to provide it.