Friday, 20 December 2013

Logicats

I ran some tests on the algorithm for generating logic puzzles in Sandcastle Builder.  In case you aren't one to read code obsessively, the code works like this:

Choose a number of statements and for each statement make it true or false.
For each statement choose whether it will be "and" or "or."
For each true "and" statement, generate two or three true claims to form the statement.
For each false "or" statement, generate two or three false claims to form the statement.
For each false "and" and true "or" statement generate one appropriately true/false claim and then generate one or two additional claims at random.
Asks you to find a statement with a truth value that at least one statement has.

What the algorithm does not do:

Force there to be a true and a false statement.  All statements might have the same truth value.  If this is the case, though, you will always win the puzzle regardless of what you click.
Make sure there is a way for you to determine what the solution actually is.

It's that latter one that I was concerned about.  I wrote code that followed the same algorithm to generate a set of statements and checked how often there was more than one solution set that worked.  It turns out the answer is "most of the time."  Usually even in a four statement puzzle there are three or four different ways to assign truth values that don't violate the conditions set out.  The more statements, the more ways of assigning truth values.  Particularly problematic are things like, "Statement C: Statement C is true and Statement C is not false."  Thanks, I'll get right on that one.

Of course you goal is not to get a truth value for every statement, it is just to find a single statment that has the desired truth value.  The former would be usually impossible given the statements, the latter is actually still very hard but not nearly as hard.

If you are just getting started, though, there is a light at the end of the tunnel.  One boost you can unlock through logicats is one that allows you to spend 50 glass blocks to take a second guess.  Once you have two guesses, almost every puzzle is trivial.  If you are looking for a false statment, find any "and" statement where one condition is that another statement, statement X, is false.  Click this statement and if you are wrong then that statement is true which means all its parts are true which means X is false.  If you need a true statmeent then you look for an "or" statement that claims statement X is false.  If that statement isn't right then it is a false "or" statement which means all of its claims are false so statement X must be true.  Of course it's just a bonus if the statement is contradictory.  X and not X is conveniently always false and X or not X is conveniently always true, so as long as you can find the "or" false/"and" false pattern two tries is all you need.

The odds you can find such a statement are very high.  If you can't then you can look for "X is false or/and X is false" which always give you two mutually exclusive statements regardless of whether you are looking for true or false.  You can also look for tautological statments and use them to do some quick logic on the rest of the statements.  Another trick is to look for statements that claim that they are false.

Obviously a statment cannot actually claim itself to be false because that's a problem in propositional logic.  So if you have a true "and" statement is will never have "I'm false" as one of the conditions because then it couldn't be true.  If you have a false "or" statement then it can't have "I'm false" as a condition because then it would be true.  Because of this we know what part of the code we went through to generate these statements.  If you have statement X which says, "X is false and Y is false" then it's not just handy because you know that statement X must be false, but you also know that statement Y must be true.  If statement Y was false then the conditions of X would be satisfied and so X would be true which can't be.  Similarly, if statement X says "X is false or Y is false" then you know that X is true and that Y is false.  This can be a helpful out if you need it.

All in all, I haven't actually lost a logic puzzle in a long time, but just as importantly, I haven't had to waste seconds thinking about them either.  A quick scan of the options and I am done.  Thinking for a long time about the statements really sucks because: a) you may start thinking about a subset of that statements that is not logically resolvable at all; and b) why would I want to be a sandcastle slowder when I could be a sandcastle fastder?

No comments:

Post a Comment