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 RRRRRRRAlas, 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?

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 =

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

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 12But 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 508. 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.)