Land of Boole

This is simple computer game with more behind it than meets the eye. The land of Boole consists of a number of islands and a number of tribes. Every island has exactly three people, each from a different tribe. If an island has only men or only women, the gods are angry (not to mention the men and women) and the volcano on the island erupts. But you can fix this! By clicking on a person in an island, you cause all the women in the tribe switch places with all the men in the tribe. (Each tribe is a different color.) In other words, the women from the tribe leave the islands they are in and are replaced by men of the same tribe, and vice versa. Of course, an island that was previously happy might become unhappy. However, in this game there is always a way (actually two ways) to make every Boole island happy.

My fellow geek friends will recognize that this game is an example of a famous unsolved problem in computer science. By “unsolved”, I mean that no one has found an easy way to get the right solution. In the worst case you might have to try all 512 possibilities for assigning the sexes before you find the right answer. This problem is equivalent to the computer science problem known as "3SAT", and computer scientists call problems of this type NP-complete. These problems have been studied for almost 50 years, and no one has been able to find an efficient solution (for example, a solution that required you to look at each tribe only once or twice). Computer scientists do not believe there will ever be efficient solutions to NP-complete problems, but in almost 50 years of trying, no one has been able to prove that either. In fact, this has long been one of the ten most important unsolved problems in mathematics. (You can read more about this in this Wikipedia article.)

So, if you confound the experts and find an efficient way to win this game, you will be world-famous. In addition, and this is truly amazing, your solution could be used to solve a whole host of other important problems that on the surface seem very different. For example, there is the Traveling Salesman Problem: you have a list of N cities, a list of the airfares between each two, and a budget of $M, can you find a tour such that you can visit every city once and still stay within budget? Or, the Bin Packing Problem: you are going to visit your grandkids and you have N suitcases and M Christmas presents, is there a way you can fit them all in your suitcases? No one knows an efficient way to solve these problems, but you can look up in a textbook to find out how to take your solution to the Land of Boole, make a few changes, and use it to solve these other NP-complete problems—hence the word “complete” in NP-complete. In addition, your solution would prove that every key-based encryption system in the world could be broken. Since that would lead to the collapse of the global banking system, I probably shouldn't wish you luck.

If you play with this, you will find that the so-called “greedy” approach will sometimes work. It goes like this: pick an erupting island and pick a tribe on that island that causes the fewest new eruptions when you click to switch the tribe’s sexes. Then repeat the process with a new erupting island. This will get you to a solution—sometimes. Other times you get into a loop, and the only way to find a solution is to start out making things worse before you start trying to improve it. (By the way, the minimum number of clicks required is always five.) I hope computer science students might find this game illuminating, and for the rest of you, I hope this is fun enough.

Click on this button to launch the game: