I think the first time I encountered the "person who always tells the truth/person who always lies" riddle was in a Super Mario Choose Your Own Adventure book...
Kyouko, Mizuki and Marii all attend the prestigious St. Arisugawa Girls' Academy, a missionary school run by the Vatican in Japan. Technically, the school isn't even located in Japan, for the three inter-connected artificial islands near Aichi are part of the Vatican grounds and there's even a passport check whenever people enter and leave the grounds. The school of course provides excellent schooling and many prominent families want to send their daughters to the place, but St. Arisugawa Girls' Academy is also a unique schooling situation due to its inclusion of detection in its curriculum. The detective is a protected position in today's society, requiring certain qualifications. St. Arisugawa Girls' Academy is the only place that allows students to study the art of detection at the secondary school level before even entering university. Each spring, the St. Arisugawa Girls' Academy always organizes a special excursion for all students, that mixes up students in all years: two first-years, two second-years and two three-years. Each group of six is then sent to a different location where they have to solve a crime. In reality, the crimes they all encounter are role-played by enormous groups of actors and other people in on the game (the Vatican has money). Each group also won't know what's coming until they are confronted with their specific case, as they only get basic instructions to go to their initial start location. While Kyouko, Mizuki and Marii all participated last year too as first-year students, this year they find all three of them in one group, despite that being very unusual as it's usually two students per year: they are also joined by two first-years and two third-years (as usual). The group are given instructions to board a particular chartered bus and find they're travelling through Aichi Prefecture, where Mizuki also hails from (her knowledge of the local dialect helps them actually communicate with the people in the countryside who speak very thick dialect). As they drive through the mountains however, their driver suddenly dies. They initially think this is part of their excursion, having to "solve the murder of their driver", but it turns he's actually dead, and even their school wouldn't arrange for something like that. The girls however decide to walk the remainder to their destination, as they'll fail their excursion if they don't make it in time. On the way however, they all pass out, and by the time the last one realizes they have been drugged, it's too late.
When the girls wake up, they find themselves in a curious place. They are located in what might be best described as a gigantic donut:there's a huge lake, with a strip of land with house and other buildings surrounding the lake, but beyond the strip of land are just gigantic walls: they're in an open spot that's completely surrounded by unclimbable mountains. The girls are also accosted by men in military uniforms, who accuse them of being spies of the empire. After a while, Mizuki manages to puzzle things together: they are in Utsuhaka Village, a small community that lives deep in this open spot in the mountains, and the people here don't know World War II has ended. The people here had isolated themselves from the outside world during the war, and have been living here since in relative peace, but without any knowledge of the outside world. The only exit out of this place was a tunnel through the mountains, but decades ago the military blew the tunnel up, locking everyone inside. Now there's a small unit of soldiers (some are children of the original soldiers) stationed at the former entrance of the tunnel, but unfortunately for the students, it also happens that some of those soldiers have been murdered. As the only outsiders here, it's perhaps only natural the girls are accused of the murder, but as they try to prove their innocence, the girls also realize the people in this village are... devout Catholic Christians: the people here were originally hidden Christians who lived here precisely out of fear of persecution. The girls manage to prove they're also Christians and are saved by Father Lucas. The girls can't explain how they arrived here, as they just passed out and then woke up here, but Lucas can't help them out of this place: nobody has left this place in decades, so all they can do is live out their lives here in service of the community. The girls learn the village is divided in four sections, corresponding to the cardinal directions, each part housing a different wing of the authorities of the village (church, military, doctor, firefighters etc.). The girls also learn everyone in the village has to be a devout Christian, as nobody can afford to be ostracized by the rest of the village (nobody can leave the village, so ostracization means certain death as you can't get by all on your own). And that makes the murder on the soldiers... impossible, because the ten commandments forbid anyone from commiting a murder. The police officer also asked everyone whether they committed the murder, to which everyone in the village said no: nobody can lie due to the commandments (bear false witness), which means nobody committed the murder. However, during their stay in the village, more people are killed, so it's clear somebody's going against the ten commandments, but who? That is the great mystery in Furuno Mahoro's Gururiyoza Satsujin Jiken ("The Gluriyosa Murder Case" 2013).Gluriyosa is actually the word "Gloriosa" by the way, but then adapted to the Japanese language and then further transformed across time due to accents.
Gururiyoza Satsujin Jiken is the second novel in The Sailor Uniforms & The Apocalypse series, which focuses on the trio of Kyouko, Mizuki and Marii. In this series, the three girls are all better at a different aspect of crime solving, and they always end up dividing the denouement: Kyouko focuses on the whodunit, Mizuki on the howdunnit and Marii on the whydunnit. The books also form one greater narrative, and one of my criticisms of the first novel were indeed that it felt very much as simply the prologue, with many suggestive scenes and episodes which hinted at a greater thing being set in motion, only you don't get to see any of it. That holds too for this second novel, where we again see scenes that suggest there's something big awaiting the three girls and that their training as a detective will be used for something else, but what that actually is, is not made clear here. So that's certainly a thing to remember if you want to start with this series.
People familiar with Japanese mystery fiction will probably quickly recognize this as a kind of parody on Yokomizo Seishi's Yatsuhaka Mura/The Village of Eight Graves, from the name of the village to the way there are 8 great authorities in the village and there's even a duo of elderly twins and some caverns! The setting of a village that still thinks Japan is in the war is pretty interesting, as this is effectively a time travel story. Technology in the village is also outdated, having not seen the enormous developments even in consumer technology, so life is extremely simple here. Which is also what makes the investigation difficult for the girls, as everyone is also quite simple, being quite sure that the ten commandments are enough to prevent anyone from committing murder or from lying, while we as the reader roll our eyes as we see more and more people getting killed. As more people are killed, the girls also notice the murderer might be doing a mitate murder, i.e. murders that are committed following a certain pattern/made to mirror a certain pattern (like nursery rhyme murders), and we even get a whole mitate lecture in this book, which alone makes this a very interesting work to read.
The way the mitate aspect of the mystery was utilized was extremely original by the way, and one of the more memorable examples of this kind of mystery, as it provides a rather novel motive for the murderer to commit to the mitate pattern. I love how the pattern was hidden so brilliantly in the narrative, as most readers would honestly never think of it, but Furuno actually starts hinting at the pattern fairly early on, and it somehow doesn't feel unfair, even if it does demand of the reader to make certain logical steps that might be a bit too far apart. Still, I absolutely love how Furuno used the mitate trope in this novel and how it is woven into the greater story regarding the village.
In a way, this is a kind of isekai mystery, where the detectives find themselves in a world that is not quite like our own, and in this case, the book feels a bit like the riddle where you have people who can only tell the truth, and where there's one liar. The way Furuno expands that idea to a whole village is pretty cool, especially by basing it on the ten commandments, and while near the end, it does feel a bit like a 'logic puzzle' at times, I have to say I was surprised Furuno managed to come up with a fairly convincing way to pull this off and not just write it off as simply 'yes, the murderer lied.'
The solution part of this novel is also enormous, as Kyouko, Mizuki and Marii all get their own, quite sizeable chapters to explain the crimes in terms of their own specific topics (who/how/whydunnit). It's nearly thirty percent of the book that's devoted to the denouement (and the book's not short in the first place), so that gives you an idea of the scale of the tale. I'm still not quite sure how necessary the split in three parts actually is though. Sure, the three girls speak in very different manners and thus explain their parts very differently, but the girls have been together most of the time, and share their information, so ultimately, it feels like a very arbitrary choice to have the three girls each explain things seperately, especially as each of the girls do seem to understand parts of the mystery beyond the scope of their own "responsibilities": it's not like they only figure out their own specific parts, for their stories make it clear they do understand other parts too at least partially (i.e. to explain the whydunnit, for some part you'd to know whodunnit), but for some reason they do only talk about their designated parts. But it's very satisfying to see the three girls tying the many murders since their arrival in the village together in such an epic manner, and there's a lot to love here, as Furuno really makes great use of the very unique setting of Utsuhaka village to carve out a one-of-a-kind mystery.
That said, I do have to admit I found the novel to be far too long, and with the ongoing narrative without real closure, it's not a very accessible book, or at least, I would only recommend this after reading the first one, but that is a lot to ask of someone for example interested in this book mainly for the mitate murders, or the way it uses the liar/truth teller riddle as the core of its mystery.
So there are parts of Gururiyoza Satsujin Jiken that really make it a very memorable mystery novel, as it makes fantastic use of its very unique, isekai-esque setting to explore themes like the mitate mystery and the notion of telling a lie. On the other hand, it is a very long novel too, and a lot of the underlying story is not really explored in detail as it's presented as part of an ongoing narrative. If you read the first book though, I'd definitely recommend this one too, as this one is genuinely the better one of the two, not just as a sequel in a series, but as a mystery novel an sich.