#1: Jan Wolter (jan) on Jul 10, 2007

I was wandering around on the web and found quite a lot of programs people have written to solve paint-by-number puzzles. Kind of boring to let a program solve the puzzle for you instead of solving it yourself, but a fun programming problem, and it might be useful to have a full solver here, to automate checking puzzles for solvability. The problem is that though most solvers run very fast on most puzzles, all of them are going to be slow on some puzzles, and if I ran them frequently on webpbn's web server, my ISP would probably get quite annoyed.

But I wanted to feed some of the webpbn puzzles into the solvers to see how they would work, so I built a little experimental export page, at

http://www.webpbn.com/export.cgi

This lets you write out webpbn puzzles in file formats that should be readable by several different programs available on the web. You can then feed these data files to those programs to try them out.

I haven't really integrated this with the rest of the web site, and might not.

The easiest to use is Steve Simpson's solver, since you can just submit the puzzle to his web page and have it solved. (It looks like his ISP is a university, and they are a bit more tolerant, I guess.)

The most impressive of the ones I tried is the solver by the two Olsaks. It's the only one I've seen that does multicolor puzzles, and it also does triddlers and such. You can download an .exe file from their website or build it from the C source. You have to run it from the command-line though - there is no GUI. And all of the "how it works" documentation is written in Czech.

An annoying thing is that there seems to be no standardization in file formats. I have not seen any two programs that can read the same puzzle files.

The export formats currently listed on the export page are all for "clue" files. They contain the row and column clues, not an image of the solution. This is typically what programs that solve puzzles want. Most of the programs that just provide a puzzle solving environment use "image" files that contain a description of the solved puzzle image instead. I'll probably write some export tools for some of those someday (especially if someone has an program they want to export puzzles too).

Many of the pbn programs available come with large collections of puzzles, each stored in their individual file formats. Hardly any of them have any clear authorship or copyright information. It'd be nice to find some of the authors and get permission to import some of them here. Though it's also nice to have mostly puzzles here that grow out of the community here, so I'm probably not going to go charging out to do that. Plus I'd have to write different import tools for each different puzzle file format.

I ran across this page a while ago:

http://www.oberlin.edu/math/faculty/bosch/pbn-page.html

This guy solves Paint-by-Number puzzles by converting them into integer linear programming problems and passing them to a standard LP solving package. He doesn't give any performance info on his web page though. So I got curious and decided to try it out. I used the GNU glpk package, which includes a program name glpsol which can solve the integer LP problems of the form he generates.

Bottom line: not a practical solution technique. It solves some puzzles rather quickly, but others it really gets mired on, including the second example problem from his paper. That one is a 20x20 puzzle that is logically solvable which my pbnsolve program can solve so quickly that it registers as 0 time on the CPU clock. glpsol has been working on it for almost 40 minutes now, and hasn't finished the job yet.

Oh well, interesting concept anyway.

Bottom line: it took just a smidgen under five hours to solve that 20x20 puzzle.

I'm kind in a project of looking over some of the other pbn puzzle solving programs out there, to see if there are any good ideas I can steal for pbnsolve. I'm going to record some of my notes here.

Jakub Wilk's Solver: http://jwilk.nfshost.com/software/nonogram.html

Black and white only. Seems to be pretty good a line solving, but gets slow when searching. Very pretty output options. Author is Polish and documentation in English (or Polish) is next to non-existent. I'd be curious to know more about his line solving algorithm.

Rich Wareham's Solver: http://www-sigproc.eng.cam.ac.uk/ga/index.php?title=User:RichWareham/Nonograms

Black & white only, and rather slow. Trying to solve puzzle #16 (34x34) paralyzed my computer. It must be munching memory as well as CPU to wreck such havoc.

Here's one that's actually pretty good:

http://jsimlo.sk/griddlers/

This is a free windows program that works as a puzzle design and solving environment. It only does black & white puzzles, but it's pretty nice. You can play one of the many, quite good, puzzles it comes with, or edit up your own. You can solve them manually, or let the built-in automatic solver solve them for you (or just help you over tricky spots). The built-in solver is one of the best I've seen, fast and capable.

One of the obnoxious quirks is that when you load puzzle to solve, the default behavior is to display the solution. You have to clear the screen before you can start solving the puzzle you just saw. Fortunately there is an option to turn this off.

webpbn's export page can now export black & white puzzles in a format that can be loaded into this "sg" program. Unfortunately, the save files include a solution image so you can't easily cut/paste them out of webpbn without seeing the solution. I suppose I could figure out a way to do that, if people really wanted it.

I decided to post some more detailed analysis of a bunch of automatic puzzle solvers on a separate page:

http://webpbn.com/survey/

Doing this has given me some good ideas for improving pbnsolve.

I've been doing some updates to my survey of automated pbn puzzle solvers.

http://webpbn.com/survey/

There are people who design general purpose programming languages for solving problems like this. They describe a problem by a set of constraints and then pass the problem to a general purpose solver. It turns out that solving paint-by-number puzzles is a standard example problem, so lots of solvers have been written, but just little demo programs. Still some of them are pretty impressive.

Now, the developers of these solvers are very competitive with each other and have been trying to see who can solve puzzles ths fastest. However, they set of sample puzzles they have been testing on are pathetically easy.

In my survey, I use webpbn puzzles as sample puzzles. The list of puzzles there consists of a few simple puzzles, and then a bunch of hard ones that were selected primarily because lots of solvers choke on them. It makes a much better test set than the ones normally used by these researchers. Problem is, the puzzles are copyrighted by their authors, so I can't distribute them freely as a test set.

So I'm going to be posting requests to this forum for some authors to grant permission for these particular puzzles to be distributed this way. Feel free to say no if you don't like the idea. This isn't really critical to anything, it'd just be nice to have.

You can use any of my puzzles for this purpose. I was specifically thinking of the "Lasts Forever" (#6574) puzzle as that type of puzzle would seem to dictate a change to the way puzzle solvers are designed.

Thanks.

Basically what I'm asking people for is to put these particular puzzles under something like a Creative Commons Attribution License.

I should really do something to let people designate the licensing of their puzzles. The default presumption here is that when someone posts a puzzle here, they license webpbn.com to redistribute it, and they give everyone else a personal use license, but they don't allow redistribution, derivative works, or commercial use by others. It would be nice if the software here let people indicate if they are willing to release their puzzles under more liberal terms.

Jan, I doubt any of mine qualify for what you're working on, but I freely grant you the right to use whatever puzzles of mine for whatever you deem the need.

Thanks. I don't think any of yours are on the list.

This is neither a good nor bad thing. Some of the puzzles on the list are terrific, some are pretty bad. The selection mostly has to do with how much trouble they are for various solvers, which has little to do with how much fun they are for humans.

Looking back at this thread is kind of interesting for me. Looks like I had no particular intention of writing my own solver when I started, but it now exists and is pretty darned good.

The survey of other people's solvers (http://webpbn.com/survey/) is something I still update periodically, and has by now been referenced by a half dozen or so academic research papers, usually about Constraint Satisfaction systems. Quite a few use the puzzles from my test set as a benchmark, and congratulate themselves happily if they can outperform my solver (which a couple have done). AI researchers tend to have very few good benchmarks by which they can actually compare their programs to other people's programs, and I seem to have helped to turn Nonogram Solving into one such benchmark.

Goto next topic

You must register and log in to be able to participate in this discussion.