Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

Programming Puzzles

Posted by michael on Sat Dec 04, 2004 12:55 AM
from the my-brane-hurts dept.
Toys Programming Technology
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."
+ -
story
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Programming Puzzles 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.
  • One version [freehackers.org].

  • high return rate (Score:3, Insightful)

    by Tablizer (95088) on Saturday December 04 2004, @01:03AM (#10994843) Homepage 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.
    • 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.
      • 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

  • 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
      • 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.

    • Re:the 15-square puzzle (Score:5, Interesting)

      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).

      • Re:the 15-square puzzle (Score:5, Interesting)

        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
        • The point isnt't to actually cheat, the point is to trick the puzzle solver by moving one of the Rs to the wrong R spot. They'll leave it there when it belongs down below, unless they're lucky or supergeniuses.
    • 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].

    • Re:You can play it here (Score:2, Informative)

      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 AT hotmail DOT com> 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.

        • 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.

  • 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.
    • 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.

  • A plug and a question... (Score:4, Informative)

    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!

  • More computer assisted puzzles (Score:3, Informative)

    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.

    • Re:I will help YOU get a JOB! (Programming puzzles (Score:4, Informative)

      by mtrisk (770081) on Saturday December 04 2004, @01:10AM (#10994870) Journal
      That's all great and dandy, but take a look at the article. It's about a guy who writes programs that will make physical puzzles; this has nothing to do with programming puzzles or exercises.
    • But if you really want to stump a slashdotter:

      15. Go outside and meet girls.
    • ITA Software [itasoftware.com] also has some great puzzles related to employment.
    • Here's the thing. I can look at each example and see a solution. But how important is it to actually give the solution?

      Computer science has devolved into programming. Is the code that important, or the solution in regular syntax?

      I think most people would find this difficult because they forget how to program in these languages, but that doesn't mean they can't see the answer

    • Question 3 Solved (Score:5, Informative)

      by LighthouseJ (453757) on Saturday December 04 2004, @01:38AM (#10994948)
      3. C/C++ : Exchange two numbers without using a temporary variable.

      My Computer Architecture teacher asked us essentially this question, he said Intel asked it in a way more palatible for computer engineers than CS students but it still works.

      If A contains one number (int or register) and B contains the other:

      B = A XOR B;
      A = A XOR B;
      B = A XOR B;

      Explanation:
      XOR is bitwise exclusive OR and is basically true when the bits differ.
      Say if we're dealing with 4-bit numbers. In the example, say A = 1011 (11 in decimal) and B = 0101 (5 in decimal).

      Step 1: If you take the exclusive OR of A (1011) and B(0101), the result is 1110 and put that into B (or A would be fine). Do bit by bit comparisons based on position from left to right and if the bits are different, mark a one in it's position, if they are the same, mark a zero. By this point A contains an original pattern, 1011 (decimal 11) and B contains the difference 1110 (decimal 14) between patterns.

      Step 2: Take the XOR of A and B again and store in the variable with an original pattern (A in this instance). 1011 XOR 1110 comes out to being 0101 (the original value for B) and we store it in A.

      Step 3: Take the final XOR of A and B again, store in last register B. 0101 XOR 1110 comes out to 1011 (our original A) and is stored in register B.

      Voila, 2 values exchanged very elegantly without wasted space and done in the same amount of steps as using a temporary variable. If you still don't understand, it works on the premise that if you have two piece of data, you only need one piece of data and whats different from the two pieces of data, that way you can reconstruct the other piece of data.

    • Solutions to some of these... (Score:5, Informative)

      by Otto (17870) on Saturday December 04 2004, @02:29AM (#10995111) Homepage Journal
      1. Write a "Hello World" program in 'C' without using a semicolon.

      void main()
      {
      if (printf("Hello World!\n") {}
      }

      2. Write a C++ program without using any loop (if, for, while etc) to print numbers from 1 to 100 and 100 to 1;

      Dumb....

      void main()
      {
      printf("1\n2\n3\n... and so on...");
      }

      3. C/C++ : Exchange two numbers without using a temporary variable.

      x^=y; y^=x; x^=y;

      4. C/C++ : Find if the given number is a power of 2.

      if (!( x & (x-1)) printf("x is a power of 2\n");

      5. C/C++ : Multiply x by 7 without using multiplication (*) operator.

      x = (x6. C/C++ : Write a function in different ways that will return f(7) = 4 and f(4) = 7

      int function(int x) {
      switch (x)
      {
      case 7: return 4;
      case 4: return 7;
      }
      }
      Or countless other ways...

      10. Convert (integer) number in binary without loops.

      I assume you mean to print the binary form of an int without using loops. So I didn't use a loop, I used recursion. ;)

      void printbits(int x)
      {
      int n=x%2;
      if(x>=2) printbits(x/2);
      printf("%d", n);
      }

      13. Swap two numbers without using a third variable.

      Same problem as #3 above.

      That's enough for now...

      • 1. int main(void) { if(puts("Hello, world")) {} }
        3. int x = 5, y = 10; x ^= y; y ^= x; x ^= y;
        4. !(var & (var - 1))
        5. x /= (1.0 / 7); =)
        6. simple: int f(int i) { return i == 7 ? 4 : 7; }
        "clever": return 11 - i;

        I only did the ones that specifically listed C. Number 3 (and, I suppose, 4 for that matter) is dubious because ^ won't work for all types. And beware of the "better" version: x ^= y ^= x ^= y; That's not defined behavior in C!

      • 1. Depending on how literally you take this, you might say "I didn't use a semicolon. I used two."

        Failing that, how about:

        cat > filename.c main()
        {
        printf("Hello World")SEMI
        }
        EOF

        gcc -DSEMI=';'

        Or I've seen other people write it as "if (prinf("Hello world")) {}".

        2. "if" is not a loop. that said:

        printf("1 2 3 4 5 6 7 8 9 .... 100");
        printf("100 99 98 97... 1");

        or

        function(int k)
        {
        return (k > 100 ? 0 : printf("%d", k) && function(k+1));
        }

        function(1);

        3. This involves xo

        • Whoops, meant to click preview.

          12. Pick 1. Then, whatever the other person picks, pick 7-n, unless they pick too many 6s. As your final number, pick a number large enough to win. There will always be a number large enough to win... if I'm doing the math right.

          13. See #3 and I'm still not doing it.

          14. Umm... no.

        • It doesn't. It is simply a clever trick on the programmers part. Another quine, in perl is:
          $b='$b=%c%s%c;printf$b,39,$b,39;';printf$b,3 9 ,$b,39;
          Looks confusing right? Actually if you format it nicer it makes more sense:
          $b='$b=%c%s%c;printf$b,39,$b,39;';
          printf$b,39, $b,39;

          You'll see that $b is a string that is equal to the entire source code except for what b is equal to. (Give it some thought and it'll make sense). printf then prints b substituting %c%s%c with the appropriate values ( quotation marks a

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.