31/08/2005 @07:31:36 ^08:18:27
hole found in wall of nudist colony
police are looking into it
You have no idea how much I missed seeing this thing
I managed to get the Overdetailed Map Cheat to work in PRBoom. This is a thing I did with the RISC OS engine DIY a long time ago. Instead of everything being boring green triangles, things show up as little shapes like triangles and hexagons and pentagrams and all sorts of stupid crap in many garish colours. It takes a bit of getting used to, at first you don't know what the hell is going on but after a while you just go "blonde, brunette, redhead..."
This is still a work in progress and probably always will be. But it's just nice to actually do something to the Doom source again after all this time, even if I've done it before and all I really did was paste the relevant parts of DIY's am_map.c into PRBoom's. And it's even better to have my map back!
I am caught in a stupid fad
Like seemingly everyone else in the world I made a program that solves sudoku puzzles, after I got stuck on one that I can't reduce any further without having to resort to trial and error. That's not to say the computer version - cringingly named "pseudoku" - doesn't resort to trial and error, because it does. It just does it fast enough so you don't really notice.
The algorithm is roughly this. I think it's called a depth-first search for a solution but I don't know.
- Try to "solve" the board as much as possible. If you solve it completely with no more unknown squares, exit.
- Find a square that isn't already known (that is, only has one possibility)
- For each possibility, make a copy of the board with the possibility at the position, and recurse
- If that guess worked, substitute it in, and go back to the start. If it didn't try the next possibility.
- If you run out of possibilities return to say the board in this state is impossible.
"Solve" means, well, you start off with an empty board where every square is marked that it could contain any of {1,...,9}. Then you put the numbers in. "Solve" means cross out all the possiblities for each square that are in fact impossible. During this it also checks stuff like if there are two of the same numbers in the same row/column/subgrid or if there's a number which can't be placed anywhere in it. The actual "solve" function tries to do this reduction as much as it can until it detects that it can't cross out any more impossibilities. If you give it a really easy board it can solve the thing without having to resort to the recursion at all.
It is a perl script so I could conceivably turn it into an mod_perl module, but it's probable that you could construct a pathological case that would end up being a denial of service attack, not to mention my usual dislike of form processing, etc. Also credits to Graeme and Stik, the algorithm came from my vague memory of their conversation following their both developing similar programs. Also there is a module to do this in CPAN but I didn't look there until after I'd done it.
