0

So, I'm working on something involving Knights and Knaves puzzles, and I want them to be randomly generated. I want to make sure that all generated puzzles have only one solution. I don't want multiple solutions to be possible, and I certainly don't want any puzzles being unsolvable.

My project involves two types of these puzzles:

  1. One where you have to determine the identity of all the participants, be they knight, knave, or whatever.
  2. One where you have to find a culprit out of the participants, but do not need to determine whether everyone is a knight/knave/whatever.

So, how would I make sure every puzzle has a unique solution, for both types of puzzle?

EDIT: I should have been more clear. My project is a video game, where each puzzle is randomly generated at runtime, and then subsequently solved by the player. Since the puzzles are generated at runtime, they need to be verified at runtime, prior to the player taking control

Robert Johnson
  • 1
  • 1
  • A reminder of what a Knight/Knave puzzle is might be useful to your question - I assume it's the standard "Knights always tell the truth, Knaves always lie, figure out who's who by asking questions" thing, right? – KReiser Jan 13 '20 at 22:40
  • That is correct. – Robert Johnson Jan 14 '20 at 14:43
  • 1
    If you are generating these puzzles by computer, and the puzzle is intended to be solved by humans (i.e. not computers) with pen & paper, then chances are you will have a small number of knights/knaves, say $< 10$. Why not just try all $2^{10}$ assignments by computer and make sure only a unique solution exists? This will run in almost no time. – antkam Jan 15 '20 at 22:01

1 Answers1

1

I see two alternatives. One, as antkam described, is just to try all the possibilities. That will not take long. The other is to have a set of deduction rules that the program applies and sees if it can come to a final solution. The advantage of this approach is that you can make the puzzles easier or harder depending on what rules you give the program. I believe most Sudoku generators work this way. There are a number of rules which the community has ranked from easiest to hardest. If you tell the computer to generate a five star puzzle, it only uses some of the rules and makes sure it can solve the puzzle. If you ask for a nine star puzzle, it uses every rule it has.

Ross Millikan
  • 374,822
  • +1 for the very relevant comments re: sudoku generators. would you happen to know a good layman intro to the rules & solver involved in determining the difficulty level? (when i googled "sudoku generators" a bunch of results came back and i'm not sure where is a good place to start.) thanks! – antkam Jan 16 '20 at 20:15
  • 1
    No, I would just look at one of the writeups on how to solve sudoku. They usually have the various rules in order and some tell you where the breakpoints are. – Ross Millikan Jan 16 '20 at 21:05