Sunday Times Brainteaser – Noughts and Crosses

by BRG on November 29, 2021

by Miss W. M. Jeffree

Published 23rd December 1956 (link)

Each square is to be occupied by either a zero or a cross, which stands for one particular digit which you may discover for yourself.

No row or column begins with a zero.

The following clues give the prime factors of the various rows and columns, each letter representing a different prime:

Rows:

(i)	a b c d
(ii)	a² b² e f
(iii)	a b² g h
(iv)	a b i j² k
(v)	a² b e j l
(vi)	a b² i k m

Columns:

(i)	a b² i j k m
(ii)	a² b e i j² k
(iii)	a b² m n p
(iv)	a² b c d e
(v)	a b i j k l

From → Uncategorized

3 Comments Leave one →

Brian Gladman permalink

This teaser provided a nice exercise in using the new pattern matching facility introduced in Python 10. It also uses my number theory library (see here)


from itertools import permutations, product
from collections import defaultdict
from number_theory import factor

# consider the digit involved
for x in range(1, 10):
  
  # the first row (no zeros) format: a.b.c.d
  fr1 = factor(11111 * x)
  pr1, er1 = zip(*fr1)
  if len(pr1) != 4 or set(er1) != {1}:
    continue
  
  # the first column format: a.b^2.i.j.k.m
  fc1 = factor(111111 * x)
  pc1, ec1 = zip(*fc1)
  if len(pc1) != 6 or sorted(ec1) != [1, 1, 1, 1, 1, 2]: 
    continue
  
  # determine a and b from the first row and column formats
  b = pc1[ec1.index(2)]
  a = (set(pr1).intersection(pc1) - {b}).pop()
  
  # dictionaries mapping row formats to their factors
  rd = [defaultdict(list) for _ in range(6)]
  
  # consider all possible rows and their prime factors
  for r4 in product('0' + str(x), repeat=4):
    r5 = str(x) + ''.join(r4)
    f = factor(int(r5))
    
    # match the six given row formats (this relies on
    # <a> and <b> being the lowest prime factors used)
    match f:
      
      # first row format: a.b.c.d -> (c, d)
      case ((a, 1), (b, 1), (c, 1), (d, 1)):
        rd[0][r5].append((c, d))
        rd[0][r5].append((d, c))
      
      # second row format: a^2.b^2.e.f -> (e, f)
      case ((a, 2), (b, 2), (e, 1), (f, 1)):
        rd[1][r5].append((e, f))
        rd[1][r5].append((f, e))
      
      # third row format: a.b^2.g.h -> (g, h)
      case ((a, 1), (b, 2), (g, 1), (h, 1)):
        rd[2][r5].append((g, h))
        rd[2][r5].append((h, g))
      
      # fourth row format: a.b.i.j^2.k -> j, (i, k)
      case ((a, 1), (b, 1), (u, eu), (v, ev), (w, ew)):
        if sorted([eu, ev, ew]) == [1, 1, 2]:
          j = u if eu == 2 else v if ev == 2 else w
          ik = tuple({u, v, w} - {j})
          rd[3][r5].append((ik[0], j, ik[1]))
          rd[3][r5].append((ik[1], j, ik[0]))
          
      # fifth row format: a^2.b.e.j.l -> (e, j, l)
      case ((a, 2), (b, 1), (e, 1), (j, 1), (l, 1)):  
        rd[4][r5] = list(permutations((e, j, l)))
      
      # sixth row format: a.b^2.i.k.m -> (i, k, m)
      case ((a, 1), (b, 2), (i, 1), (k, 1), (m, 1)):
        rd[5][r5] = list(permutations((i, k, m)))
  
  sols = set()
  prms = set()
  # consider all possible arrangements of six rows
  for rows in product(*(rd[i].keys() for i in range(6))):
    
    # there are no zeros in the first row
    if set(rows[0]) != {str(x)}:
      continue
    # form the five columns
    cols = list(zip(*rows))
    icols = list(int(''.join(cols[i])) for i in range(5))
    
    # find all possible arrangements of the prime values ...
    for p6 in product(*(rd[i][rows[i]] for i in range(6))):
      (c, d), (e, f), (g, h), (i, j, k), (_e, _j, l), (_i, _k, m) = p6
      # ... and check that they are consistent
      if (e, i, j, k) == (_e, _i, _j, _k):
                          
        # use column three to assign primes n and p 
        # from the product of n and p
        np, r = divmod(icols[2], a * b ** 2 * m)
        fnp = factor(np)
        if not r and len(fnp) == 2:
          n, p = fnp[0][0], fnp[1][0]
          for n, p in ((n, p), (p, n)):
            
            # calculate the five column values from the known
            # primes and test for a match with those obtained
            # from the rows (column three check is redundant)
            icolp = [ a * b ** 2 * i * j * k * m, 
                      a ** 2 * b * e * i * j ** 2 * k,
                      a * b ** 2 * m * n * p,
                      a ** 2 * b * c * d * e,
                      a * b * i * j * k * l
                    ]
            if all(u == v for u, v in zip(icols, icolp)):
              
              # using prior knowledge of pairings
              pt = (a, b, (c, d), e, f, (g, h), j, (i, k), l, m, (n, p))
              sols.add(tuple(icols))
              prms.add(pt)

# output the columns and the prime values used
for s in sols:
  print(f"Columns: {s}; Primes:")
print(" a  b  (c   d  )  e  f    (g   h )  j   (i   k)  l    m   (n   p )")
for p in prms:
  print(p)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

