The puzzle generator
Kenneth Tolman
I am very interested in computer programs that generate puzzles of various
sorts.
The true false puzzle.
A bunch of named people sit around saying true and false things. They
name each other and say that so and so is lying or telling the truth.
The program would generate such a puzzle of X complexity randomly.
A way to solve such a puzzle is to consider each statement to be a
logic statement. Then there is a series of logical statements which
can be AND together with every possible assumption of true false possibilities.
In such a puzzle we must have some people telling truth, and some telling
false. With N people we could have 1, 2, 3 .. N-1 people telling the truth.
This makes N-1 possible puzzles.
(Example, with N = 3 we could have 1 liar or 2 liars, not 3 or zero)
Each player could theoretically say that any particular player was:
telling the truth
lying
no comment on that player
So each player says any of 3^N things. Thus the complete number of
possible puzzles of size N is:
(N-1) * N * 3^N pretty big!
N total
1 0
2 18
3 162
4 972
5 4860
6 21870
Of course, most of these will be nonsense. For example, all the puzzles
where no one says anything about anyone will be worthless. Also some
of these will have multiple solutions. I have no idea how many of each
size is "valid" and "one solutioned".
It seems that the computer could figure out each particular puzzle
for its validity. It would do this by constructing the logic table for
each one, then testing it with replacement trying to reach truth.
Questions:
What would be a good next addition beyond each player just saying other
players are true or false?
(possibly using "or", some sort of ordering, alternating true false, etc)
How can this numerical explosion be handled computationally for the
larger puzzles?
Would anyone have a use for such a program? Maybe in a MUD?
What other puzzle generators would be good to work on?
(I failed previously at a sliding block constructor- search space too big)
In the puzzle maker above, how can the computer tell if the solution is
obvious?
John Farrell
>Of course, most of these will be nonsense. For example, all the puzzles
>where no one says anything about anyone will be worthless. Also some
>of these will have multiple solutions. I have no idea how many of each
>size is "valid" and "one solutioned".
As it turns out, the simple versions of these problems, where you can only
make statements of the form "X tells the truth", and "Y lies" are boring.
In the solution, there are two groups of people: liars and truthtellers.
A statement by X that Y tells the truth means that X and Y are in the same
group. A statement by X that Y is a liar means that X and Y are in different
groups. Hence if there are n people, you only need (n-1) statements to divide
the people into a unique partitioning. Any other statements will be redundant
or inconsistent.
Now here's the annoying bit. Just from the testimony of the people, you
can't tell which are the liars and which are the truthtellers! You can find
the two groups, but you need additional information to decide which to trust.
> What would be a good next addition beyond each player just saying other
>players are true or false?
> (possibly using "or", some sort of ordering, alternating true false, etc)
A simple statement type which could be added is "X is the same as me", or
"Y is different from me". If I say "X is different from me", it means that X
is a liar, no matter what I am. This allows a unique solution. If there are n
people, n-1 statements of the form (tells the truth/lies) and 1 statement of
this form can provide a unique solution.
> Would anyone have a use for such a program? Maybe in a MUD?
Well I've just turned it into a great student assignment :-).
> In the puzzle maker above, how can the computer tell if the solution is
>obvious?
Now that I know how, they're all obvious :-(.
Friendless