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

31–40 of 60 posts

Re: The Hardest Logic Puzzles

#31

Post by hpenedones »

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.

You can find an alternative list of top 10 hardest Sudoku puzzles here (with C source code to find them):

https://github.com/hpenedones/sudoku

Basically, I have a solver and I count the number of backtracking decisions that the solver has to make.

Re: The Hardest Logic Puzzles

#32

Post by crondee »

gweinberg wrote: post #26

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 ne…

I dont think it will max out. I brute forced it upto 10 million and I got the following numbers (5, 679) (6, 6788) (7, 68889) (8, 2677889) sure the numbers are exponential but no reason to suspect that a glass ceiling exists.

Re: The Hardest Logic Puzzles

#33

Post by jules »

ColinWright wrote: post #29
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?

You can solve 2 with a computer by enumerating all possible questions. The gods can be in 3! = 6 configurations, and either da means yes or da means no. So there are 12 configurations in total. A question you can pose to a god will, as far as I can tell, always be of the form "are we in configuration A or configuration B or configuration C ...". So there are 2^12 questions you can pose. You can enumerate all of those and find a question strategy that works.

Re: The Hardest Logic Puzzles

#34

Post by GhotiFish »

javajosh wrote: post #21
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…

I suspect they are mentioned to be gods to suggest that they may be asked extremely complicated questions, which they will interpret from a purely logical standpoint. ie. Not human.

Re: The Hardest Logic Puzzles

#35

Post by GhotiFish »

pliny wrote: post #22
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.

I got the sense alot of people consider a sudoku puzzle unfair if there isn't a discrete set of logical steps you can take to solve it, sans guessing.

After all, if you're looking for a hard Sudoku to solve in that vein, just look at the minimally unique Sudokus. Those required a metric ton of back tracking.

Re: The Hardest Logic Puzzles

#36

Post by GhotiFish »

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?

Difficulty rating systems I've seen essentially take a sudoku and then solve it starting with easy human steps, and working their way down to more complicated logical deductions.

Chokepoints that can only be found in a large set, or having to solve the puzzle with a complicated deduction like an X-wing or Y-wing, raise the number. With guessing as a fully last resort.

Re: The Hardest Logic Puzzles

#37

Post by tempestn »

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…

I haven't looked at the answers yet, but here's what I came up with in pseudocode:

    A: Would one of the other Gods, who is not Random, say "da" \
        if I asked him if God C was Random?
    (DA) {
        :God A or B is Random.

        C: Does "da" mean "yes"?
        (DA) {
            :God C is True.
        } (JA) {
            :God C is False.
        }
        
        C: Would you say "da" if asked whether God A is Random?
        (DA) {
            :God A is Random
            :God B is !God C.
        } (JA) {
            :God B is Random.
            :God A is !God C.
        }
    } (JA) {

        :God A or C is Random.
        B: Does "da" mean "yes"?
        (DA) {
            :God B is True.
        } (JA) {
            :God B is False.
        }
        
        B: Would you say "da" if asked whether God A is Random?
        (DA) {
            :God A is Random
            :God C is !God B.
        } (JA) {
            :God C is Random.
            :God A is !God B.
        }
    }
I found it helpful to build the logic assuming they would answer "yes" and "no" in English. Once that was done it was fairly simply to modify it to handle the da/ja.

Re: The Hardest Logic Puzzles

#38

Post by GhotiFish »

ColinWright wrote: post #25
javajosh wrote: post #20

Earlier quoted context omitted.

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.

I have no idea how you'd make a scoring system that worked well with a hill climbing algorithm. You could check each word for a match in the dictionary, but with a substitution cipher you could essentially turn one word into any other word of the same length (excluding words with the same letter in them). Without a way to check for "close" words, you wouldn't be able to climb the hill. would "pello" score a 0.7 and "hello" a 1? I can't think of a fast way to get that number.

I'd like to try my own hand at this, but the way I'm thinking of making the fitness function doesn't seem like it would be smooth enough.

What did you do?

Re: The Hardest Logic Puzzles

#40

Post by ColinWright »

GhotiFish wrote: post #38
ColinWright wrote: post #25

Earlier quoted context omitted.

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.

I have no idea how you'd make a scoring system that worked well with a hill climbing algorithm. You could check each word for a match in the dictionary, but with a substitution cipher you could essentially turn one word into any other word of the same length (excluding words with the same letter in them). Without a way to check for "close" words, you wouldn't be able to climb the hill. would "pello" score a 0.7 and "…

Take a frequency chart of all trigrams in English, and take the vector product of the frequency in the decrypt with the frequency in English.

So, let E(t) be the frequency of occurrence of the trigram t in English, d(t) be how often it occurs in the decrypted text, and compute:

  Score = sum( [ E(t)*d(t) for t in decrypt ] )
If common trigrams turn up frequently in the decrypt, this will be "large". If uncommon trigrams turn up frequently, this will be "small".
Post reply on HN