Hacker News Reader

Comment by asgard1024 | Hacker News Reader

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.

View on HN

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.

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.

How does the traditional "double-ask" question:

    If I were to ask you if you are the
    truth-telling god, would you say "da"?

fit in your scheme?

In particular, I think you'll find the solution to 2 does not fit in your scheme. At least, not as far as I understand it. I'd like to see your scheme for enumerating possible questions fleshed out in more detail, but I don't think I believe you.

And you haven't answered about 4. Or 9.

If I'm not mistaken, a question of the form "If I asked you Q, would you say A?" is the same as asking "Q xor (A means yes) xor (you are speaking the truth)". That is a direct question, which is part of the enumeration.

> And you haven't answered about 4. Or 9.

Umm...yes? I didn't intend to. But if you insist, 4 is not a logic puzzle, and 9 is easily solved in principle but possibly prohibitively long to calculate in practice. Compared to humans, computers are relatively less bad at finding a guaranteed winning move than at playing Go well, so you can't necessarily conclude that because humans play Go better than computers, they would also be able to solve that puzzle faster than computers.

Reply on news.ycombinator.com