Level 32

I love these sorts of puzzles, but I'm a bit embarrassed that I was reduced to writing a second solver in C, when the Python version proved too slow after all my optimisations

A hint for those who have been waiting a few days for a solution to be found: there are a couple of different algorithms you can use here, one of which scales really well. If you get bored, try a dramatically different approach.

PS., the Javascript doesn't work correctly in Safari - particularly on the third page

[mjpieters]

the Javascript doesn't work correctly in Safari - particularly on the third page

Botheration! It works fine in konqueror.... It's all standard ECMAscript and DOM.

How long *should* it take in python?

My first attempt ran all night and consumed huge quantities of memory

Much more aggressive pruning made the warm up solution run about 10 times faster - the serious one has been running 15 minutes and is still going...

Martin

Well, on my G4 powerbook the C version of the brute-force solver took about 40 seconds on the second puzzle.

My Python solver improved in performance more than 50x through optimisation, but didn't come close to solving the second puzzle due to obscene memory usage - it didn't get more than two levels deep.

All I can recommend is:
1. To further improve your current solution, minimise memory usage as much as you can.
2. Think about radically different algorithms for solving the problem - there is one which will solve it in seconds, even in Python.
3. If all else fails, do what I did and write a highly optimised version in a different language.

There is a fast algorithm that isn't much more complicated than the dumb brute force one. My totally-unoptimised-who-cares-about-speed Lua implementation solved the big one in 45 seconds.

Work in two directions. Work on one thing at a time.

Use what you know to find all possibilities for each piece. Your knowledge comes from more than one place.

Increase your knowledge at every opportunity.

Or you can cheat and google for someone's ready-made solver.

This was a good level. It was the first that felt (to me) like it needed some real programming.

How long *should* it take in python? ...

There are two quite different Python programs on the solutions Wiki today that solve "the big one" in less than a second (on fast boxes), at least one of them including the time to display progress-so-far using Tk.

Both of those are non-trivial programs. This level is much more (than previous levels) about coming up with a "good" algorithm. My first program to solve this would not have finished over the age of the universe (there's a discussion of that on the Wiki ). My second solved the big one in about 3 hours, including time to prove that the solution was unique. My third attempt cut that to about 3 minutes. My current fastest Python program solves it in less than a fifth of a second (with Tk progress-so-far updating disabled; about 0.6 seconds with Tk updating).

So if you can get the solution using Python in somewhere between a fraction of a second and the lifetime of the universe, you're doing exactly as well as I did .

hmm, my brute force approach solved the little one in less than a second. The big one has been running over night. As an exersize to figure out the scope of this I tried to work out how to calculate how many figures I'd be going through. The little one came out to 10500, which appears to be right. The big one, however, came out to 82328990834424911796572570759111661840585435283304767104151084911820800000000000000000000000.

I'm not sure if that's correct, but I'm only on #42209000. I guess I'll have to re-write for some pruning

... The big one, however, came out to 82328990834424911796572570759111661840585435283304767104151084911820800000000000000000000000.

I'm not sure if that's correct, but I'm only on #42209000. I guess I'll have to re-write for some pruning

You'll eventually see that same number again, on the solutions Wiki. Unfortunately, it appears in a discussion of why my first algorithm would not have completed over the lifetime of the universe .

Well, I rewrote my brute force version in c , and while it ran much faster, the universe would still end. I added pruning and it got better, but it would've probably still taken days. Aggressive googling finally turned up a few algorithms (had to figure out what to look for), which I was able to translate into a script that ran in 1.25 seconds

I'm going to re-read my code a few times until I understand it completely while I also stare at #33 So far I know that it works in two directions, along with a few other tidbits of info that would probably be spoilers to anyone not actually on #32

I wrote a Pascal program that solves the second puzzle (32x32 one) in 2-3 seconds. But when I try the URL it _looks_ like I get a 404. The solver works, though... hmmm.. does that thing have a name I should know?

There is a specific word for that thing. You've seen the word enough times.

I figured out a way to solve the puzzle efficiently for the big one. My program that solved the little one would have taken centuries to solve the big one. I thought of a way of reducing the possibilities, figuring I'd get down to a manageable size. As it turned out, I could apply this over and over and it eventually reduced the possibilities to 1. I haven't tried to prove whether this will work in all cases.

Hello.........

Much more aggressive pruning made the warm up solution run about 10 times faster - the serious one has been running 15 minutes and is still going..

Thanksss.........
best way to get rid of acne