from itertools import permutations, product

from collections import defaultdict

from number_theory import factor

# consider the digit involved

for x in range(1, 10):

# the first row (no zeros) format: a.b.c.d

fr1 = factor(11111 * x)

pr1, er1 = zip(*fr1)

if len(pr1) != 4 or set(er1) != {1}:

continue

# the first column format: a.b^2.i.j.k.m

fc1 = factor(111111 * x)

pc1, ec1 = zip(*fc1)

if len(pc1) != 6 or sorted(ec1) != [1, 1, 1, 1, 1, 2]:

continue

# determine a and b from the first row and column formats

b = pc1[ec1.index(2)]

a = (set(pr1).intersection(pc1) - {b}).pop()

# dictionaries mapping row formats to their factors

rd = [defaultdict(list) for _ in range(6)]

# consider all possible rows and their prime factors

for r4 in product('0' + str(x), repeat=4):

r5 = str(x) + ''.join(r4)

f = factor(int(r5))

# match the six given row formats (this relies on

# <a> and <b> being the lowest prime factors used)

match f:

# first row format: a.b.c.d -> (c, d)

case ((a, 1), (b, 1), (c, 1), (d, 1)):

rd[0][r5].append((c, d))

rd[0][r5].append((d, c))

# second row format: a^2.b^2.e.f -> (e, f)

case ((a, 2), (b, 2), (e, 1), (f, 1)):

rd[1][r5].append((e, f))

rd[1][r5].append((f, e))

# third row format: a.b^2.g.h -> (g, h)

case ((a, 1), (b, 2), (g, 1), (h, 1)):

rd[2][r5].append((g, h))

rd[2][r5].append((h, g))

# fourth row format: a.b.i.j^2.k -> j, (i, k)

case ((a, 1), (b, 1), (u, eu), (v, ev), (w, ew)):

if sorted([eu, ev, ew]) == [1, 1, 2]:

j = u if eu == 2 else v if ev == 2 else w

ik = tuple({u, v, w} - {j})

rd[3][r5].append((ik[0], j, ik[1]))

rd[3][r5].append((ik[1], j, ik[0]))

# fifth row format: a^2.b.e.j.l -> (e, j, l)

case ((a, 2), (b, 1), (e, 1), (j, 1), (l, 1)):

rd[4][r5] = list(permutations((e, j, l)))

# sixth row format: a.b^2.i.k.m -> (i, k, m)

case ((a, 1), (b, 2), (i, 1), (k, 1), (m, 1)):

rd[5][r5] = list(permutations((i, k, m)))

sols = set()

prms = set()

# consider all possible arrangements of six rows

for rows in product(*(rd[i].keys() for i in range(6))):

# there are no zeros in the first row

if set(rows[0]) != {str(x)}:

continue

# form the five columns

cols = list(zip(*rows))

icols = list(int(''.join(cols[i])) for i in range(5))

# find all possible arrangements of the prime values ...

for p6 in product(*(rd[i][rows[i]] for i in range(6))):

(c, d), (e, f), (g, h), (i, j, k), (_e, _j, l), (_i, _k, m) = p6

# ... and check that they are consistent

if (e, i, j, k) == (_e, _i, _j, _k):

# use column three to assign primes n and p

# from the product of n and p

np, r = divmod(icols[2], a * b ** 2 * m)

fnp = factor(np)

if not r and len(fnp) == 2:

n, p = fnp[0][0], fnp[1][0]

for n, p in ((n, p), (p, n)):

# calculate the five column values from the known

# primes and test for a match with those obtained

# from the rows (column three check is redundant)

icolp = [ a * b ** 2 * i * j * k * m,

a ** 2 * b * e * i * j ** 2 * k,

a * b ** 2 * m * n * p,

a ** 2 * b * c * d * e,

a * b * i * j * k * l

]

if all(u == v for u, v in zip(icols, icolp)):

# using prior knowledge of pairings

pt = (a, b, (c, d), e, f, (g, h), j, (i, k), l, m, (n, p))

sols.add(tuple(icols))

prms.add(pt)

# output the columns and the prime values used

for s in sols:

print(f"Columns: {s}; Primes:")

print(" a b (c d ) e f (g h ) j (i k) l m (n p )")

for p in prms:

print(p)

Frits permalink

Interesting.

– (iii) is not correct in the puzzle description.

– you don’t seem to use the early determination of a and b (nice idea to determine variable a from crossing first row and column).

– the check for no zeros in the first row could have been done earlier in the r4 loop (however, I know you like esthetically pleasing code).

– output is a bit confusing as it looks like n and p have fixed values where as you only know the value of n x p.

Reply
- Brian Gladman permalink
  
  Hi Frits
  
  Thanks for picking up the error in the description.
  
  I didn’t see an earlier way of determining a and b 🙁
  
  I agree that the zeros check could be done earlier but it doesn’t really fit neatly
  in the earlier loop.
  
  The n and p issue is annoying but the way these two are found is different and
  its not easy to show the order ambiguity (a more complex replacement for line
  96 might be possible).
  
  PS: I have now updated the code to display the ambiguity in n and p. I also found that the use of pattern matching in the column reconstruction was a considerable overkill and was slow when compared with the simpler approach I am now using. This got the run time down to 14 milliseconds from around 50 previously.
  
  Reply

Sunday Times Brainteaser – Noughts and Crosses

by Miss W. M. Jeffree

Published 23rd December 1956 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta