it's Friday afternoon, let's have a fun puzzle/algorithm problem to solve.
One of my favorite Nintendo DS games is Picross DS. The game is quite simple, it involves solving puzzles called Nonograms. You can try a simple online Picross clone here: TylerK's Picross.
Nonograms are a grid, with sequences of numbers defined for every row and column of the grid. The numbers define blocks of "filled in" squares for that row/column, but the unfilled areas on either sides of the blocks are not defined. For example, if you have a row that looks like this:
(source: steam-punk.net)
Possible solutions for that row would include:
(source: steam-punk.net)
(source: steam-punk.net)
etc.
The "4 5" simply tells you that, somewhere in the row, there are 4 sequential blocks filled in, followed by 5 sequential blocks filled in. Those will be the only blocks filled in, and the amount of space before/after them are not defined.
A puzzle is complete when all rows and columns meet their definitions, without any contradictions.
Extremely simple game in concept, but it can take quite a while to solve some of them manually. Picross DS's puzzles gradually increase in size up to 25x20 grids, which would generally take me about half an hour to solve.
However, it always occurs to me that it'd be a pretty easy game to write a program to solve. I've never gotten around to it, but perhaps some people here will enjoy the challenge. If a decent number of solutions are posted, I'll benchmark them on a large puzzle against each other, similar to what Paolo Bergantino did here with his Boggle question. There's quite a bit of information on the Nonogram Wikipedia page about methods of attacking a puzzle, if you want to reference that.
Here's an easy-to-parse definition of Puzzle #1 from TylerK's Picross, so you have something to feed a program. Line 1 is puzzle dimensions (probably unnecessary), line 2 is row definitions, line 3 is column definitions. This is just the first thing that came to mind, so if anyone can think of a better input format, feel free to comment or edit this post to include it.
15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10
Answer
Yes, the problem is NP-complete, but that only means that you are (pretty much) stuck with exponentially growing run-times as the size of the puzzle grows. But in real life puzzle sizes don't grow. Hardly anyone bothers to build puzzles that are bigger than 100x100 and the vast majority are smaller than 50x50. Building a solver that will solve 95% of the puzzles published in books and magazines in a fraction of second is actually not particularly challenging. A fairly straight-forward depth-first search system will do it.
What's less obvious is that there is a small fraction of puzzles that are quite nasty and will cause run-times to explode for most simple solvers. Most of these are badly designed puzzles that are also difficult or impossible for humans to solve, but some are particularly clever puzzles that experienced human solvers can readily solve, using deeper insights than most AI programs can manage.
I've written a solver of my own that will solve most puzzles very quickly, and I've done a survey of many other solvers with benchmark results comparing their performance. I also have a discussion of an interesting class of hard puzzles (the Domino puzzles) that demonstrates how some puzzles that are not hard for a clever human prove very hard for most programs. Links to my solver and the Domino Puzzle will be found in the survey.
I think there is still a lot of room for improvement and would encourage people with fresh ideas to take a shot at it. But it's worth noting that the obvious things have been done and there isn't much use in doing them again.