In addition to Paint by Number, one of the puzzles that became a regular feature in Games Magazine is called Battleships, a logic puzzle loosely based on the mindless two-player board game that's been around for ages. In each puzzle, there are ten ships that must be placed on a 10x10 grid such that the number of ship segments in each row and column add up to the numbers assigned to each.
This seemed like the perfect problem to solve using a computer, and it was one of the first I ever tackled, way back when I was still using Borland's compiler on a Windows 3.1 computer and programming in Pascal! Try to imagine how slowly this solver ran on a 486 66dx, one of the fastest of its time. Shudder.
At the same time, I was learning Windows programming, and wrote a little crappy app that played original Battleships. Such beautiful graphics! Remember when applications could still fit on a floppy disk? Even with all the extraneous code in bwcc.dll, this is still under 250k!
Later on in college, armed with Java and a little more AI knowledge, I returned to the Battleships problem. I still didn't quite get it nailed, though. At least I had a nicer interface for the solver. Maybe one of these days I'll get back to this problem and write a better solver. After all, if I can solve them by hand in a few minutes with some logic and a little guessing, the computer should be able to do a whole lot better.