New to ProLog
Author Message
New to ProLog

Hello all,

I found out about ProLog a number of years ago when it was included on a
cover-disk of a computer magazine. And now I want to use ProLog to solve a
problem that appears weekly in a news paper (Sunday Telegraph, [UK]). The
puzzle is called a 'Nonogram' or 'Griddler'. Basically it is like crossword
but by using numbers. The idea is to use logic to deduce where coloured
blocks appear to complete a picture (or any other pattern - but a picture
makes it more interesting to solve).

Here's a good link to find out what a Nonogram is:
http://www.*-*-*.com/

What I want to know is:

Would ProLog be a good language to try and solve this?
If so, what would be the best ProLog program to use? (I have already

Thanks

Andy

Fri, 21 Jan 2005 08:00:47 GMT
New to ProLog

Quote:
> Hello all,

> I found out about ProLog a number of years ago when it was included on
> a cover-disk of a computer magazine. And now I want to use ProLog to
> solve a problem that appears weekly in a news paper (Sunday Telegraph,
> [UK]). The puzzle is called a 'Nonogram' or 'Griddler'. Basically it is
> like crossword but by using numbers. The idea is to use logic to deduce
> where coloured blocks appear to complete a picture (or any other
> pattern - but a picture makes it more interesting to solve).

> Here's a good link to find out what a Nonogram is:
> http://www.comp.lancs.ac.uk/computing/users/ss/nonogram/theory.html

> What I want to know is:

> Would ProLog be a good language to try and solve this?
> If so, what would be the best ProLog program to use? (I have already

I wrote a nonogram solver in Prolog.  I think I used LPA, which works
great, but any robust Prolog system would work.  Prolog was an excellent
choice for such a solver.  This was years ago, and I'm not sure how long it
would take me to find the program, but here is what I remember:

The basic solver would repeatedly scan horizontally, then vertically
marking basic must fit squares as filled or open.  It would stop scanning
after a complete scan produced no new marks.  The must fit rules are quite
obvious.

The second stage would scan through a list of heuristics for more complex
deductions, repeating the basic scan after each new mark from a heuristic.
I was adding heuristics every time I discovered a new rule I was using
during manual solutions.  For example, there were perimeter rules, row or
column pair rules, etc.

The third and final stage (rarely needed) would guess a square and then
repeat the first and second stages looking for conflicts.  A guess would
either solve, fail, or be indeterminate (requiring another guess).  A
guess that failed would determine the square must be the opposite of the
guess (open/filled).  Indeterminate results were skipped until all other
unmarked cells were tried.  Very rarely would a indeterminate result ever
need to be revisited (moving on to second level guesses).  It would have
been easy to write some guessing heuristics, too, and might have been fun
to try to solve puzzles with the minimum possible guesses.

As more and more rules were added to the second stage, the third stage saw
less and less use.  Any time I could solve a puzzle deterministically (no
guesses), when the Prolog solver still used the third stage, was an
excellent motivator to find new stage 2 heuristics!

The program would halt and display the board after a solution in any stage,
but a retry would continue to check for multiple solutions.  I recall
solving large nonograms, like 50x50 in seconds on an under 10 MLIPS
machine.  Extending the heuristics was quite interesting, and usually quite
easy, once a new heuristic was recognized.

On the other hand, a basic C program that skipped stage 2 would be fairly
easy to write, and could get the job done!  That is NOT to say the C code
would be easier to write than the Prolog code; only that I find Prolog most
rewarding on those tasks that would be way more difficult in other
languages, and this stage 2 comes close to that.

-- Alan Newman

Sat, 22 Jan 2005 02:53:16 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages