Alien Tiles Reader Comments
The biggest challenges for Alien Tiles involve experiments with different-sized
playing boards and the creation of special target patterns. What targets
can and can't you create?
There is a 14 click solution to change an all-red 7x7 board to an all-blue 7x7
board. You can write to
Cliff Pickover
if you find the solution.
More clicks are needed to
change the tiles to all purple or all green starting from red.
From Suzy F.:
I am a seventh grade teacher, and I had my students look at
Alien Tiles. We were wondering if it is possible to form
an array with a single blue tile in the center of a red
background, like this:
RRRRRRR
RRRRRRR
RRRRRRR
RRRBRRR
RRRRRRR
RRRRRRR
RRRRRRR
We tried to create this but were not successful. Can you create a target
with a single spot of different color anywhere? P.S. We love
your web site.
From April P.:
Alien tiles is a vivdly stunning puzzle, resembling a Rubik's Cube from
another dimension! For those of us who are not mathematically inclined, it
is fun just to click randomly on tiles to see the colorful patterns. May
inquiring minds everywhere have a blast unlocking its secrets! - April
From Brian N.:
I'm working with a team of friends who have decided to
devote an hour each week studying your Alien Tiles. One friend
has made it his life's mission to create an "onion" pattern
with different colors for each concentric layer:
RRRRRRR
RGGGGGR
RGBBBGR
RGBPBGR
RGBBBGR
RGGGGGR
RRRRRRR
Alas, I think my friend will die of old age before he ever creates
his beloved onion structure. I was thinking of offering
a $100 award to anyone who creates the onion! Will you offer
any rewards?
From Melissa M.: A math question for you... How many different
possible boards are there for a 7x7 board? Of these, do you
think more than 50% can be actually realized starting from
a red screen?
From Kent B.:
Try this when you do a replay for the 7x7 board.
1. Highlight the text below with a mouse.
2. On Windows, do Control-C for copy.
3. Click in the Playback field.
4. On Windows, do Control-A to highlight any text that is already there.
5. Do Control-V to Paste the text into the rectangle.
6. Select "Replay"
Isn't the final pattern awesome?
s0|0|0|1|1|2|2|3|3|4|4|5|5|6|6|6|0|5|1|4|2|3|3|2|4|1|5|0|6|0|0|1|1|2|2|3|3|4|4|5|5|6|6|6|0|5|1|4|2|3|3|2|4|1|5|0|6|1|0|0|1|0|5|1|6|5|6|6|5|6|1|5|0|3|1|2|2|1|3|2|4|3|5|4|4|5|3|4|2|2|2|4|2|4|4|2|4|3|3|
From
Zoran Sunik:
What is the minimal (known) number of moves needed to obtain a
chessboard pattern in two colors?
Outrageous Ramblings for Mathematical Junkies:
Eswar Sivaraman was the first person on Earth to
create a 4x4 xenoplastic blue diamond in an otherwise red 7x7 array. First he created it in 42 moves,
and then he later discovered he could create the same diamond in only 26 moves.
Is this the least number of moves needed? What other colored diamonds can be created?
Glenn Rhoads asserts that all configurations of alien tiles
are achievable on an even-order board. However, he says that some configurations are not
achievable on an odd-order board.
Also note that every *solvable* position has a solution requiring less than or equal to
3*N^2 moves. For even-order boards, every position has a *unique*
solution with <= 3*N^2 moves.
Harry J. Smith asserts that
the order of the moves (clicks) is irrelevant. For a given set of moves, they can be done
in any order with the same result. Also, if in a given set of moves, the same square has been selected more
than three times, the selections of that square can be reduced by 4 times with the same result.
From this we see that there is at most 3*N^2 moves for the solution of any pattern. When N is 7 (for the 7x7
board) this gives 147 moves max. The total number of configurations of a 7x7 board is 2^(4*7*7) = 2^196 =
100433627766186892221372630771322662657637687111424552206336.
The total number of unique
solutions is also 2^(4*7*7). Here a solution is a series of moves used to go from all red to another state. From
this we see that if we can find more than one unique solution for the same configuration, we have proven that
not all configurations have solutions.
Eswar Sivaraman provides a diagram showing one strategy for creating
an interesting pattern. Each move is a double
click, and the moves follow the order shown in the diagram. All points can be clicked in any order, and the order shown above is
just one example. Observe that each double-clicked point changes color an even number of times - the centre point changes
color twice (one double click), and so, the color changes from red to blue. Is this the shortest solution?
Glenn Rhoads says there is an error in Harry Smith's numbers. The formula for
the number of configurations and number of possible solutions
is 4^(N^2) (for N=7, this is 4^49 = (2^2)^49 = 2^98).
Also, note that for odd-order boards, Rhoads has found positions
with more than one solution (e.g. all red to all green) and
because of this, not all configurations are achievable on an
odd-order board. Regarding
Suzy F.'s question: Is it possible to reach all red except a
single blue tile in the center of a 7x7 board? The answer is
yes! Click on the central tile twice. Click on all other
tiles in the central row and column once. Click on all other
entries twice. This method can be used to cycle *any* tile forward by 2 colors
when N = 3 mod 4 (i.e. N is 1 less than a multiple of 4).
I don't know if it is possible or not when N = 1 mod 4 (i.e.
1 more than a multiple of 4). Regarding Melissa M.'s questions,
the first one has already been answered; there are 4^49 possible
positions. The answer to the second question is that at most
1/92 of the positions on an 7x7 board are reachable. More
generally, when N = 3 mod 4 (1 less than a multiple of 4),
the percentage of reachable positions is <= 1 / (2N^2-N+1).
For N=3, equality holds (i.e. precisely 1/16 of the positions
are reachable). I don't know if equality holds or not for larger
N. Also note that the percentage of reachable positions gets
arbitrarily small as N increases (for N=3 mod 4).
Rhoads has simple proofs of these facts.
Glenn Rhoads comments about challenges that require the player to
make a board all have the same color tiles.
All red is always achievable (duh!).
Suppose the board is NxN.
case 1: N = 1 mod 4. All colors are achievable.
case 2: N = 3 mod 4. Blue is the only achievable color (besides red).
case 3: N = 0 mod 4 OR N = 2 mod 4. No color (besides red) is
achievable.
Interestingly, when a solution exists, you can always find it as
follows. Pick a row or column. Click all entries of that row
except 1 x times. Click the remaining entry y times. x and y
satisfy the following modular equations. Let c be the target
color -- red <==> c = 0, green <==> c = 1, blue <==> c = 2,
purple <==> c = 3.
x = c mod 4;
y = c mod 4;
(N-1)y = 0 mod 4.
Let x = c and find the minimal solution for y.
It's not hard to see that this yields solutions for the above
mentioned cases. Using a similar modular argument shows that
there are no other solutions. I didn't bother writing up
proofs. Other board sizes and target colors are achievable but require
different solution methods.
Solving other target patterns has to be handled on a case by
case basis. Solving for a particular pattern may be rather
difficult. I'll let you worry about that!
I've now completed studied all square board sizes. All
board sizes are solvable for any target color.
Case 1: N odd. Click on every tile once. This achieves all green.
Repeating this cycles the colors red -> green -> blue -> purple -> red.
Case 2: N even. Same method but now the colors cycle through
red -> purple -> blue -> green -> red.
Note: my previous solution method uses less clicks when it works
(I suspect it is optimal).F
Chris Worrell: As others have noted, all even boards are solvable.
Using a straightforward encoding
0 - red;
1 - green;
2 - blue;
3 - purple;
look at the individual sum (modulus 4) of each row and column.
For 4K+3 boards, all sums must be odd, or all sums must be even.
For 4K+1 boards, all sums must be the same.
This shows that your "Second Goal" and someone else's
"Onion Pattern" are both impossible.
For N=4K+3 boards 1/2^(2N-2) boards are possible.
For N=4K+1 boards 1/4^(2N-2) boards are possible.
Specifically, on a 7x7 board exactly 1/2^12 boards are possible.Alien Tiles is also interesting because as the board size is increased
by 4 the analysis can be extended by anology rather than needing new
calculations.
Hmmmmm.....
Does this mean that my solution method for square boards can be
used on non-square boards whose dimensions only differ by multiples
of 4? (say 3 x 7 )
Do other non-square boards (say 3 x 4) extend in the same way or
are they more complicated?
From Werner Nickel:
Instead of using 4 colours, we can use the numbers 0,1,2,3. The move
that corresponds to a particular square on the board adds 1 (modulo
4) to each square in the corresponding row and column. If we arrange
the rows of the board in a line, we can think of each move as a vector
with 1s in certain positions. Applying the move means adding the
corresponding vector (modulo 4) to the current position. As you know,
the order of moves does not matter, therefore we end up with a
lattice (or abelian group) generated by the NxN moves of an NxN
square. The question whether a certain position can be obtained from
the all red state is to ask whether the vector corresponding to that
position lies in that abelian group. For this question constructive
methods from linear algebra are available. The decide whether the
vector is in the lattice and write it as a sum of the NxN generators.
What questions might I pose in the future that will be difficult yet
interesting for a general audience?
For someone without much of a mathematical background, Devil's Target
is likely to be a challenge. Much harder might be asking for a
minimal solution. Although at this stage I can't say whether a
straight forward brute force approach might be able to solve this for
moderate board sizes. Asking for a pattern that requires a
maximal number is an interesting question, but I have no idea how to
tackle that. Incidentally, this still an open question for Rubik's
cube.
From Glenn Rhoads: I have conducted additional in-depth studies of
Alien tiles for
odd-order boards.
For N = 1 mod 4: there are 4^(N^2-2N+2) achievable positions.
The fraction of achievable positions is 1 / 4^(2n-2)
For N = 3 mod 4: there are 4^(N^2-N+1) achievable positions.
The fraction of achievable positions is 1 / 4^(n-1)
This means that for N = 7, the fraction of achievable positions
is 1 / 4^6 = 1 / 4096. Or if you prefer odds, for a random
position the odds are 4095:1 against it being solvable.
Solution algorithms below.
The chain of reasoning (without the proofs).
Case: N = 1 mod 4.
Definition: A Quarter Identity (QI) is a pattern of clicks where
each tile in a row or column is clicked once.
Fact: A QI advances each tile on the board once.
Thus, any number X QIs where X is a multiple of 4 is an identity
transformation.
Fact: There are 4^2N distinct ways of selecting QIs (since we need
consider only "short" solutions)
Fact: The number of identities achievable by composing QIs is
4^(2N-2) (since 1/4 of the ways of selecting distinct QIs is an
identy and since these selections count each identity 4 times.)
Thm 1: A pattern of clicks is an identity transformation if and only
if it is composed of X QIs where X is a multiple of 4.
Corollary: The number of identity transformations is 4^(2N-2)
Corollary: Thus the number of solvable positions is
4^(N^2) / 4^(2N-2) = 4^(N^2-2N+2)
Solution Method when N=1 mod 4
>From the above, once we fix all but 2n-2 = 2(n-1) entries,
these final entries will be in fact completely determined.
Consider the even-order square submatrix 1..N-1 X 1..N-1.
We can fix this submatrix any way we like by using the solution
algorithm for the 0 mod 4 case. Once we've fixed this, we can
also independently fix entry N,N. This fixes everything except
2(N-1) entries in row N and column N. But from the above
observation these entries will be uniquely determined and thus
we have solved the puzzle.
Case: N = 3 mod 4
definition: A "HI" (Half Identity) is any of the 2N patterns of clicks
where each element in a row or column is clicked twice.
Fact: A HI advances each tile on the board forward by two colors.
Thus, any number X QIs where X is a multiple of 2 is an identity
transformation.
Fact: There are 2^2N distinct ways of selecting HIs (since we need
consider only "short" solutions)
Fact: The number of identities achievable by composing HIs is
2^(2N-2) (since 1/2 of the ways of selecting distinct HIs is an
identy and since these selections count each identity 2 times.)
Thm 2: A pattern of clicks is an identity transformation if and only
if it is composed of X HIs where X is a multiple of 2.
Corollary: The number of identity transformations is 2^(2N-2) =
4^(N-1)
Corollary: Thus, the number of solvable positions is
4^(N^2) / 4^(N-1) = 4^(N^2-N+1)
Algorithm for solving NxN when N=3 mod 4
I'll use numbers 0,1,2,3 for the colors.
We can independently move any tile forward by two.
So any achievable configuration can be uniquely composed
from an achievable pattern of 0s and 1s followed by cycling
some subset of tiles forward by 2 each.
Consider the even-order square submatrix 1..N-1 X 1..N-1.
We can fix this into any pattern of 0s and 1s we like by using the
solution algorithm for the even-order case. Once we've fixed this,
we can also independently fix a 0 or 1 in entry N,N. Then we can
cycle any subset of the N^2 tile forward by 2. The number of
patterns achievable by this method is
2^[(n-1)^2] * 2 * 2^(n^2) = 2^(2n^2-2n+2) = (2^2)^(n^2-n+1) =
4^(n^2-n+1)
which from the above is the total number of achievable positions.
Thus, this constitutes a solution method (i.e. the remaining
pattern of 0s and 1s that we did not fixed is uniquely
determined and hence must be set correctly as well).
Credits:
Dennis Yelle -- For everything in the N=1 mod 4 except the proof
of theorem 1 (which he conjectured) and the solution algorithm.
The idea that all identities could be composed from QIs was of
critical importance in resolving the odd-order boards.
Nis Jorgensen -- For the original proof of theorem 1 (he
actually mistated the proof but he had correct reasoning).
Me -- The algorithm for N=1 mod 4 and all of the N=3 mod 4
case (which closely parallels the N=1 mod 4 case.
For reference: All solvable positions can be solved by composing
the following 3 transformations.
To cycle a tile 1 forward in a (sub)matrix of size 0 mod 4
Ex)
2221;
2221;
2221;
1113;
To cycle a tile 1 forward in a (sub)matrix of size 2 mod 4
Ex)
222223;
222223;
222223;
222223;
333333;
To cycle a tile 2 forward when N=3 mod 4
Ex)
221;
221;
112;
The effected tile in each example is the one in the lower-right
corner. You can use the same patterns to cycle any given tile
and these patterns generalize to larger boards in the obvious way.
Note that the solution method and the above 3 basic transformations
give you a way to describe whether a given position is achievable
but the condition is not particularly simple.
ex)
Let M be a 7x7 matrix of colors.
Use 0 for red, 1 for green, 2 for blue, 3 for purple.
The parity of a "color" is either even or odd.
Break M up into the 6x6 upper-left submatrix, M', location M77,
and two rectangles containing the 7'th row and column except (7,7)
Thm. M is reachable iff the following two conditions hold
(I) For every element M7j in the 7'th row rectangle,
The parity of M7j = the parity of
[the sum of those elements in M' not in column j + M77];
(II) For every element Mi7 in the 7'th column rectangle,
The parity of Mi7 = the parity of
[the sum of those elements in M' not in row i + M77].
The puzzle could be extended to the MxN matrices and to different
numbers of colors. But I'm not inclined to do that (note that
solution to the even-ordered square board extends to all MxN where
both M and N are even).
One final note: I'll offer a $1,000,000 reward for anybody who
can solve the "onion pattern" given in Brian M.'s email message.
(you can verify that the given pattern doesn't satisfy the
conditions of the theorem above).
Most humans have extreme difficulty
solving the various Alien Tiles questions without the aid of a computer.
It would be fascinating to see if there is something special with the brains
of people able to create the target patterns. Does this ability correlate with
other special talents?
Although unanswered questions still exist, a detailed mathematical analysis
is given here at the
Alien Tile Analysis Center, located in New Jersey.
-- Glenn C. Rhoads
Elizabeth Analysis
Elizabeth is 22 and studying genetics at the University of Western
Australia. She is interested in science, mathematics, art, music, language, in
fact almost everything. If there was only there was enough time to do
everything!
This is just a few thoughts on methods of creating target patterns on the 7x7
board. Probably other people have already worked all this out, but as I know
only a little mathematics, I can't understand most of what they have written.
But I think the alien tiles are lots of fun so I thought I'd send this anyway,
perhaps less mathematical people will be interested.
First of all the basics:
1. As others point out, the order in which you click on tiles is irrelevant.
2. Clicking on every tile once moves each tile on the board forward one colour
(eg red to green or blue to purple). This is because every tile gets its colour
changed 13 times which is 3 multiples of 4 (so three times back to its original
colour) plus 1, giving it the next colour in the sequence. By repeating this
you can get any of the four solid colours.
3. Clicking twice on all the tiles in a single row or column moves every tile
on the board forward two colours (eg red to blue or green to purple).
4. You can change any single tile on the board by two colours relative to
the "background" (all the rest of the tiles), eg a blue background with a
single red tile. You do this by clicking on all the tiles in the row and column
of the "chosen" tile, except the chosen tile itself, which recieves 0 clicks.
This actually makes the chosen tile stay the same colour, while all the other
tiles on the board change by two colours. So starting with all red, you would
get a blue background with a single red tile, and vice versa. Starting with all
green you would get a purple background with a single green tile and vice versa.
Ok, now down to business:
Because of points 3 and 4, and because there are four colours, the colours form
two pairs: the green/purple pair, and the red/blue pair. Its nice how each
pair are opposite colours in the spectrum.
You can repeat (4) with more tiles, to build up any design comprised of red and
blue, or comprised of green and purple. Each time you add another tile to
the "foreground", the design "inverts" (eg blue tiles on a red background
changes to red tiles on a blue background, or green tiles on a purple
background changes to purple tiles on a green background. In other words each
tile moves two colours).
You can easily invert your design by double clicking on a row or column (ie
blue changes to red, red changes to blue, purple changes to green and green
changes to purple). You can easily change a red/blue design to a green/purple
design (or vice versa) by clicking once on every tile.
But you are always stuck within the blue/red or purple/green combinations.
5. If the design contains a lot of foreground tiles, you may end up clicking on
some tiles more than three times. As others have pointed out, this is
redundant. If you mark out on a grid all the moves you make as you create the
design, you can then remove this redundancy to create a shorter pathway to your
design. Any group of four clicks on a tile can be removed from the grid.
You can use points 2 and 3 to increase the redundancy, and actually shorten the
solution. Eg changing to the other colour pair (by clicking once on each tile)
may create many groups of four clicks, which you can then elimenate. Point 3 is
usually more useful. Adding two clicks to all tiles in a row or column often
shortens the solution. Each time you do this the design inverts (as described
above), so as long as you do it an even number of times, you can keep the exact
colours you want.
Using the above methods, you can create Zoran Suniks chessboard pattern in
red/blue in 56 moves, and in purple/green in 57 moves.
You can also get a red/blue xenoplastic diamond in 22 moves, rather than the
previously reported 26:
0 0 2 0 2 0 0
0 0 0 0 0 0 0
0 2 0 0 0 2 0
0 0 2 2 2 0 0
0 2 0 0 0 2 0
0 0 0 0 0 0 0
0 0 2 0 2 0 0
(the above represents the 7x7 alien tile board with numbers showing the number
of times to click on each tile)
Eswar Sivaraman's 26 move diamond actually simplifies down to exactly the above
solution when you mark it out on a grid, and use (3) to shorten it.
6. You can create a pattern of purple/green against red/blue, that is both
vertically and horizontally symetrical, and that does not include tiles in the
central row or column. Put another way, think of there being only two colours;
purple/green and red/blue. One colour makes up the "pattern" which must be
bisymmetrical and confined to the four (3x3 tile) corner blocks of nine tiles.
The other colour is the "background" (the rest of the tiles on the board). Eg,
the following would be fine:
PG PG RB RB RB PG PG
RB PG PG RB PG PG RB
RB PG RB RB RB PG RB
RB RB RB RB RB RB RB
RB PG RB RB RB PG RB
RB PG PG RB PG PG RB
PG PG RB RB RB PG PG
(RB=red/blue and PG=purple/green)
You make the pattern by clicking on all the tiles to be part of the pattern
(click on them in all four of the nine-tile corner blocks). The "pattern" tiles
will now all be green or purple, and the rest of the tiles red or blue. You can
switch to a red/blue pattern on purple/green background by clicking on all
tiles once.
Once you have this basic pattern, you can then change any individual tile to
the other colour in its pair (by clicking on its row and column tiles but not
the chosen tile itself). Each time you do this to a tile, the whole pattern
inverts. So it alternates between two inverse states with each tile change.
This is because, as described in (4), the tile you are "changing" actually
stays the same colour while everything else changes by two colours (ok, maybe
my terminology is somewhat flawed!) Provided you focus on one of the two
inverse states as the "correct" state, and pick tiles to change based on their
colour when in the correct state, all will be well. This means that when the
pattern is in the "incorrect/inverse" state, you actually have to pick a tile
to change that is already the right colour (because it will retain this desired
colour while everything else changes back to "correct" state). If you get
confused you can always just double click a row or column to get the whole
thing back to the "correct" state.
If you need to change an odd number of tiles, the design will be in its
inverted ("incorrect") state when you finish. Just double click a row or column
to invert it back again.
7. I used the above methods to solve some of the alien tile puzzles on the
website.
The xenoplastic diamond pattern can be made using the method in (6). It is
therefore possible to create a xenoplastic diamond in any colour combination.
You can create all the goal 4 patterns in this way, and also the devils target.
Eg the devil's target; all tiles purple/green except for the "pattern" of 8 red
tiles which fall into a bisymmetrical design confined to the nine-tile corner
blocks. SO, starting from a red background:
a) Click on the 8 tiles to be red.
You now have 8 purple tiles on a red/blue background.
b) Click on all tiles once to advance al tiles one colour, switching to red
tiles on a purple/green background.
c) Many of the purple and green are not right, so change them by clicking on
their row and column.
This simplifies down to:
0 0 3 0 3 0 0
0 2 2 1 2 2 0
3 2 1 2 1 2 3
0 1 2 1 2 1 0
3 2 1 2 1 2 3
0 2 2 1 2 2 0
0 0 3 0 3 0 0
(the number of times to click on each tile)
d) Add two clicks to rows 3 and 5 and columns 3 and 5 to shorten the solution
(this is an even number of times so maintains the right colours):
0 0 1 0 1 0 0
0 2 0 1 0 2 0
1 0 1 0 1 0 1
0 1 0 1 0 1 0
1 0 1 0 1 0 1
0 2 0 1 0 2 0
0 0 1 0 1 0 0
(25 moves)
Using these strategies I can reach the goal 4 patterns Bazuluk, Shenkursk,
Vologda, Orel and Sharya in a number of moves equal to or less than those
stated on the website:
stated no. moves on web no. moves I took
Bazuluk 37 12
Shenkursk 50 34
Vologda 34 34
Orel 61 42
Sharya 12 12
But I took more than the stated number of moves for the Novomosk and Charon:
stated no. moves on web no. moves I took
Novomosk 22 28
Charon 19 50
8. So there must be other tricks to get shorter solutions. I dont know whether
the methods I described here will sometimes result in the optimal solution, and
if they do, how to tell whether the solution for a particular target pattern is
optimal or not. Also, you can obviously create all kinds of other designs, but
I dont know how to deliberately create them. I suspect there are tricks
involving clicking on diagonal rows, but I havent worked it out yet.
9. Yes, these methods of creating patterns and then shortening them are rather
laborious. I dont know if there are short cuts you could take to get to the
shorter solutions more directly.
Has anyone else sent you things along these lines? If so I would be very
interested in reading them.
Elizabeth
Return to Alien Tiles Main Page
(Cartoon image by Brian Mansfield.)