7 ms·
The Hardest Logic Puzzles
- DanielRibeiro 13y agoWhat about making Conway's Game of Life in Conway's Game of Life? http://www.youtube.com/watch?v=xP5-iIeKXE8 http://www.youtube.com/watch?v=xP5-iIeKXE8
- gidan 13y agoConways' Game of Life is not a strategy game. I built one using Javascript: http://jules.boussekeyt.org/game-of-life/ http://jules.boussekeyt.org/game-of-life/ (instructions: click on some squares and press "Start")
- pearjuice 13y agoIt certainly has a strategy element seeing as the whole game is build upon the premise that particles act depending on a certain strategy.
- deleted 13y ago[deleted]
- lcedp 13y agoThe logic is mind blowing. That's similar to what I imagine to be programming of nanodevices in the future.
- Gormo 13y agoThis is brilliant. It's not even a "logic puzzle" as much as it is an engineering feat. And it's not like software engineering, where you're defining the nature of the system as a whole, and then instantiating it, but more like a physical engineering discipline, in which you're juxtaposing already-existing materials against each other such that their pre-existing properties interact with each other to produce the behavior you want.
- deleted 13y ago[deleted]
- cpuzzle13 13y agoCentury Puzzle - https://itunes.apple.com/us/app/century-puzzle/id627982930?mt=8 https://itunes.apple.com/us/app/century-puzzle/id627982930?m...
- jbri 13y agoSo I just got sucked into that Killer Sudoku puzzle - and ugh, now I have a burning desire to print it out on a big A2 spread to work on it. After the first couple of "gimme" squares, the interface is completely worthless for tracking the information you actually need to remember. There's no good way to express "This square is three more than that square, and also can only be one of these possibilities", which makes it a pain to correlate that with similar information about other squares, but at the same time (at least at this, admittedly early stage) it still feels like you can always make another logical step to another piece of information. I don't even want to look at the others until I've either finished or given up on this one.
- marknadal 13y ago#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 || no" ((da || ja) || (ja || da)) This means, you will always only get the following combination of answers, no matter what A,B,C order you ask: da, da, da; ja, ja, ja; da, da, ja; ja, ja, da; ja, ja, da; da, da, ja; da, ja, da; ja, da, ja; ja, da, ja; da, ja, da; 'Yes' will always have 2 or 3 of the same values. 'No' can only have 1 or 0 values. Now that you have the cipher, you can decode everything. (edit: formatting)
- ColinWright 13y agoHow 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.
- marknadal 13y agoOh, I must not have read the instructions thoroughly enough - I thought the solution was looking for an answer, not for the identities. My bad. I'm guessing the same principle should apply though, I'll comment an update if I don't fall asleep from having been up all night. Thanks for pointing that out, though.
- marknadal 13y agoSo 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 out with awk/sed/grep/command line stuff, from a year ago!
- 13y ago
- impendia 13y agoWhat 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?
- jbri 13y agoThe difference between an "easy" and a "hard" sudoku (and other problems of that ilk) is essentially how many steps ahead you need to think in order to derive useful information. An "easy" sudoku is one solvable by mechanical application of the rules of the game - if there's only number that can be placed in a cell, fill it in, and similarly if there's only one cell in a given row, column, or box that a given number fits in, fill it in there. As things get harder, other logical steps are required. For example, if there are two cells in a line, and both of them can only accept the numbers 5 and 9, you can conclusively say that no other cell in that line can be a 5 or a 9. That's looking one step ahead, and (depending on how often it's necessary) makes for a medium-difficulty puzzle. As you move up difficulties things get more complex, and thinking several steps ahead becomes necessary if you want to make meaningful headway. -- I would expect the "hardest" sudoku would not be one that's only solvable by brute force - that's a rather uninteresting puzzle, for a start. Instead, the hardest (in my opinion) would be one that requires making the trickiest insights in order to make headway without resorting to guess-and-check style exhaustive search.
- pliny 13y agoThe 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.
- GhotiFish 13y agoI 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.
- gweinberg 13y ago#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.
- gholap 13y agoI am not sure whether that info has much bearing on the puzzle itself as such. Even in the case when random randomly answers either "yes" or "no", the solution is equally straightforward and simple.
- gweinberg 13y agoThe 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.
- crondee 13y agoI 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.
- peterderivaz 13y agoInterestingly, Wikipedia disagrees. For a radix of 10, there is thought to be no number with a multiplicative persistence > 11: this is known to be true for numbers up to 10 to the power of 50. http://en.wikipedia.org/wiki/Persistence_of_a_number http://en.wikipedia.org/wiki/Persistence_of_a_number I guess the problem is that when you multiply lots of digits together you become increasingly likely to end up with a 0 digit somewhere.
- crondee 13y agoThanks for the link, I dug a little more and came across [1] which mentions a contribution by erdos to the effect that persistence might not be bounded. I guess I might spend some time to figure out number 12 :) [1] http://web.archive.org/web/20050214141815/http://www.wschnei.de/digit-related-numbers/persistence.html http://web.archive.org/web/20050214141815/http://www.wschnei...
- joachim_b 13y agoCOMBIN3! - (visual logic puzzles) - Online demo: http://combin3.com/demo/ http://combin3.com/demo/
- asgard1024 13y agoHardest? 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.
- ColinWright 13y agoJust out of interest, how would you propose a computer solve number 2? Or 4? Or 9?
- jules 13y agoYou 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.
- ColinWright 13y agoHow 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.
- jules 13y agoIf 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.
- theon144 13y agoHow about xkcd's Blue Eyes puzzle? https://xkcd.com/blue_eyes.html https://xkcd.com/blue_eyes.html
- GhotiFish 13y agoI'm surprised "no one leaves" the guru really doesn't seem to provide any new information. everyone knew she could see someone with blue eyes. Nor does it seem anyone can act on the information, nor does it seem everyone's inaction be taken as new information. If the guru said. I see someone with red eyes, then everyone would try to leave (or only the guy with red eyes would try to leave if the guru wasn't lying). That's the only circumstance I can see where someone could take action. As much as that page insists that there is no word trickery going on, I'm inclined to think I've misunderstood the situation.
- Avshalom 13y agothe version of this I've seen before every one has blue eyes (except maybe the guru). day one some body with blue eyes looks around and knows there's at least one other person with blue eyes, so maybe the guru was talking about that person. day two no one has left so they know there's at least two people with blue eyes or else the blue eyed would have figured it out day one. of course they can still see at least two people with blue eyes, so no problem. Etc... day N hits and they come to the inescapable conclusion that they all have blue eyes and they all leave. I'm not sure how that translates to two eye colors though. I'd guess basically the same, but I'd need to think some more.
- ProblemFactory 13y agoThe guru does provide very indirect meta-information. Everyone's inaction cannot be taken as information on the first day, but inaction over time can. Consider the case with 100 brown and 1 blue person (+ guru). As soon as the guru speaks, the blue person knows their eye colour and leaves. Consider the case with 100 brown and 2 blue people. After the guru speaks, both of the blue people still don't know their own eye colour - the guru could have been thinking of the other one. So both blue people stay on the island on the first night. The other one staying on the island is information to the each of the blue people. Because the other blue one didn't leave on the first night, they must be also unsure - and therefore they must have blue eyes themselves. Both leave on second night. See also: http://img.spikedmath.com/comics/445-three-logicians-walk-into-a-bar.png http://img.spikedmath.com/comics/445-three-logicians-walk-in...
- gholap 13y agoRegarding #2, I read Boolos' paper and found that the way the solution was explained wasn't quite to my taste (it did not have discussion on how one would go about thinking of a solution and step-by-step, logically proceed toward a solution). Add to that, the concepts of abstraction, putting away the complexity into a neat-separate function and then forgetting about the internal details, could be applied nicely to the solution in a number of places and I thought it would make the solution much easier to understand. I took an approach where I keep on reducing the problem to a simpler one by abstracting away some details and complications. Do have a look at my attempt at explaining the solution, especially the process of arriving at the solution (for "The Hardest Logic Puzzle Ever"): http://blog.sujeet.me/2013/07/solving-the-hardest-logic-puzzle-ever.html http://blog.sujeet.me/2013/07/solving-the-hardest-logic-puzz... Feedback's welcome!