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

high return rate

[Tablizer]

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.

Whats so special?

[ryen]

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.

Re:Whats so special?

[Fortran IV]

He didn't write a program to solve the puzzle; he wrote a program to invent the puzzle. "Given a specific class of simple-looking puzzles, find the most difficult to solve." A much broader and deeper problem than finding the solution for a specific puzzle.

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

[Stevyn]

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

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

[Anonymous Coward]

1. int main(void) { if(puts("Hello, world")) {} }
3. int x = 5, y = 10; x ^= y; y ^= x; x ^= y;
4. !(var & (var - 1))
5. x /= (1.0 / 7); =)
6. simple: int f(int i) { return i == 7 ? 4 : 7; }
"clever": return 11 - i;

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!

Re:Question 3 Solved

[brer_rabbit]

That isn't correct C/C++. You're modifying the same variable multiple times in the same statement. Although it'll probably work on most compilers, the result is technically undefined.

Re:Question 3 Solved

[Lehk228]

I thought that was the whole point of having an order in which operators were resolved, so such things could be done, though the code would certainly be more legible if it were seperated into descrete statements.

Re:Use only subtraction and addition

[hazem]

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?

Re:the 15-square puzzle

[Fortran IV]

Oops, you're right. I wrote a Q&D simulator for it, and sure enough you can swap the A's to solve the puzzle.

For this to work right, you also have to color the squares in a checkerboard pattern, like the old plastic ones I used to have. Then the two R's are the same color, but the two A's are not. So if your victim uses the other A, the puzzle still won't look right