This Conan story is set in mythical Hyborian versions of IndiaâPakistan (then united) and Afghanistan (Vendhya and Ghulistan respectively).
The death of Bunda Chand, King of Vendhya, via a curse channeled to his soul through a lock of his hair leads to the ascension of his sister, Devi Yasmina, who vows to get revenge on his killers, the Black Seers of Yimsha. Conan, meanwhile, has become chief of a tribe of Afghuli hillmen. Seven of his men have been captured by the Vendhyans and Yasmina intends to use them as collateral to force Conan to kill the Seers. However, Conan infiltrates the border fort where they are held and kidnaps the Devi instead (with the intent of exchanging her for the seven men). The problems are complicated by Kerim Shah, an agent of King Yezdigerd of Turan, who arranged Bunda Chand's death in order to lead an army through the mountains and invade in the subsequent confusion and turmoil. His contact with the Black Seers, Khemsa, has fallen in love with the Devi's maid Gitara. They decide to strike out on their own, kill the seven hillmen and pursue Conan and Yasmina to kill them both as well.
Conan escapes into the Afghuli villages of the Zaibar Pass and Himelian Mountains (Hyborian equivalents of the Khyber pass and Himalayas). Yar Afzal, chief of the Wazuli village, is killed by Khemsa and the people turn against Conan, yet he manages to escape again with Yasmina. Khemsa again catches up with the pair but his attack is interrupted by four Rakhshas from Yimsha. His original masters kill Khemsa and Gitara, stun Conan and kidnap Yasmina. Khemsa survives a fall from the mountain-side long enough to give Conan a warning and a magic girdle. Shortly after, Kerim Shah and a group of Irakzai (Iraqis), also intent on capturing the Devi for King Yezdigerd, encounter Conan. They join together to rescue Yasmina, both open about their private reasons for doing so, and approach the mountain of Yimsha. Most of the men are killed in the attempt but, following Khemsa's warnings, Conan succeeds in killing the Black Seers and rescuing Yasmina.
As they escape they encounter the Turanian army of King Yezdigerd in conflict with Conan's former hillmen (who blame him for the death of the seven captives). Despite their attitude, Conan feels obliged to assist but cannot abandon the Devi. This problem is resolved when a Vendhyan army, invading the mountains to rescue their Queen, arrives. Together, Conan with his Afghulis and Yasmina with her cavalry, they destroy the Turanian army. Conan leaves with the hillmen and the Devi returns to her country.
Though they are strongly attracted to each other, the affair between Conan and Yasmina never gets beyond some kissing. Their respective roles pull them in opposite directions - she the Queen of Vendhiya, he the leader of roving hillemen engaged in constant robbery against her domain. In the original Howard stories, they never meet again. In the 1957 Return of Conan BjĂśrn Nyberg and L. Sprague de Camp let Conan and Yasmina meet again for one night of intensive love-making, many years later - when he is already King of Aquilonia and there is no more a conflict of interest.

Question: What makes the relationship between Conan and Queen Devi so difficult? 
Answer: She has queen duites in her country while the hillemen engange in robbery of her domain
Alternative answer: Their respective roles pull them in opposite directions.