Maze of Life - World domination

One of the earliest yet most difficult challenges to date has been that of world domination. From an arbitrary start, such asY-start, is it possible to clear the board leaving the blue-cell the last and only cell left alive?



World domination is possible, but it took a computer search to prove it, find out more below. Alternatively discover world domination for yourself using this mini-challenge:

Find: world-domination in 4 moves
Note: this challenge has been pre-loaded for you, just click on the grid to move the blue cell.

Sorry, this is a Java applet.

Click on Edit to set up a start position.
Click on Play to switch to play mode or to restart.
Use Undo/redo to replay previous moves (play mode only).
Click on Load to verify and rerun the move sequence in the text box (play mode only).

In Edit mode click on the grid to toggle cell status (black/blue/empty).
In Play mode click on the grid to move.

u – undo last move.


For many months world domination remained an unsolved challange, but in March 2001 Jacco Compier proved by computer search that world domination was possible, in as little as 15 moves. A convincing vindication that world domination is probably possible from almost any start-state that the blue-cell can 'escape' from. Here is a selection of the shortest known solutions for world-domination from Y-start. x,y indicates the final resting place of the blue-cell.

 Solution  Length  x,y
 USS\D\UD/SSS>SD  15  4,3
 SS<U<D>U<SSSU/D>\UD  19  3,6
 SS<U<DS/D/</S<UL\/R  19  3,3
 SS<U<DURSLSRS//D\>D  19  5,5
 SS<U<DURUR/<LS>\SD  18  3,5

And here are some slightly longer solutions that all end with the blue-cell back in the centre (4,4).


All these solutions are of course edge-dependent, which is true for many of the challenges posed and solved so far, but having proved world-domination is possible in as few as 15 moves, it is particularly tempting to ask... is world-domination also possible on an infinite board? And if so, what is the minimum size board?

We have shown it is possible for the blue-cell to manouvre itself into the tiniest one-cell state, but one-cell is never going to survive by itself. What is the smallest, indefinitely survivable, state for the blue-cell? Is it those two 4-cell stable-states 4a and 4b we've already seen? No. If the blue-cell is prepared to retire to an oscillator, rather than a stable-state, the minimum is actually 3 cells. If you a familiar with Game of Life, you probably know the 3-cell, 2-step, oscillator I refer too, but can the blue-cell retire to it from Y-start? I feel sure the answer is yes - but I do not know the shortest solution.

Carl Hoff stumbled on several oscillators in his early search for stable-states and we began to collect examples of a brand new type of oscillator which is unique to intelligent-cell life. To find out more see the page on active oscillators.

iLife pages: Maze of life V1 World domination Optimal sequences (new)
  The Y-start challenge Active oscillators Glider gun in 247 (new)
  Stable-state goals Riding the glider iLife play area
  Dense goals  Building a glider gun

material - Andrea Gilbert, Carl Hoff, Jacco Compier
applet - © Andrea Gilbert 2000-2002