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:
- One where you have to determine the identity of all the participants, be they knight, knave, or whatever.
- 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
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.