The solution uses something called common knowledge, which is that everyone knows that everyone knows that every one knows, ad infinitum. Before the queen makes the announcement they may all know that the other husbands are cheating but they don't know if everybody else knows. To see the difference consider the case where there are only two husbands (H1, H2) and two wives (W1,W2). So, every man has cheated on his wife, and when the queen announces that a man has been unfaithful, then consider the situation from W1's perspective. She knows that H2 has cheated on W2, she doesn't know that H1 has cheated on her, and she can't talk to W2 about it. With the announcement, from her perspective, there are two possibilities (both H1 and H2 are cheaters), or (just H2 is a cheater). Now, to continue we need to think about what W1 will think about these two possibilities given her incomplete information: If it were possible world where (just H2 is a cheater) and H1 is honest, then since W2 would know that H1 hasn't cheated then W2 would conclude that (just H2 is a cheater) since at least one husband had cheated. Thus, by the laws of the island W2 would kill H2 the day of the announcement.

Since W1 considers it a possibility that her husband, H1, was faithful, she won't do anything the first day; instead she'll just wait to see whether W2 kills H2.

By symmetry W2 will go through the same line of reasoning about W1. Thus, both will do nothing the first day. So then on the second day, W1 will realize that (just H2 is a cheater) must be false, since W2 didn't kill H2. So, she'll go ahead and kill W1. (Apply the same reason symmetrically to W2). Therefore, they'll both kill their husbands on the second day.

The rest of the details are pretty easy to establish. The point is that 99 days later all the men are killed.