Along with swords-and-sorcery, sword-and-planet stories exerted an immense influence over the imaginations of many early game writers. This second genre is most famously exemplified by the Barsoom stories of Edgar Rice Burroughs, but also includes the works of authors as diverse as Edmond Hamilton, Otis Adalbert Kline (who was Robert E. Howard's literary agent), Gardner Fox, and Michael Moorcock. Stories in this genre can't rightly be called science fiction, since they often play rather fast and loose with scientific fact. At the same time, they're not wholly fantasy either, since many sword-and-planet authors tried to maintain some semblance of plausibility to their tales. Thus, they exist in a middle realm, freely borrowing elements from both science fiction and fantasy.
Leigh Brackett wasn't just another sword-and-planet writer. In 1946, she co-wrote -- with William Faulkner, no less! -- the script to the Humphrey Bogart movie, The Big Sleep, considered by some the best hardboiled detective movie ever made. Brackett also wrote the first story treatment for The Empire Strikes Back, owing to George Lucas's great fondness for her tales of planetary mercenary Eric John Stark. Stark made his first appearance in Planet Stories in the summer of 1949 and went on to become the protagonist in many more stories throughout the 1950s and 1960s.
"Queen of the Martian Catacombs" describes Stark's adventures on Mars, where he becomes enmeshed in a plot by criminals who are attempting to stage a revolution that would leave them masters of the planet. Initially, Stark comes to Mars as a mercenary to fight in the little wars between its city-states. When he's caught by Terran agents, though, he reluctantly agrees to work with them in investigating this plot and soon discovers that there's far more going on than anyone realizes. Unlike many sword-and-planet protagonists, Stark isn't a chivalrous straight arrow; he has a wild and unruly nature and his innate sense of justice means that he often acts against the powers-that-be rather than with them. Indeed, Brackett's stories often have an unexpectedly anti-colonialist thrust to them, a theme that becomes ever more important as the series grew over time.
"Queen of the Martian Catacombs" was expanded and republished in 1964 under the title The Secret of Sinharat, which is currently available from Paizo Publishing as part of their Planet Stories line. It's an engagingly written story and Eric John Stark is a terrific character. And of course Leigh Brackett is one of the great unsung writers of pulp fantasy and science fiction. It's unfortunate how few people in this hobby are familiar with her many works, given how much of an impact she's had over its early days. If you're one of those people, do yourself a favor and read a story or two by her -- any one will do; they'll all repay the effort.