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."
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.
Table-ized A.I.
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.
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?
99 bottles of beer in 175 characte
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.
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.
But if you really want to stump a slashdotter:
15. Go outside and meet girls.
Table-ized A.I.
ITA Software 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
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?
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!
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!
It doesn't. It is simply a clever trick on the programmers part. Another quine, in perl is:9 ,$b,39;, $b,39;
$b='$b=%c%s%c;printf$b,39,$b,39;';printf$b,3
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
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
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.
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.
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 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
Your answer points out that the problem definition is inadequate or ambiguous.
Maybe the people who start generating code without properly understanding and defining the problem to be solved don't get the job? Who wants a programmer who jumps into code-writing as the first step of design?
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.
Believing something doesn't make it true. Not believing something doesn't make it false.
Uh, you have to get the 2x2 block to the upper right silly... Getting it to the lower right does happen as part of the full solution, but it's only the first of the corners you need to visit... See my other post.