Web Paint-by-Number Forum
Topic #46: Automatic Puzzle Checking and 'pbnsolve'
By Jan Wolter (jan)

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

Over the last month or so, I've written a C program to solve paint-by-number puzzles. There is some information about it at http://webpbn.com/pbnsolve.html

It is kind of like the "helper" program that has been around for a long time, but substantially faster and smarter. In the first place, it is a C-program that runs on the webserver instead of a Javascript program that runs in the browser on your computer. Second, it's much smarter about multi-colored puzzles, which the helper was always bad at. Third, if the puzzle can't entirely be solved by it's line solving logic, then it starts doing some trial and error to figure things out.

When I was testing it on my computer, I found was able to solve all except one of the puzzles currently on webpbn (the exception is puzzle #672). For the vast majority of the puzzles, it was able to solve them in less than a second of CPU time.

Of course, sitting around and watching computer programs solve paint-by-number puzzles is basically rather a dull pass time compared to solving them yourself. What I wanted this for was to check newly created puzzles.

On the puzzle creating page, there is now a "Check" button which will run the solver on your current puzzle, and display the results in a pop-up box. It'll tell you if there are multiple solutions, and if there are, it will let you look at one. If the solver didn't need to do any trial and error, it will declare with confidence that the puzzle is solvable by logic alone. If it did have to do some, it advises you to check it yourself. It should also warn you about puzzles that have too little white space to be interesting to solve.

When you publish a puzzle, the check gets run automatically. If there are no problems, it will get published. If there are, it will warn you of them, but still let you publish the puzzle if you want. If it draws any firm conclusions about the uniqueness of the solution, or the logicality of solving the puzzle, it will save those to the database, so that those things won't always need to be manually determined any more.

On rare puzzles, the 'pbnsolve' program will run a really long time. I let it run for two days on puzzle 672 before I decided it was hopeless and interrupted it. If I did that on webpbn server, then my ISP would be very, very angry at me. So the copy of pbnsolve installed here has be configured to give up if more than 1 second of CPU time is consumed and also to run at reduced priority, so that if web page requests come in while pbnsolve is running, the webserver will prefer to let the puzzle solving wait while it handles the page request. All this means that some times it will take more than a second of real clock time for the check to be completed, and sometimes you will get a time-out instead of a result.

The pbnsolve program is open source, so if you like that kind of stuff you can download it and run it on your own Unix system (what?? you don't have a Unix system?). If you make significant improvements to it, I'd appreciate hearing about it.

This is all pretty new, and, likely enough, will prove a little bit buggy. I apologize in advance for any inconvenience. But I think it'll benefit the site in the long run.

I suspect that this will have the side effect of causing more very difficult puzzles to be posted to the site. Some people will take the fact that it reports that a puzzle has a unique solution to mean that the puzzle is solvable, but really a manual test is needed to determine that. Many puzzles with unique solutions are nevertheless darn near impossible for a human to solve.
#2: J.C. Anderson (jc.noserdna) on Sep 10, 2007
Dave? What are you doing...Dave?.....

.....daisy, daisy, tell me your answer true......
#3: Gypso (Gypso) on Sep 10, 2007
Very cool Jan! Nicely done. Thanks ^V^
No, I don't have Unix.
#4: Carolyn Lovelace (prettyletters) on Apr 16, 2009
I don't like that the "checker" is always on while working puzzles now. I always turned it off in the old version. Can the on-off buttons be restored to the new version? Am I simply overlooking the tool to reset this option?

Carolyn
#5: Jan Wolter (jan) on Apr 21, 2009
Look for the "options" button on the puzzle solving page. You can not only turn it off for the current puzzle, you can set it to default off for all future puzzles.

The settings button on the side bar menu also lets you set this.

Though actually, the red-ball error check is different from the "checker". The checker checks newly created puzzles, helping puzzle designers decide if the image they created is solvable.

Goto next topic

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