The sky became stable again, but the chaos didn't end there. People were becoming ill, including children. Shennongshi was a doctor traveling across the world, and healed patients he encountered on the way. Nuwa recommended Zhuge Liang give Shennongshi a hand with this. One day, they arrived at a village where the children were at risk of becoming cursed with an illness. Every child born in the village was associated with 2 out of 28 constellations in the sky. These constellations were also associated with certain bagua properties. The health of each child was determined by the combination of active bagua properties of their two constellations. For boys, the combination of bagua properties had to be the same as one of the predefined combinations. For girls, so long as their properties were different, they were okay. Every night, the moon randomly selected and activated one property of a child's constellation. If a property existed on their other constellation that suited the one selected by the moon, the child remained healthy. Otherwise, the child became unwell. To eliminate the risk of illness, Shennongshi decided to remove some bagua properties. Zhuge Liang summoned the dragon of dimensions for assistance from the professors. >> So Zhuge Liang has arrived in a cursed village as Shennong is struggling to solve a difficult problem. So each child is born with two constellations, a major constellation, and a minor constellation. And there are 28 different constellations. And in this village, there are actually boys, which are represented by the black arrows and girls, which are represented by the red lines, each of having two constellations. And each constellation has some set of the bagua properties that we've seen before. So each constellation, so this constellation here, the wren has these three bagua properties, the lamb actually has all eight bagua properties, and the stag, these five. And so here's all 28 constellations and their bagua properties. Now, there's a condition for maintaining boys to be healthy and that is that their pair, if we take their minor and their major constellation, we have to have a bagua property which fits into this table of healthy pairs of bagua properties. So this boy, let's say, has this pair of bagua properties, which is in the table, so they're going to be healthy. This boy has this pair of bagua properties chosen for his constellations, doesn't appear in the table, so he'll become unhealthy. The girls' health condition is simpler. They just have to have two bagua properties which are not the same, and then they'll be healthy. So this girl is unhealthy, two cloud bagua properties, whereas this girl has different bagua properties so she will be healthy. And this arises because the moon is going through, and every day picking a child, and if they can have the right bagua properties then they'll stay healthy, otherwise, they'll fall ill. So this is the curse. So once we pick a child, of course, we've fixed their two constellations, and the moon will fix a bagua property for one of these constellations. And it better be that we can find another bagua property for the other constellation of the child, which maintains the healthy condition. So for example, in this case, the moon picks this major constellation, and fixes it to the water bagua property, then there are actually three possible bagua properties that we could pick for the fox which would fit in this table, which would keep the boy healthy, so that would be fine. So in this case, if the moon picked this bagua property for the first constellation, we'll find there's nothing we can pick from the fox which will keep the boy healthy, because the only pair which starts with mountains is this mountain-lightning pair, and the fox does not have a lightning bagua property to pick. So what Shennong decides to do is that he should eliminate the risky bagua properties from the constellation so that the moon won't be able to make any child unhealthy. So this is our problem. We've got our children in the village, each born with a major and a minor constellation. And each constellation has some bagua properties that are attached to it and we want to have no sick child on any day. So that is, no matter which child is picked, and no matter which constellation of the child is chosen, and no matter which bagua property of the chosen constellation is picked, there will be a bagua property of the other constellation of the child, which will keep them healthy. So let's try that naively just on a small example. So here we have three boys to examine. We'll look at the first boy in the queue. There's their two constellations, and we can see there's a line between everything. So that means if the moon picks, let's say, water then any of these three would be a good pick. If the moon picks this lightning, they'll be fine. Only problem is if moon picks this constellation and water, right? Then there's no way I could pick a bagua property on the other side which would match the table of possible pairs which will keep a boy healthy, similarly for the top level here. So we should basically remove this bagua property from the bagua properties of this constellation, alright? If that's the case, then we'll look at the next boy. We'll look across their bagua properties, and we'll find, again, there's an example here. We should remove these two bagua properties from these two constellations in order that whatever the moon picked, there'll be another choice on the other side to keep the boy healthy. Then we look at the last boy, and we can see there's virtually no correct pairs left over. Basically, the only things we can keep are these last bagua properties, so we should remove all of the other ones from those two constellations. And now, obviously, we're going to have to do it again, right? We've changed the constellations, so we're going to have to go around again. So we look at the first boy now, and we have to remove some more constellations, or some more bagua properties from this constellation to enforce that he stays healthy. And then we have to look at the second boy, again, have to remove some more constellations to keep him healthy, and we'll look at the third boy, everything's fine here but these two constellations only have one choice, it'll keep him healthy whatever happens. Then we're going to have to go around again because the constellations change, so we look at the first boy again, there's no problem. We look at the next boy, he's no problem, and the last boy, no problem. Okay, so you can see, we did a lot of work. We basically went through the queue every time until there were no changes, but we can do a bit better than that. So what we're going to do is maintain a queue of the potentially uncured children, we'll try a slightly bigger example here. We look at this first girl. Okay, so every property is supported by some other property on the other side, so there's no changes. So we'll put the girl over here, and this seems to be fine, whatever happens, this girl is fine. We'll look at the next girl, again, as the girls are much easier to keep healthy so we can just put her over here saying, she can be cured whatever happens. Now, we pick our first boy, and now, we see in a much tighter constraint that we have to remove some values from this constellation, and if that's the case, we're going to have to put him back in the queue because obviously, the consolation changed. We look at the next boy, we look at the possible values here, and nothing needs to be changed so he can go into this queue of people who look fine, we don't have to look at them again. We look at the next boy, these two have to change, and so, well, one of the ones that changed is a bagua property for this girl, so we have to consider her again, right? So we've changed the constellation, which this girl is interested in, so she may no longer be safe. So she has to go back in the queue, as well as the boy because we obviously changed his constellations. And do the next boy, he can just go into this, appear apparently safe category. The next boy is an out change in the constellation. And again, this is a constellation which is involved in this girl and this boy. So they go back into the queue as well as that boy. We can keep going around, so boys are going to the back of the queue. Again, once this constellation changes, this boy who looked safe has to go back in the queue, and we can keep going, we remove lots of constellations, the number of constellations getting more and more. As we keep removing, things keep going to the back in the queue. Now, this boy is fine, we did no reduction, so he's apparently safe, but she goes back in the queue, he goes back in the queue. This boy is safe, so he can go here. This boy is safe, girl is safe. This boy is safe. This girl is safe. Alright, now, unfortunately, this boy, again, changed this constellation with the girls involved, so she has to go back into the queue with him. This is safe, safe, safe, safe, and we're finally finished. 26 steps and all of our children are now safe. And we've reduced the domains of our consolations quite a lot. So what's happening here? Well, our 28 constellations are the variables, and the eight bagua properties are their domain values. And basically, what we're doing is using these children are constraint propagators. So in fact, the boy constraint propagator is actually a table constraint. So he's a table of possible values that his two constellations have to satisfy. And the girl propagator is actually a not equals constraint, requiring that her two consolations can take different values. And so, we've done this domain propagator for our table constraint, and we've done domain propagation for all of our constraints together. And so, this outcome that no sick child on any day, no matter which child is picked, no matter which constellation is picked, no matter which bagua property is picked, is exactly domain consistency for every possible constraint in this collection. And so, this shows us that we've basically, what we've got is a set of variables, {Xi}, and so that's our constellation. Each have a domain, so that's initial domain, the initial set of bagua properties they have, and the set of propagators which correspond to our children, and what we're trying to find is the largest domain, so we're trying to keep as many bagua properties as we can such that each of these propagators doesn't change the domain anymore. So basically, we don't remove any more values from any domain. So the propagation engine is actually what's going on, this is the core of a constraint programming solver. What it does is repeatedly apply these propagators until they're all at fixpoint. So if I apply them to the current domain, no changes. And we're going to assume that we start with some propagators, which are already at fixpoint. So for the current domain to be D, we know that there are fixpoint. And some new propagators which may not be at fixpoint. And then, we're going to run through this loop. And this loop is exactly, basically, the loop that we've demonstrated with the children. So all the propagators, of course, the old and the new ones, and the queue starts with the new ones in it, although originally we had all of our children in the queue originally, and no old ones, and then, we keep going through the loop like this. We take out queue and we pick a propagator from that queue. We remove it from the queue, and then apply it. So we change our domain, update our domain with that propagator, and then, we have to add back into the queue all of the propagators which might be affected, alright? Once we do that, we set the domain to the new domain, and we keep going round this loop, and you can see that's what we did before. So we chose the first child in the queue, remove them from the queue, apply their rules, their propagation rules, and then we added back all the children who could be affected. And in this case, we added back all the children who shared a constellation with one of the ones that changed. So that algorithm is rather abstract, the choose(Q) is typically a FIFO queue, as we saw in our example, right? We pick the propagator that's been in the queue the longest, so we had our queue of children, we would pick the one who came to the front of the queue, they'd been in the queue longest. And one thing we have to be careful of is we don't add the same propagator twice, okay? There's a queue of propagators, there's no need to have the same propagator twice. The second part was this new, which returns the propagators that are in this set, F, where it's possible they may no longer be at fixed point, right? So the very simplest version of this is which is what we implemented in our example, is we add propagators for the constraints whose variables have changed domain. So remove from the domain of x to the D prime of x, that's the set of variables which have changed, if that intersects with the variables of our propagator, then that propagator should go back in the queue because we changed something about the variables which it knows about, and so it may no longer be at fixpoint. So what can go wrong with this? If we think about this rule, if we've just run propagator F, then it's clearly the case that if F did some propagation, so it did nothing, then one variable in f changed, because we're only changing the variables in f. That means that every propagator that makes a change puts itself back in the queue. But we would expect, if we've just run the propagator, if we ran it again, it wouldn't make any change. That's certainly true for domain propagators, and it's true for many other propagators as well. And we have to be aware that most propagators wake up and make no changes to their domains, right? So, we want to try to avoid waking up propagators if there's no chance that they can make change domains. So we want to have a better definition of new, if we can. So, a propagator is idempotent if basically, if you apply it, and then you apply it again, you don't change anything, and many propagators are idempotent. So an idempotent propagator doesn't need to be put back in the queue immediately after it's exercise because obviously it's at fixpoint at that place, right? So domain propagators are always idempotent, but many propagators which you might think are idempotent, aren't, because of domain holes. So we can think about our X equals absolute value of Y propagator, and if we have here the domain of X is zero, two, and four, and domain of Y is minus 3 and 1, if we run our bounds propagator, then we'll change the domain of X to zero and 2, and the domain of Y of minus 3 of 1. And if we ran it again, right? We would get X staying unchanged, but Y would change again. And that's because when we reduced the domain, we used the value zero and 4 to support the original values of minus 3 and 1. But then, the 4 disappeared, and not only the 4 disappeared, but the 3 disappeared, and so, there's no support left for the next time around. So, as I said, domain propagators are idempotent, and the strongest bounds propagators are also idempotent if the domains they're dealing with have no holes. And we can also have a dynamic idempotent check so that the propagator can actually return whether it was idempotent for this particular execution or not, and that makes it most efficient because then propagator actually can tell the system whether it needs to be re-run or not. The next thing we can do is notice that sometimes only certain kinds of changes in a variable's domain will actually affect a variable, a propagator. So we only need to wake up on some events of interest. And the typical events that we are interested in are when a variable X becomes fixed. So we're only interested in looking at this variable when it becomes fixed or when it's lower bound change, or when it's upper bound change. Or in the worst case, when anything about the domain changes. So that's basically the same event that we've been talking about now. Whenever the variable changes, we wake up anything that talked about that variable but that's a domain change of X. So we have to look and think about propagators for constraints like X not equal to Y, and think what events should wake up this constraint X not equal to Y? As it turns out, the only events that should wake this up are fixing X or fixing Y. The other thing we can do is sometimes we know that for all future domains, we know that we are at fixpoint with this propagator f and its true for all future domains D, so as domains keep going and then will still be solved and the simplest case of this is when there's only one value left in all the variables that f talks about. So if there's only one value left, then all future domains will either be false because we'll remove that value or we'll still have this propagator at fixpoint. And so it's solved, it doesn't need to be looked at again and what that technically means is D, it models c. So basically, any solution of D is a solution of c. And an example, which is interesting for this is X not equal to Y, if it actually propagates, then it will be solved. The only time it propagates is if let's say, Y is fixed to a single value, it will remove that value from X and then there's no way that we can ever violate that constraint again. So, if we're going to optimise our engine, all the disequality propagators with non-singleton domains can start in this solved form, sorry, not solved, but this old propagator, they're at fixpoint. So the disequality propagators will only be woken up when one of their domains becomes singleton, one of the values in that domain, in that propagator, becomes fixed, and after a domain propagator f is exercised, it can be removed from the queue, it doesn't have to go back around, because we know it's idempotent, and if a constraint becomes solved, it can basically be removed permanently from the queue, we never have to look at it again. So once a disequality constraint is propagated, it's permanently solved, and once a constrain is solved, so let's talk about this case, in this case, we have two variables and they both become singleton, there's nothing more this constraint can ever do, we can also remove it permanently from the queue. So let's revisit our example again of the children, and are now we have our initial, the two disequalities are not in the queue, because they have more than one value in each of their constellations, so we know that no matter what, there's nothing to get out of looking at them and then we can start going around the queue again, this time a bit more efficiently. So you look at the first boy, obviously, it doesn't propagation, but because we know it's idempotent, it doesn't go back in the queue, it goes into this list of safe children at the moment. We look at the next boy, it'll do some propagation and go into safe, no, it didn't do any propagation I believe, no, it's all fine. The next boy does some propagation and goes into safe. The next boy just goes straight into safe and the next boy actually does some propagation, and updates a domain of another boy, so that boy actually has to go back in queue. The boy who propagated, notice the boy who propagated went into the safe list, but this boy came out and went back into the queue. Alright, the last boy actually does a stack of propagation and all of these variables are affected, and in fact, we fixed now, you've noticed that we've fixed both of these consolations to have a single value, so now, the girls who involved those variables come out of the queue. But now, this boy has got only a single value left for each of its variables, so it's solved and it goes back into this solved box, but our queue has become much busier because basically, you made a big difference. Now this boy is just healthy, nothing changed. This girl now propagates, because she's only got one value on this side, so we get rid of that value, but then we know that, that not equals propagator is solved, so she can go in the solved cube. Of course, she's changed some domains and some boys come back out of the safe place, and this girl, again, also propagates, but she's also solved, so she goes in there and she brings some other people in and then we can keep going for the boys, right, they keep propagating, We're moving guys from the queue, keep propagating, keep propagating. And some people going back, you're going to keep going through this and we are finished in 18 steps rather than the 26 we had before. Now that might not seem like a big difference, but propagation steps will help in the millions of the billions times during a solving, so this reduction can make a very significant difference. So if you think about running the algorithm, we have these initial domains of the variables which are these bagua properties. Once we run the algorithm, we find that none of these values can be kept and we end up with these final domains and that's just one inference step in the propagation engine. So a propagation engine is this thing that repeatedly runs propagators until there's no domain change so we reach a fixpoint for each propagator and to be efficient, we could only reconsider a propagator when it could possibly change the domain. So it can be solved and we don't have to ever wake it up again. Or we can use events, so we can only wake up propagators when they could make a change, when we look at the events and it's possible that they might make a change. And the key to understanding how propagation engines work is that almost always when we run a propagator, it discovers nothing. So the case that is very, very frequent, overwhelmingly frequent is a propagator does exactly no propagation.