Chapter 7: Mechanisms in Programs and Nature

Section 8: The Problem of Satisfying Constraints

Implementation [of constraint satisfaction]

The number of squares violating the constraint used here is given by

Cost[list_] := Apply[Plus, Abs[list - RotateLeft[list]]]

When applied to all possible patterns, this function yields a distribution with Gaussian tails, but with a sharp point in the middle. Successive steps in the iterative procedure used on this page are given by

Move[list_] := If[Cost[#] < Cost[list], #, list]& [ MapAt[(1 - #)&, list, Random[Integer, {1, Length[list]}]] ]

while those in the procedure on page 347 have in place of <. The third curve shown on page 346 is obtained from

Table[Cost[IntegerDigits[i,2,n]], {i, 0, 2^n-1}]

There is no single ordering that makes all states which can be reached by changing a single square be adjacent. However, the ordering defined by GrayCode from page 901 does do this for one particular sequence of single square changes. The resulting curve is very similar to what is already shown.

From Stephen Wolfram: A New Kind of Science [citation]