NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

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
   # # · # · · ·    2,1
   · # # # · # #    3,2
   · · # # # # #    5
   · · # # # # ·    4
   · · · · # · ·    1
   · · · # # · ·    2

   1 3 1 5 4 3 2
       3 1

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:
1) The 'energy' of the grid is calculated (an objective function comparing the clues that would be created by the current pattern against the desired target clues - when this reaches zero the nonagram is solved), E1.
2) An agent is selected at random and allowed to move, breed or die.
3) The energy of the grid is calculated again, E2.
4) If E2<=E1, then the change in (2) is accepted. If E2>E1, the change in (2) has a probability of acceptance of exp(-(E2-E1)/T), where T is a 'temperature' that is gradually reduced as the annealing proceeds.

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:
(i) In 'to setup', replace setupChickenClues by setupTeaBreakClues
(ii) change the world size (by manual edit of the interface)
to screen-edge-x = screen-edge-y = 3

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).

   ###########·····#########
   ###########······########
   ····###···········#######
   ····###············######
   ····###··············####
   ·····##···············###
   ····#·#·########·······##
   ····##··########········#
   ····###·########·········
   ····###·###··············
   ····###··##··············
   ········#·#####··········
   ········##·####··········
   ········###·###··········
   ········###··············
   ········###··············
   ········########··###····
   ········########··###····
   #·······########·#####···
   ##···············#####···
   ###·············#·#·###··
   ####············##···##··
   #####··········###···###·
   ######·········##·····##·
   #######········#######·#·
   ########······#########·#
   #########·····###·····##·
   ##########····###·····###

NETLOGO FEATURES

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.

RELATED MODELS

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.