NetLogo User Community Models
by Robert Holmes (Submitted: 06/18/2003)
WHAT IS IT?
This program solves nonograms (sometimes) using simulated annealing.
A nonogram is a logic problem, invented in Japan and popularised in the UK. It consists of a rectangular grid with one set of clues for each row and column of the grid. Solving the clues determines which cells in the puzzle are to be shaded to produce a picture. Clues are of the form Љx1,x2, ... ,xnњ, which translates as x1 shaded cells followed by at least one blank cell, followed by x2 shaded squares followed by at least one blank cell etc.
For example, the following nonogram (it's a chicken, honest) has clues as shown
и # # # и и и 3
1 3 1 5 4 3 2
If you want to solve anything other than the 'chicken' nonogram, you'll need to download the file and tinker with the input routines.
HOW IT WORKS
Although there is a deterministic (and fast) algorithm - see "Related Models" below - I decided to try a simulated annealing approach:
HOW TO USE IT
1) Initialise the nonagram by selecting a value for fraction-on (the fraction of patches that are originally occupied) and pressing 'setup'.
2) Set temperature (somewhere around the top end of the scale is good), and set the relative weights of agent death, breeding and moving (the bigger the weight, the more likely that action will be chosen by an agent). Leave wt-diff at zero for the time being (see 'Things to Try').
3) Press go. You'll see the developing solution in the grid and a graph of the global error as the annealing progresses. When this graph hits zero, the solution is found and the run automatically stops.
THINGS TO NOTICE
As the global error reduces and you start to see the emergence of some vague pattern, start reducing the temperature. Somewhere round the 0.4 - 0.6 mark, you'll get a solution. If the temperature is much hotter, the probability of moving away from the solution is too high.
Once you have reduced the temperature, you might find that the global error gets stuck at some low but non-zero number (i.e. it's fallen into a local minimum). If this happens just briefly boil the chicken again and return to a low simmer.
THINGS TO TRY
1) Different objective functions (I). Use a Euclidean distance in the objective function rather than a city-block distance. Any effect?
2) Different objective functions (II). On a large nonogram with large contiguous blocks, it might be a good idea to penalise differences in number of clues (see to-report calculateError). Does this have an effect?
3) Large nonagrams. I have included the clues for a 25 x 29 nonagram called 'Tea Break' (I got it off the Web somewhere). To use it:
The solution is below. I've not been able to converge to it. This rather suggests that simulated annealing is *not* the best solution to solving nonagrams (also see 'Related models' below).
I used patches rather than turtles as my agents because of the one-to-one correspondence between patches and cells of the grid - I didn't need to worry about how to evaluate objective functions if multiple turtles decided to squat on the same patch.
Simulated annealing might be fun but it's criminally slow. It's actually possible to work out an extremely fast algorithm that relies solely on the same sort of logical processes you'd use if you were solving one long-hand. For example, you'd probably start with that 5-row in the middle. The extreme positions for the block are either all the way left and all the way right, that is:
# # # # # и и and и и # # # # #
which means that the three central blocks must be occupied thus:
и и # # # и и
You can then use this as a constraint on the column clues, working out what cells can and cannot be occupied, and continue in this fashion till the nonogram is solved. You can find a Java program that uses this approach at http://www.morleysoft.freeserve.co.uk/computing/java/griddler.html. It might be fast, but it's not as much fun as boiling the chicken and cooling it down.
(back to the NetLogo User Community Models)