Member-only story
A Prime Example of Pruning
How a little number theory and factorizing make a Bayesian network much more efficient.
Barry Leung posed this little number puzzle:
The numbers 2, 3, 4, 5, 6, 7 and 8 are to be placed in the empty circles so that (i) there is one number in each circle, and (ii) the sum of the numbers in each pair of adjacent circles is prime.
How many possible values are there for x?
This is a very straightforward Constraint Satisfaction problem. We can use the picture above as our guide. Since the top node is a constant, we leave it unconnected to the rest of the network (but it can be referenced internally).
In this topology, all the constraint equations will be in the central node, but it creates a gigantic table:
The needed equations are fairly simple: We make sure that all values are all different, and then the sum is prime iff it is odd and not divisible by 3, or just itself 3.
Valid (A1, A2, A3, A4, A5, A6, X) =…
