Translation:The soldier does not fight between the cities.
As you already mentioned, it is because the emphasis is on the location and not on the fact that the soldier is fighting.
Nevertheless, "a katona nem harcol a városok között" as well as "a katona a városok között nem harcol" are correct sentences - but again with slightly different meanings.
The phrasing in thid sentence is a bit weird and i think its causing a few people problems. From what i understand, in the hungarian the emphasis is that the fighting is not happening in the space between the cities. Where as the english sentence has a more natural emphasis on the soldier not actually fighting at all.