Volume 7, Number 1, September 2006
An Alien IP
 
 
Martin J.Chlond
Lancashire Business School
University of Central Lancashire
Preston PR1 2HE
UK
 
 

1. Introduction

The 'Alien Tiles' game is taken from Clifford Pickover's website here. It consists of a 7x7 grid of colored cells, initially all red. Each time a cell is clicked then that cell and all cells in the same row and column cycle from red to green to blue to purple and back to red. The objective is to change the color of the entire grid to green, blue or purple. The following images depict the initial grid and then after a single click on row 3, column 2.


2. IP Formulation

It should be noted at his point that the number of clicks on any particular cell need not exceed 3 as the effective number of clicks on a cell is equal to the actual number of clicks modulo 4. Also, the order of the clicks is not important.

We number the colors as follows: red = 0, green = 1, blue = 2 and purple = 3.

If, for example, we wish to turn the entire grid from color 0 (red) to target color t = 2 (blue) then for each cell the number of times it is affected modulo 4 must be equal to 2.

To this end we define xi,j (with upper bound = 3) as the number of times cell {i,j} is clicked and di,j a dummy integer variable for each cell. Finally, we define the range N = 1..n where, in this case, n = 7.

The objective is to move from the start position to the target position in the minimum number of mouse clicks. This may be achieved as follows.

objfun.gif

Subject to:

con1.gif

The initial puzzles suggested by Pickover involve changing an all-red grid to all-green, all-blue or all-purple. He goes on to suggest various patterns that may be achieved from the all-red grid and also allows for a random start position. For a more general formulation which accomodates both of these features we define tables S and T, where si,j and ti,j are the start and target colors respectively for cell {i,j}, and amend the above constraints to the following.

con2.gif

An OPL model of this formulation is here. If the start and finish positions have top-bottom and left-right mirror symmetry then we may use symmetry elimination constraints to cut down the solution times and these are included in the OPL model provided. They need to be deleted if these symmetries do not exist in the particular puzzle under consideration. Also, an Excel spreadsheet with Solver instructions for a 4x4 version of the puzzle is here. The formulations are quite succinct and do not require large numbers of variables. They are, however, for some start and finish positions, surprisingly difficult to solve. Even the 4x4 version, in some cases, proves tricky for the Excel Solver.

The following 'Xenoplastic diamond' took almost two hours to solve using OPL on a P4.

The clicks required to produce this target position are:

The single color problems prove even more difficult and the writer was unable to find solutions for the 7x7 grid using the above model despite the fact that these may be solved by inspection (hint - consider what happens if you click once on every cell).


To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
To reference this paper, please use: 
Chlond, M. J. (2006), "An Alien IP," INFORMS Transactions on Education, Vol. 7, No 1,  http://ite.pubs.informs.org/Vol7No1/Chlond/