Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Hardest Logic Puzzles

conceptispuzzles.com

Post reply on HN
Print view View original

21–30 of 60 posts

Re: The Hardest Logic Puzzles

#21

Post by javajosh »

marknadal wrote: post #9

#2 is easy, by using double negatives and asking the same question to each god (asking different questions does you no good): "Is the other non-random god capable of lying?" The truth telling god will always answer: "yes" (da || ja) The false telling god will always answer: "yes" (da || ja) [the truthful answer is 'no', but this god tells only lies, therefore the answer is 'yes'] The random god will answer: "yes || n…

That's an interesting insight, and it may be useful as part of the solution, but it doesn't solve the puzzle. The question is how to determine the identity of the three gods with three questions.

Personally, I think it's interesting that they are gods. Does this mean that they can answer questions about what WILL happen? E.g. you could ask a god what the next god will answer. If the answer is correct, that's the true or random god. If the answer is wrong, then it's the false or random god. But then we get recursive rather quickly if we ask the question twice in a row. :)

Re: The Hardest Logic Puzzles

#22

Post by pliny »

impendia wrote: post #13

What makes a difficult sudoku problem difficult? Is it possible that a brilliant, experienced solver would find the right "tricks" to solve the puzzle? Or is the sudoku such that it can be only solved by some flavor of exhaustive search on the space of potential solutions?

The more backtracking you have to do, the harder it is for a human to solve / more likely that your weak flesh brain will encounter a stack overflow.

Re: The Hardest Logic Puzzles

#23

Post by TallboyOne »

marknadal wrote: post #16
ColinWright wrote: post #10

Earlier quoted context omitted.

How can you then distinguish between the two non-randomly-answering gods? They will answer the same, and the answer from the randomly-answering god appears to contain no useful information.

So I started to work it out, only to discover the link about the problem in the article gives it away - counterfactuals can be used, so might as well read that instead of any thing I come up with. And thus I just wasted a bunch of time trying to figure out which specific one worked (now erased) ... but my hunch was correct! (Although hunches are hardly proofs, tsk tsk) Also, I want to thank you again for helping me o…

What's a counterfactual? can you give a simple explanation of how that solves the problem?

Re: The Hardest Logic Puzzles

#24

Post by gweinberg »

#2 is really only difficult because it's easy to misinterpret the rules. Random doesn't randomly answer yes or know, he randomly decides whether to answer truthfully or falsely. So for example if you ask the recursive question "are you answering this current question truthfully" he will answer yes either way. Or rather, his word for yes. Once that rule is clear, the puzzle is pretty straightforward.

Re: The Hardest Logic Puzzles

#25

Post by ColinWright »

javajosh wrote: post #20
ColinWright wrote: post #19

Earlier quoted context omitted.

Apropos of nothing in particular ... Not bothering to use ROT13, I just dropped that into my generic substitution cipher decoder and it spat out the answer almost immediately - quite pleased with that.

Interesting. You cycle through substitutions and match against a dictionary to detect a hit?

Nope, I use the shotgun stochastic hill-climbing algorithm I wrote for something else, with the ballistic option disabled.

In short:

    While True:
        Generate a random key
        "Decode"
        Score
        Start timer
        While timer not expired:

            Perturb the key
            Score
            If better:
                Keep the new key
                Reset timer
        Print decrypt
In this case the first output was completely readable.

Re: The Hardest Logic Puzzles

#26

Post by gweinberg »

The Martin Gardner doesn't really seem to fit, since it is trivial to solve using brute force. Even if using a computer is considered cheating, there are shortcuts to use to keep from having to try everything. For example, having a "1" digit gets you nowhere, a "0" kills you, and a "5" and any even digit also kills you (and the 5 will persist at the end if you don't have an even digit, so it will probably kill you next round).

This led me to wonder, does persistence ever max out? It seems likely to me that it does.

Re: The Hardest Logic Puzzles

#28

Post by asgard1024 »

Hardest? Are you kidding me? A computer can solve these quite easily.

If you want really hard logic puzzles, get puzzle books from Peter Winkler (such as Mind Benders or Connoiseur's Collection). These sometimes even contain unsolved puzzles as well.

Re: The Hardest Logic Puzzles

#29

Post by ColinWright »

asgard1024 wrote: post #28

Hardest? Are you kidding me? A computer can solve these quite easily. If you want really hard logic puzzles, get puzzle books from Peter Winkler (such as Mind Benders or Connoiseur's Collection). These sometimes even contain unsolved puzzles as well.

Just out of interest, how would you propose a computer solve number 2?

Or 4?

Or 9?

Re: The Hardest Logic Puzzles

#30

Post by Someone »

impendia wrote: post #13

What makes a difficult sudoku problem difficult? Is it possible that a brilliant, experienced solver would find the right "tricks" to solve the puzzle? Or is the sudoku such that it can be only solved by some flavor of exhaustive search on the space of potential solutions?

According to http://www.nature.com/srep/2012/121011/srep00725/full/srep00..., there is a nice correlation between perceived difficulty and a nice, objectively computable number.

So, a sudoku seems to be extremely hard iff η > 3.

And no, you don't need to do an exhaustive search.

Post reply on HN