Programming Puzzles

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

Comments

the 15-square puzzle

[bm17]

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.

Re:the 15-square puzzle

[Fortran IV]

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

[Westacular]

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 "15" Puzzle

[Claire-plus-plus]

I am reminded that the "15" puzzle was set up to be impossibleby the inventor. As is stated on this page 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?

Re:high return rate

[Hatta]

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.

Re:I will help YOU get a JOB! (Programming puzzles

[ajs]

ITA Software also has some great puzzles related to employment.

Re:I will help YOU get a JOB! (Programming puzzles

[LnxAddct]

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,39 ,$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 and the value of $b in the middle). It's going to be hard for a non-programmer to grasp, but hopefully this helped.
Regards,
Steve

Re:Rubik's Cube

[Qrlx]

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 and was solving the cube in under a minute shortly thereafter. I've long since forgotten the patterns, but I bet the topologist could still solve it.

Re:Whats so special?

[itsNothing]

From the sound of it, the guy did an exhautive search on the trees of all puzzles which were 4x4.

And incredibly so, he did it in Haskell (crowd gasps!), a functional programming language which requires recursive execution of algorithms. What was it, 50 lines of code? 75?

What impresses me is how this guy got so many column inches in the Economist. I need better marketting...

Map of Quzzle puzzle space

[paylett]

Hey, don't know if anyone's still reading comments for this article now but..

We've put together a graph linking all the positions you can get to with the Quzzle.

Starting point shown in red. Top/right Ending point(s) shown in blue. And the (incorrect) bottom right solution in pink. The path from start to solution is shown in green.

Notes: Used aiSee to draw the graph. The circuits that seem to appear in the solution are just due to the graph being drawn with crossovers.

Ok.. time to go and find something less geeky to do with the rest of the evening.