Slashdot Mirror
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."
One version.
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.
Without a proper flamewar, Anonymous was undecided on what shell to run.
You'd think he would have created a web version of this puzzle so we could all try it out. :/
The puzzle can be played here.
You can analyze puzzles like this using GAP. Here is an example using Rubik's cube(Google cache since the site seems down to be down at the moment.)
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.
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...)
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 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?
This is what popped into my head upon reading this post... same principal as the XOR method but simpler to explain to layfolk...
A = A*B
B = A/B (gives B the orig A)
A = A/B (gives A the orig B)
I have Unix underpants.
True, but what if you have large numbers, like 64-bit values? To properly handle that, your ALU need to be able to multiply 2 64-bit values and the result is a 128-bit product then perform the division. With my style, you can keep the 64-bit bus sizes and the computation needed is considerably small, XOR is a very cheap instruction computationally.
ooops - should've previewed. The code didn't paste well into HTML. Here's another try:
#include <stdio.h>
int main()
{
if (printf("Hello, world\n")) { }
}
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...
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
The pic in the article reminds me of Traffic, that awesomely addicting old Palm game (based on a real-world sliding block puzzle). I wish there was a PocketPC version!
This idea is not new, the guy that runs www.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.
sheep.horse - does not contain information on sheep or horses.
why does the r have to come from r. You still have to destroy the parity even if you use the r from rate
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:n .txt
8 LLAD6DL2L3UU AR8RU5U7LLAD8RR2D1R4U6DL2L8LU3D1R2U6RR2D4D1LL8U3U6 UAU7RR5D2D6L8D1R4U2LAL3DD1R8R6R4R2UUAL6DD8L3U6RAR2 DD4L8LUAU6LL7U5RR6DR7L5L3DDAR8DD4R2UU8LD4D2D1LAU
http://www.abysmalstudios.com/files/quzzlesolutio
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.
AD1LL2U3U6UL3DD2R6UUAR4UU5L7L8LU7RR5D
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!
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.
I Browse at +4 Flamebait
Open Source Sysadmin
The hardest 4x4 instance can be played at
http://www.cwi.nl/~tromp/oriscript4.html
while the hardest 5x5 instance is at
http://www.cwi.nl/~tromp/oriscript5.html
-John
http://www.johnrausch.com/SlidingBlockPuzzles/quzz le.htm
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.