Enigmatic Code

Programming Enigma Puzzles

Enigma 1591: Pseudo coup

From New Scientist #2756, 17th April 2010 [link]

All Penny had to do this week was fill in the missing numbers so that each row, each column and each three-by-three square all had each of the numbers 1 to 9.

In printing out the puzzle Joe had interchanged some of the three-by-three squares.

Penny worked out which and filled in all the missing numbers.

What number did Penny place in the small shaded square?

[enigma1591]

Advertisements

2 responses to “Enigma 1591: Pseudo coup

  1. Jim Randell 23 January 2012 at 11:31 am

    I was thinking I might have to bring to bear my generic Sudoku solving code on this one, but it turns out that a simple elimination solver is sufficient.

    I first create a table of which squares are incompatible in a horizontal and vertical direction, and use this to reduce the possibilities from the rearrangement of the squares. The elimination solver is then unleashed on the composite Sudoku puzzle.

    The following Python program runs in 300ms.

    from itertools import permutations
    from enigma import irange, printf
    
    numbers = set(irange(1, 9))
    
    s = (
      (0, 6, 0, 8, 4, 0, 0, 0, 9),
      (0, 2, 0, 0, 3, 4, 8, 0, 0),
      (0, 9, 0, 2, 0, 6, 0, 5, 0),
      (0, 0, 3, 8, 5, 0, 0, 7, 0),
      (9, 8, 0, 0, 0, 0, 0, 7, 3),
      (0, 0, 7, 3, 0, 1, 5, 0, 0),
      (4, 6, 0, 0, 0, 0, 0, 3, 1),
      (0, 0, 4, 3, 0, 2, 6, 0, 0),
      (5, 0, 0, 0, 8, 4, 0, 7, 0)
    )
    
    # check each square for H(orizontal) and V(ertical) incompatibility
    H = [[0] * 9 for i in irange(0, 8)]
    V = [[0] * 9 for i in irange(0, 8)]
    for i in irange(0, 8):
      for j in irange(0, 8):
        if i == j: continue
        if numbers.intersection(s[i][0:3]).intersection(s[j][0:3]) or \
           numbers.intersection(s[i][3:6]).intersection(s[j][3:6]) or \
           numbers.intersection(s[i][3:6]).intersection(s[j][3:6]):
          H[i][j] = 1
        if numbers.intersection(s[i][0:9:3]).intersection(s[j][0:9:3]) or \
           numbers.intersection(s[i][1:9:3]).intersection(s[j][1:9:3]) or \
           numbers.intersection(s[i][2:9:3]).intersection(s[j][2:9:3]):
          V[i][j] = 1
    
    # now consider all the permutations
    for x in permutations(irange(0, 8), 9):
      # check for H incompatibilities
      if H[x[0]][x[1]] or H[x[0]][x[2]] or H[x[1]][x[2]]: continue
      if H[x[3]][x[4]] or H[x[3]][x[5]] or H[x[4]][x[5]]: continue
      if H[x[6]][x[7]] or H[x[6]][x[8]] or H[x[7]][x[8]]: continue
      # and V incompatibilities
      if V[x[0]][x[3]] or V[x[0]][x[6]] or V[x[3]][x[6]]: continue
      if V[x[1]][x[4]] or V[x[1]][x[7]] or V[x[4]][x[7]]: continue
      if V[x[2]][x[5]] or V[x[2]][x[8]] or V[x[5]][x[8]]: continue
    
      # OK, create a composite Sudoku from the squares
      p = (
        list(s[x[0]][0:3] + s[x[1]][0:3] + s[x[2]][0:3]),
        list(s[x[0]][3:6] + s[x[1]][3:6] + s[x[2]][3:6]),
        list(s[x[0]][6:9] + s[x[1]][6:9] + s[x[2]][6:9]),
        list(s[x[3]][0:3] + s[x[4]][0:3] + s[x[5]][0:3]),
        list(s[x[3]][3:6] + s[x[4]][3:6] + s[x[5]][3:6]),
        list(s[x[3]][6:9] + s[x[4]][6:9] + s[x[5]][6:9]),
        list(s[x[6]][0:3] + s[x[7]][0:3] + s[x[8]][0:3]),
        list(s[x[6]][3:6] + s[x[7]][3:6] + s[x[8]][3:6]),
        list(s[x[6]][6:9] + s[x[7]][6:9] + s[x[8]][6:9]),
      )
    
      # and solve it
      def solve(p):
        progress = False
        for i in irange(0, 8):
          a = 3 * (i // 3)
          for j in irange(0, 8):
            if p[i][j]: continue        
            b = 3 * (j // 3)
            x = numbers.difference(
              p[i], # row
              (p[x][j] for x in irange(0, 8)), # column
              (p[a][b], p[a+1][b], p[a+2][b], p[a+1][b], p[a+1][b+1], p[a+1][b+2], p[a+2][b], p[a+2][b+1], p[a+2][b+2]) # square
            )
            if len(x) > 1: continue
            p[i][j] = x.pop()
            progress = True
        return progress
    
      while solve(p):
        pass
    
      # and find the target square
      where = [(2, 0), (2, 3), (2, 6), (5, 0), (5, 3), (5, 6), (8, 0), (8, 3), (8, 6)]
      (a, b) = where[x.index(2)]
      printf("{x} => {p}", p=p[a][b])
    

    Solution: The shaded square contains the number 4.

  2. Hugh Casement 7 April 2016 at 2:26 pm

    I labelled the 3×3 squares A to I in order.  There are many arrangements that resolve the incompatibilities (for example, 4 occurs twice in the second row), but this one involves fewest moves, leaving five in position:
    D  B  C
    H  E  A
    G  F  I

    I admit I didn’t then check whether the sudoku as a whole has a solution, but solved only for square C (still at top right).

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: