The computing challenge is simple to describe and hard to execute: Plot the optimal path down to the target without running out of fuel. That’s complicated enough, but also consider the time constraint: The rocket’s computers need to solve this problem before they run out of fuel or crash into earth—in a “fraction of a second,” according to Blackmore. He and his colleagues developed one of the first algorithms to do this in three dimensions in that 2009 paper on Mars landings, receiving a patent on their ideas in 2013.

(A visualization of the rocket booster’s path back to earth)

The solution involves solving a “convex optimization problem,” a common challenge in modern machine learning. In wildly reductive layman’s terms, it involves considering all the possible answers to the question of “what’s the best way to get from here to the landing pad without running out of fuel” as a geometric shape, and uses mathematical tools developed first by John von Neumann, the father of game theory, and refined by Indian mathematician Narendra Karmarkar in the 1980s, to quickly choose the best way down from that set.

(Via qz.)

It wasn't always so apparently easy and quick; here are some of SpaceX's less successful moments:

Science fiction authors have been utilizing their imagination in advance of engineering. In Redemption Cairn, by Stanley G. Weinbaum, published in Astounding Science Fiction in 1936, we read this description of trying to land a rocket on its tail:

"Those lousy reporters!” I blazed. "All of them seemed to think landing a rocket is like settling down in bed; you just cushion down on your underblast. Yeah; they don’t realize that you have to land blind, because three hundred feet from the ground the blast begins to splash against it.

I slapped her hands hard and grabbed the U-bar. I cut the underjets completely off, letting the ship fall free, then shot the full blast through the right laterals. It was damn close, I’m ready to swear, but we leveled, and I snapped on the underblast before we lost a hundred feet of altitude.

('Redemption Cairn' by Stanley G. Weinbaum)

"You watch the leveling poles at the edge of the field and try to judge your altitude from them, but you don’t see the ground ; what you see under you are the flames of Hell. And another thing they don’t realize; lowering a ship is like bringing down a dinner plate balanced on a fishing rod. If she starts to roll sideways — blooey! The underjets only hold you up when they’re pointing down, you know.”