Forgot your password?
typodupeerror
Toys Programming Technology

Programming Puzzles 392

Posted by michael
from the my-brane-hurts dept.
An anonymous reader writes "Spotted over at the Economist: 'Sliding-block puzzles look easy, but they can be tricky to solve. The best known is the 15 Puzzle, which became hugely popular in the late 1870s. This involves square tiles labelled with the numbers 1 to 15, which must be arranged in the correct order inside a four-by-four frame.' While we've all tried these puzzles, the inventor of Quzzle set out to design the easiest looking - yet most difficult puzzle around and turned to CS to find it. While the original article touches on it, at the puzzle's site you'll find Jim Lewis, the inventor, wrote a program in Haskell, a functional programming language to find the best design."
This discussion has been archived. No new comments can be posted.

Programming Puzzles

Comments Filter:
  • by TheLink (130905)
    One version [freehackers.org].
  • high return rate (Score:3, Insightful)

    by Tablizer (95088) on Saturday December 04, 2004 @01:03AM (#10994843) Journal
    People are going to buy it because it *looks* simple, but take it back after long times of fiddling in frustration. Or, give it bad reviews in websites.

    Ideally puzzles offer some form of partial gratification if one can see that they are getting closer. I don't know yet if this puzzle is all-or-nothing. There are a lot of different factors that make a puzzle commercially successful. Driving them crackers with deceiptful design is not aways one of them. But, it is an interesting idea.
    • Re:high return rate (Score:3, Interesting)

      by Hatta (162192)
      People are going to buy it because it *looks* simple, but take it back after long times of fiddling in frustration. Or, give it bad reviews in websites.

      Ideally puzzles offer some form of partial gratification if one can see that they are getting closer.


      In solving the rubiks cube the partial gratification of completing a side must be forsaken for the larger goal of solving the whole cube. This didn't stop it from becoming immensely popular.
    • Look up the solution... there's no way that someone works out how to do it without learning the solution... the solution required study from specialized people. The last "move" took a whole bunch of people a long time to work out how to do reliably. The solution is easy to learn as an algorithm, but understanding how it works and reaching those conclusions without help... is a wild leap. It was the most simple-complex puzzle of its time.

      I do believe that some people would understand how to solve the Rubik
      • Re:Rubik's Cube (Score:3, Interesting)

        by Qrlx (258924)
        Or derive the solution...

        I was a kid when the Rubik's Cube came out. Our neighbor was a topologist. He went out and bought the cube, and presented it to his wife to have her scramble it. Then it sat, unmolested, on the coffee table for many nights while the topologist figured out the necessary moves to solve the puzzle.

        It took him lots of pages on a legal pad but he did solve it. After about two weeks as I recall.

        I, being a kid, bought the "How To Solve The Rubik's Cube" book on the family vacation a
      • [How to solve Rubik's cube]: Look up the solution... there's no way that someone works out how to do it without learning the solution... the solution required study from specialized people.

        If you don't really like puzzles, you're right.
        When I bought my Rubik's Cube (was that in '82?), it was because it was a complete enigma to me.
        I simply had to have it because I did not understand it one bit.
        Then I just started to turn, and turn, and turn, and gradually I started recognizing patterns in what specific com
  • the 15-square puzzle (Score:5, Interesting)

    by bm17 (834529) * <brm@yoyodyne.com> on Saturday December 04, 2004 @01:03AM (#10994844)
    here's an interesting factoid: Put 15 squares in a 4x4 frame at random and that state will fall into one of two subspaces; call it parity, odd or even. From there, sliding a piece is an operation that will keep the resulting state within the original subspace. So if you have a friend with one of these puzzles, and you pry out two of the pieces and swap them, you will reverse the partiy of the game and he'll never be able to solve it. I leave it to the reader to come up with usefull applications.
    • So if you have a friend with one of these puzzles, and you pry out two of the pieces and swap them, you will reverse the partiy of the game and he'll never be able to solve it.

      My brother used to pull multiple Rubix Cubes apart and add extra color blocks to a side or two (making it unsolvable), and them give them to Rubix gurus to solve under the guise of needing help. It was interesting to watch them as their facial expression switched from a confident processing mode to confusion mode. We could take be
      • It's easier to just flip over a couple of the edge pieces. With even one of the edges reversed, it becomes unsolvable. Of course, if you do it to only one edge piece it's obviously messed up. Do it to 4 or 5 of them, and it's not quite so obvious. ;)

        Or give a couple of the corner pieces a clockwise rotation. That's even more evil.
      • I'll bet that the labels on most Rubix Cubes are easily removable.
        If you swap the labels on two pieces it could make it unsolvable.

        I'm looking at my Rubix Cube now and I'm noticing that a couple of the labels aren't on straight. Hmmmm....
        Either this means that manufacturing standards are low enough that you probably wouldn't notice this type of hoaxing, or it means that someone has already done it to my Rubix cube and I still haven't noticed.

    • by Fortran IV (737299) on Saturday December 04, 2004 @01:32AM (#10994934) Journal
      A nasty variant of that I've read (but never seen) about is a 15-block puzzle that starts with the pattern:
      R A T E
      Y O U R
      M I N D
      P A L
      Show your victim the solved puzzle, then scramble it up. Before you give it to him, make sure the R from YOUR is moved into the top-left corner (replacing the R from RATE). If your target is someone who thinks he already knows how these things work, he's likely to leave that R right where you put it - destroying the parity of the puzzle. He's seen that the puzzle can be solved, but he'll never solve it until he moves that R (so I'm told).
      • by Westacular (118145) on Saturday December 04, 2004 @05:31AM (#10995529)
        Actually, he can solve it without moving the R if he also happens to use the A from PAL to make RATE. As you said, it's the parity -- and in an even/odd setup such as this, two wrongs make a right.

        For this reason, an alternate way to ensure his confounding is to leave the orginal R for RATE in the corner and then mix the puzzle up such that the A of PAL is near the top and the A of RATE is near the bottom.
        • The original (and I believe it was Sam Lloyd himself who came up with it) had RATEYOUR in on colour of tile and MINDPAL in another, so there was no possibility of swapping the As around.
        • Oops, you're right. I wrote a Q&D simulator for it, and sure enough you can swap the A's to solve the puzzle.

          For this to work right, you also have to color the squares in a checkerboard pattern, like the old plastic ones I used to have. Then the two R's are the same color, but the two A's are not. So if your victim uses the other A, the puzzle still won't look right
    • Niven and Barnes used this trick for a minor puzzle in the novel "The California Voodoo Game" (part of the Dream Park series). The poser swapped two letter R's that could only be told apart by color.
  • The "15" Puzzle (Score:4, Interesting)

    by Claire-plus-plus (786407) on Saturday December 04, 2004 @01:07AM (#10994856) Journal
    I am reminded that the "15" puzzle was set up to be impossibleby the inventor. As is stated on this page [thrijswijk.nl] and other places the way the puzzle was set up made it impossible to solve. This is because there was a prize for the first person to solve it. It looked possible but wasn't. What a scam eh?
  • You'd think he would have created a web version of this puzzle so we could all try it out. :/
  • You can play it here (Score:5, Informative)

    by ambrosine10 (747895) on Saturday December 04, 2004 @01:11AM (#10994873)
    The puzzle can be played here [puzzleworld.org].
    • by Anonymous Coward
      And for those looking to cheat, the solution is availible here (warning: pdf document) [johnrausch.com] on page 20.

      Unfortunately, reading the solution is almost a puzzle intself.
      • FULL SOLUTION (Score:4, Informative)

        by Kelerain (577551) <avc_mapmaster@GI ... l.com minus poet> on Saturday December 04, 2004 @04:03AM (#10995361)
        I've worked through that solution, and writen up a much more aproachable version. Slashdots lameness filter prevents me from posting it in full, so I will link to it on my website here:
        http://www.abysmalstudios.com/files/quzzlesolution .txt [abysmalstudios.com]

        although that will most certainly disapear in a while, as I clean up my server from time to time. In the interests of preserving history, I'll give you the excessively condensed version:

        The goal is to move the A block in the far upper left corner, to the far upper right corner.

        ----
        AA11
        AA23
        **23 - starting puzzle condition (* is a space)
        4556
        4778
        ----

        The code below gives a block (1-8 or 'A') and an u/d/l/r direction.
        AD1LL2U3U6UL3DD2R6UUAR4UU5L7L8LU7RR5D8 LLAD6DL2L3UU AR8RU5U7LLAD8RR2D1R4U6DL2L8LU3D1R2U6RR2D4D1LL8U3U6 UAU7RR5D2D6L8D1R4U2LAL3DD1R8R6R4R2UUAL6DD8L3U6RAR2 DD4L8LUAU6LL7U5RR6DR7L5L3DDAR8DD4R2UU8LD4D2D1LAU

        You will have to break it up manually, because slashdots lameness filter wont even let me put line breaks in. Grab a copy of the text from my site while you can!
        • Re:FULL SOLUTION (Score:3, Informative)

          by Anonymous Coward
          Near the end of the solution is the sequence:

          5RR6DR7L5L

          The correct sequence is:

          5RR6DL7L5L

          Note that changes only one move from R to L.

          Other than that, the solution works wonderfully :-) Thanks for posting it.

        • hardest puzzle? bah...10 minutes and 37 moves total.
          lets see if i can reproduce it here for people.
          AD...1L...1L...2U...3U...6U...6U...3D...3 D...2R... 6U...6U...AR...4U...4U...5L...7L...8L...8U...7R... 7R...5D...8R...8R...AD...6D...6L...2L...3U...3U... AR...8L...8U...5U...7L...7L...AD

          It's amazing what you can learn playing the 11th Hour :)
        • Re:FULL SOLUTION (Score:3, Informative)

          by nachoboy (107025)
          The solution on your website [Last-Modified: Sat, 04 Dec 2004 08:52:13 GMT] mislabels move 69 as move 68, and move 72 is noted as 6DR but should be 6DL.

          Despite that, the instructions were quite helpful. Thank you.
    • I got it in 93 moves on the first try, and I've been drinking tonight. Easier than it looks, or just difficult to get in 84 moves?
  • Whats so special? (Score:3, Insightful)

    by ryen (684684) on Saturday December 04, 2004 @01:14AM (#10994885)
    The Economist needs to do some research on current AI practices.. in particular, that of which taught in a beginning AI course at any university.
    The puzzle presented in the article can be solved easily using a variety of basic AI heuristic search algorithms. A* and its varients come to mind.
    I fail to see the significance of this guys program when people in my beginners AI class do this stuff for course projects every semester.
    • by Fortran IV (737299)
      He didn't write a program to solve the puzzle; he wrote a program to invent the puzzle. "Given a specific class of simple-looking puzzles, find the most difficult to solve." A much broader and deeper problem than finding the solution for a specific puzzle.
    • Judging by actual research, the current AI approach would be to model the puzzles with a gaussian curve, then build a Bayesian network to find the most frustrating puzzle.
  • by Rahga (13479) on Saturday December 04, 2004 @01:38AM (#10994951) Homepage Journal
    First of all, for GNOME 2.10, gnome-game's Klotski has been updated and now supports SVG and comes with 37 puzzles, several classic wood puzzles from Minrobu Abe (this one may be solvable in 227 moves, not sure [rahga.com]...)

    I've also started a hint function that thells the user the precalculated minimum number of moves for each puzzle. The only problem is that Microsoft's Sunshine [rahga.com] puzzle is huge, and I've not seen any solutions for it online yet, never mind a calculated minimum. Any klotski addicts out there want to help me out?
  • Is that old puzzle that apple had where you had to reassemble the apple logo.
    Man I remember messing with that in the labs at school (back when they had macs) instead of doing work.
  • Traffic (Score:3, Informative)

    by FlunkedFlank (737955) on Saturday December 04, 2004 @02:34AM (#10995131)
    The pic in the article reminds me of Traffic [stanford.edu], that awesomely addicting old Palm game (based on a real-world sliding block puzzle). I wish there was a PocketPC version!
  • by AndrewStephens (815287) * on Saturday December 04, 2004 @02:57AM (#10995206) Homepage
    This idea is not new, the guy that runs www.puzzlebeast.com [puzzlebeast.com] uses a similar program to generate ingenious puzzles. Read about the program he uses, then check our his java applets if you have a an hour or eight to spare.

What this country needs is a dime that will buy a good five-cent bagel.

Working...