Fact and Fiction

Thoughts about a funny old world, and what is real, and what is not. Comments are welcome, but please keep them on topic.

Friday, February 09, 2007

Enigma variations

Am I the only one, or has anyone else noticed how a lot of the New Scientist brainteasers (in the Enigma section) appear to have been constructed so that they can be solved by brute force? In fact, brute force makes it very easy to construct a "brain" teaser in the first place, because all you need to do is to describe a largish (but not too large) ensemble of potential solutions (e.g. all possible n-by-n grids of digits), then state a set of conditions that a unique member of the ensemble has to satisfy, then ask the reader to find that unique member, and submit it as their solution to the "brain" teaser.

Enigma 1428 in the most recent New Scientist appears to belong to this category of "brain" teaser. Here it is:

Foursight. Enigma No. 1428

If you place a 1, 2, 3 or 4 in each of the sixteen places in this grid, with no digit repeated in any row or column, then you end up with a “Latin square”. Then you can read eight four-figure numbers in the grid, namely across each of the four rows and down each of the four columns. Your task today is to construct such a Latin square in which those eight numbers are all different, none is a prime, no two are reverses of each other, and:

1st column X 3rd column
-------------------------------
2nd row X 3rd row

is greater than 4.


The relatively small size of this problem, and the fact that it looks numerically messy, immediately suggested to me that it was designed on computer, and that the quickest way to get the correct result was a brute force computer attack. I got out my trusty Mathematica and did the following steps (inputs in bold), where I made abolutely no attempt to streamline the code, I generated each input by copying/pasting/modifying earlier inputs, and the goal was to get to the answer as quickly as possible. The code is not really intended to be read except by masochists; it is a special write-only style that I use for problems like this.

How many candidate Latin squares with all digits different in each single row?

4!^4

331776

Construct all possible single rows.

perms = Permutations[{1, 2, 3, 4}]

{{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,2,3},{1,4,3,2},{2,1,3,4},{2,1,4,3},{2,3,1,4},{2,3,4,1},{2,4,1,3},{2,4,3,1},{3,1,2,4},{3,1,4,2},{3,2,1,4},{3,2,4,1},{3,4,1,2},{3,4,2,1},{4,1,2,3},{4,1,3,2},{4,2,1,3},{4,2,3,1},{4,3,1,2},{4,3,2,1}}

Join together in all possible ways to make all possible candidate Latin squares.

perms2 = Flatten[Table[{perms[[i]], perms[[j]], perms[[k]], perms[[l]]}, {i, 24}, {j, 24}, {k, 24}, {l, 24}], 3];
Length[perms2]

331776

Keep only the ones in which each single column has all digits different. The rows already satisfy this condition.

perms3=Select[perms2,Apply[And,Map[Length[Union[#]]==4&,Transpose[#]]]&];
Length[perms3]

576

Keep only the ones in which all 8 rows and columns are different numbers.

perms4=Select[perms3,Length[Union[Map[FromDigits,Join[#,Transpose[#]]&[#]]]]==8&];
Length[perms4]

480

Keep only the ones in which none of the 8 rows and columns is prime.

perms5=Select[perms4,!Apply[Or,Map[PrimeQ[FromDigits[#]]&,Join[#,Transpose[#]]&[#]]]&];
Length[perms5]

88

Keep only the ones in which none of the 8 rows and columns is the reverse of another.

perms6=Select[perms5,Length[Union[Map[FromDigits,Join[#,Transpose[#],Map[Reverse,#],Map[Reverse,Transpose[#]]&[#]]]]]==16&];
Length[perms6]

24

Keep only the ones in which col 1 * col 3 / (row 2 * row 3) > 4.

perms7=Select[perms6,#[[5]]#[[7]]/(#[[2]]#[[3]])>4&[Map[FromDigits,Join[#,Transpose[#]]&[#]]]&];
Length[perms7]

1

The unique answer.

perms7[[1]]

{{3,2,4,1},{1,4,3,2},{2,3,1,4},{4,1,2,3}}

0 Comments:

Post a Comment

<< Home