#1: Mark Boehmer (mboehmer) on Sep 29, 2006

Jan I was wondering what language you program in to solve these puzzles. I would think it would need some sort of PERL script so that it can follow a "pattern" in the numbers, but I'm not too familiar with PERL. If it is Java, C/C++/C#, or something else...is the code available?

There's two-and-a-half languages being used here:

• JavaScript: Programs that run in your browser.
• Perl: Programs that run on the server.
• SQL: Server database access/update language.

SQL isn't really a full-blown programming language, but some pages, like the "Find Puzzles" page are really just a thin Perl wrapper around a lot of SQL.

The puzzle solving screen, the board editor, and the solver/helper are all big Javascript programs. They are sent to your browser by the server when your browser loads the page. You can actually see all the Javascript code by doing "View Source" on the page for a board (you may need to select it from the right-click menu, so that you get the source for the frame that contains the puzzle, not the source for the grey menu or the top level frame). Though the source is sent to you in a slightly compressed form that makes it load a bit faster and makes it a bit hard to read.

But the Javascript program that runs in the browser is generated by the Perl program running on the screen. Different variations of the program are generated for different browser, special data structures for the particular puzzle are compiled by the Perl program and inserted into the Javascript, and so forth.

Some things are done twice. When you edit a board, the Javascript maintains the clues, so adding a black pixel might change a number in a row clue from "2" to "3". This is done by Javascript code. But the clues aren't saved with puzzle. Only the bit map for the solution is saved in the database. When you load a puzzle, a Perl program regenerates the clues from the grid. It compiles the clues into data structures that the Javascript can use. If you look at the page source, you'll see definitions of "tclue" and "sclue" arrays that tell what the clues in on the top and side should be. The Javascript uses these to draw the puzzle. There are also "sre" and "tre" arrays containing the side and top regular expressions, which are used to check for errors. And if the helper is enabled, arrays named "ers" and "ert" with backwards versions of the regular expressions. All of this is generated on the server using Perl.

These data structures, along with a version of the Javascript code tuned for your browser get sent to your browser. The Javascript starts running as soon as the page is all loaded. The first hunk of Javascript draws the board on the page based on the description given in the in the data structures. Other hunks then get activated as you click on things and do various updates to the displayed image.

For more detail on how the puzzle solver works, check the FAQ. Regular expressions (whose syntax almost counts as a fourth language) are the key to both the solver and the error checker (the thing that lights up red balls when you make a mistake).

So the actual solver is a mixture of Perl Javascript. Perl is used to compile the clues into regular expressions, and Javascript uses those regular expressions to solve the puzzle.

Is the code available? Hmmm...

Well, the Javascript you get every time you load a puzzle. I suppose I could make the Perl available too. But frankly I don't see the point. The solver is no stand-alone program. It is pretty deeply embedded into the puzzle solving screen as implemented here. It would need a total rewrite to use in any other context. The description on the FAQ really tells everything there is to know about it. The line solver that is the key to the whole thing is about 20 lines of code. Not complex at all. The board solver just runs the line solver on each row, then on each column, and keeps doing that until it nothing more to solve is found. Converting clues into regular expressions is completely straight-forward. Implementing the whole thing in any language that has regular expressions would be a pretty trivial exercise. If I was still a professor, I think it might make a nice programming exercise for a class.

Building it up into a full solver that could solve any puzzle that can be solved would take only a little more work. It already pushs a record of every mark it makes on the "undo" stack. You'd need to add the ability to make random guess when the line solver no longer gives you anything, and we need to mark that as a guess when we push it on the stack. If we hit an error, we backtrack to the last guess by popping things off the undo stack. Once we've undone our guess, we make a different one, and proceed again. Not hard to do at all. Probably wouldn't add more than a couple dozen lines of code.

But this solver would occasionally run for a very long time. Solving paint-by-number puzzles has been proven to be an NP-complete problem. That means that while you can make solvers that work pretty quickly a lot of the time, there will always be cases where they won't be quick.

Anyway, I don't see any real use in releasing copies of what little code isn't released already.

There are paint-by-number puzzle solving programs available from a number of different people on the net.

Thanks Jan

I'm reviewing various old forum threads, and thought this needed an update.

There are now also substantial parts of the site written in the C programming language, namely the checker (aka pbnsolve) used to check if puzzles have unique solution and the backend of the chat program. These are applications where I needed the code to be fast and efficient so as not to put excess load on the server. C programs are significantly faster than Perl programs, if written carefully.

More updates to an old item:

Source code for the solver I wrote to check puzzles here is available at http://webpbn.com/pbnsolve.html . The rest of the code for this site is not publicly available and isn't going to be.

The website is still mostly Javascript, but it isn't as easily viewable as it was. It's mostly in compressed libraries these days.

Goto next topic

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