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

I will help YOU get a JOB! (Programming puzzles)

[Amsterdam Vallon]

Check these out that I found online, they're great things to use b4 interviews!

Programming Puzzles

Some companies certainly ask for these things. Specially Microsoft. Here are my favorite puzzles. Don't send me emails asking for the solutions.

1. Write a "Hello World" program in 'C' without using a semicolon.
2. Write a C++ program without using any loop (if, for, while etc) to print numbers from 1 to 100 and 100 to 1;
3. C/C++ : Exchange two numbers without using a temporary variable.
4. C/C++ : Find if the given number is a power of 2.
5. C/C++ : Multiply x by 7 without using multiplication (*) operator.
6. C/C++ : Write a function in different ways that will return f(7) = 4 and f(4) = 7
7. Remove duplicates in array
8. Finding if there is any loop inside linked list.
9. Remove duplicates in an no key access database without using an array
10. Convert (integer) number in binary without loops.
11. Write a program whose printed output is an exact copy of the source. Needless to say, merely echoing the actual source file is not allowed.
12. From a 'pool' of numbers (four '1's, four '2's .... four '6's), each player selects a number and adds it to the total. Once a number is used, it must be removed from the pool. The winner is the person whose number makes the total equal 31 exactly.
13. Swap two numbers without using a third variable.
14. Given an array (group) of numbers write all the possible sub groups of this group.

[ von http://www.onesmartclick.com ]

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.

Done the 8 Puzzle

[cmad_x]

I have done the 8 Puzzle in C++. I doubt the 15 puzzle is more difficult. Sure some things might change, but the idea should remain the same :)

Re:Question 3 Solved

[szap]

The solution is canonically written in C/C++ as:

a ^= b ^= a ^= b;

or

#define SWAP(a,b) (a^=b^=a^=b);

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:Question 3 Solved

[Anonymous Coward]

the hacker style (c/c++/java and more):
a = b + 0*(b=a);

~avinu

The solution

[kipsate]

Xn means: move piece X with n squares.

a1, 12, 21, 31, 62, 32, 21, 62, a1, 42, 51, 71, 82, 72, 51, 82, a1, 62, 21, 32, a1, 82, 51, 72, a1

Try it here

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.