Enigmatic Code

Programming Enigma Puzzles

Enigma 133: Are you positive?

From New Scientist #1277, 29th October 1981 [link]

Enigma 133

On a 3-by-3 array like the one shown, I have coloured some of the little squares black and left the rest white. The four 2-by-2 corners of my pattern look like:

Enigma 133

These are not necessarily the right way up and some, unfortunately, may be the negatives of what they should be. Sorry! But if I told you the colour of the middle square in the top row of my pattern and I told you the number of black squares in my pattern, then you’d be able to work out my pattern (the right way up too!).

Find my pattern, or the negative of it, whichever takes less shading.

Note: As stated I don’t think this problem has any solutions, but it is possible to add reasonable extra conditions to the problem in order to give a unique solution.

[enigma133]

Advertisements

One response to “Enigma 133: Are you positive?

  1. Jim Randell 8 October 2013 at 10:07 am

    I’ve marked this puzzle as flawed, as given the most reasonable interpretation of the problem there are no patterns and orientations uniquely determined by the colour of the top middle square and the number of black squares.

    However, it’s not unsalvageable, as we can add the following extra conditions to come up with a problem that has a unique solution. The first extra condition is to interpret the phrase “These are not necessarily the right way up” to mean “Some of the squares may be shown upside-down” (but not rotated by ±90°). The second extra condition is to consider that the 2×2 squares are presented in the following order NW, NE, SW, SE.

    These seem to be reasonable assumptions to solve the problem, as if we were allowed arbitrary rotations and permutations of the smaller squares (without considering the possibility that they might be negatives) then any pattern that gives a solution would also give solutions for the three other rotations of the 3×3 square, which would stop you being able to uniquely identify a solution (unless the solution has rotational symmetry).

    This Python program takes these additional conditions into account, and finds the solution. It runs in 36ms.

    from itertools import product
    from collections import defaultdict
    from enigma import printf
    
    # if the 3x3 square is:
    #
    #  a b c
    #  d e f
    #  g h i
    #
    # then the 2x2 corners are:
    def corners(a, b, c, d, e, f, g, h, i):
      return (
        (a, b, d, e),
        (b, c, e, f),
        (d, e, g, h),
        (e, f, h, i)
      )
    
    # the rotations of a 2x2 square are:
    def rotations(a, b, c, d):
      return (
       # rotations
       (a, b, c, d),
       (d, c, b, a),
      )
    
    # the negative of a grid is:
    def negative(*g):
      return tuple(x ^ 1 for x in g)
    
    # the given squares
    sqs = [ (0, 1, 0, 1), (0, 1, 0, 1), (1, 0, 1, 0), (0, 1, 0, 0) ]
    
    # in their various orientations and negatives
    squares = []
    for sq in sqs:
      s = set(rotations(*sq))
      s.update(list(negative(*g) for g in s))
      squares.append(s)
    
    # record results by the colour of the top middle square and the
    # count of black squares
    r = defaultdict(list)
    
    # consider possible colourings of the 3x3 grid
    for s in product((0, 1), repeat=9):
      # extract the corners from it
      cs = corners(*s)
      # these need to match the given squares (in order)
      if all(c in s for (c, s) in zip(cs, squares)):
        r[(s[1], s.count(1))].append(s)
    
    # look for uniquely identified values
    for (k, v) in r.items():
      if len(v) != 1: continue
      printf("top middle = {k[0]}, blacks = {k[1]}, pattern = {v[0]}")
    

    Solution: The original 3×3 pattern (or the negative of it) is shown below:

    Enigma 133 - Solution

    Of course, two solutions are found. One being the negative of the other. We are asked to give the pattern that requires the least shading.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: