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.

You can play it here

[ambrosine10]

The puzzle can be played here.

Question 3 Solved

[LighthouseJ]

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

[Otto]

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