Sunday Times Teaser 3173 – Dots and Boxes

by BRG on July 19, 2023

by Susan Bricket

Published Sunday July 16 2023 (link)

In this game, two players take turns drawing a single horizontal or vertical line between two unjoined adjacent dots in a rectangular grid. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. The winner is the one with the most points at the end. A recent game with 4×4 dots (as above) between two beginners, reached a critical position when no box had more than two sides already drawn and the next player was forced to complete the third side of some box. It turned out that this was the shortest possible 4×4 game to reach a critical position. Their next 4×4 game reached a critical position in the largest possible number of turns.

How many turns were in each game?

From → Uncategorized

One Comment Leave one →

BRG permalink

Here is my first effort which is a bit slow:

from itertools import combinations

# number boxes (0..8) and lines (0..23) left to right and then from top to 
# bottom, mapping lines to the boxes for which they are a side
l2b = { 0:   (0,),  1:   (1,),  2:   (2,),  3:   (0,),  4: (0, 1),  5: (1, 2),
        6:   (2,),  7: (0, 3),  8: (1, 4),  9: (2, 5), 10:   (3,), 11: (3, 4),
       12: (4, 5), 13:   (5,), 14: (3, 6), 15: (4, 7), 16: (5, 8), 17:   (6,),
       18: (6, 7), 19: (7, 8), 20:   (8,), 21:   (6,), 22:   (7,), 23:   (8,) }

# look for solutions for numbers of filled lines in the range <r>
def solve(r):
  for nl in r:
    # consider the possible combinations of lines to be drawn
    for lns in combinations(l2b, nl):
      # find the number of drawn sides for each of the 9 boxes
      bx = [0] * 9
      for ln in lns:
        for b in l2b[ln]:
          bx[b] += 1
      # ensure that our opponent cannot complete a box
      if all(x <= 2 for x in bx):
        # but they cannot avoid making a three sided one
        for l in set(range(24)).difference(lns):
          bx_ = bx[:]
          for b in l2b[l]:
            bx_[b] += 1
          if not any(b == 3 for b in bx_):
            break
        else:
          yield nl, lns
      continue

# find the minimum and maximum length critical sequences
for nl, lns in solve(range(1, 9)):
  print(f"{nl + 2} {lns} + 2")
  break
for nl, lns in solve(range(24, 0, -1)):
  print(f"{nl + 2} {lns} + 2")
  break

from itertools import combinations

# number boxes (0..8) and lines (0..23) left to right and then from top to

# bottom, mapping lines to the boxes for which they are a side

l2b = { 0: (0,), 1: (1,), 2: (2,), 3: (0,), 4: (0, 1), 5: (1, 2),

6: (2,), 7: (0, 3), 8: (1, 4), 9: (2, 5), 10: (3,), 11: (3, 4),

12: (4, 5), 13: (5,), 14: (3, 6), 15: (4, 7), 16: (5, 8), 17: (6,),

18: (6, 7), 19: (7, 8), 20: (8,), 21: (6,), 22: (7,), 23: (8,) }

# look for solutions for numbers of filled lines in the range <r>

def solve(r):

for nl in r:

# consider the possible combinations of lines to be drawn

for lns in combinations(l2b, nl):

# find the number of drawn sides for each of the 9 boxes

bx = [0] * 9

for ln in lns:

for b in l2b[ln]:

bx[b] += 1

# ensure that our opponent cannot complete a box

if all(x <= 2 for x in bx):

# but they cannot avoid making a three sided one

for l in set(range(24)).difference(lns):

bx_ = bx[:]

for b in l2b[l]:

bx_[b] += 1

if not any(b == 3 for b in bx_):

break

else:

yield nl, lns

continue

# find the minimum and maximum length critical sequences

for nl, lns in solve(range(1, 9)):

print(f"{nl + 2} {lns} + 2")

break

for nl, lns in solve(range(24, 0, -1)):

print(f"{nl + 2} {lns} + 2")

break

A recursive solution is faster:

# try to add line <l_no> (0..23) while storing counts
# of the number of completed sides for the nine boxes
# in <side_cnts>[0..8] and the lines added in <l_seq>
def add_lines(l_no, side_cnts, l_seq=()):
  if l_no == 24:
    # remove all solutions that don't force the 
    # opponent to complete three sides of a box
    for l in set(range(24)).difference(l_seq):
      if all(side_cnts[b] < 2 for b in l2b[l]):
        return
    yield l_seq
  else:
    # try for solutions that include the current line but only if
    # we can do so without allowing the opponent to complete a box
    lbxs = l2b[l_no]
    if all(side_cnts[b] < 2 for b in lbxs):
      for b in lbxs:
        side_cnts[b] += 1
      yield from add_lines(l_no + 1, side_cnts, l_seq + (l_no,))
      for b in lbxs:
        side_cnts[b] -= 1
    # try for solutions that exclude the current line
    yield from add_lines(l_no + 1, side_cnts, l_seq)

# find the minimum and maximum length critical sequences
mn, mn_seq = 24, None
mx, mx_seq =  0, None
for s in add_lines(0, [0] * 9):
  if (m := len(s)) < mn:
    mn, mn_seq = m, s
  if (m := len(s)) > mx:
      mx, mx_seq = m, s
print(f"{mn + 2} {mn_seq} + 2")
print(f"{mx + 2} {mx_seq} + 2")

# number boxes (0..8) and lines (0..23) left to right and then from top to

# bottom, mapping lines to the boxes for which they are a side

l2b = { 0: (0,), 1: (1,), 2: (2,), 3: (0,), 4: (0, 1), 5: (1, 2),

6: (2,), 7: (0, 3), 8: (1, 4), 9: (2, 5), 10: (3,), 11: (3, 4),

12: (4, 5), 13: (5,), 14: (3, 6), 15: (4, 7), 16: (5, 8), 17: (6,),

18: (6, 7), 19: (7, 8), 20: (8,), 21: (6,), 22: (7,), 23: (8,) }

# try to add line <l_no> (0..23) while storing counts

# of the number of completed sides for the nine boxes

# in <side_cnts>[0..8] and the lines added in <l_seq>

def add_lines(l_no, side_cnts, l_seq=()):

if l_no == 24:

# remove all solutions that don't force the

# opponent to complete three sides of a box

for l in set(range(24)).difference(l_seq):

if all(side_cnts[b] < 2 for b in l2b[l]):

return

yield l_seq

else:

# try for solutions that include the current line but only if

# we can do so without allowing the opponent to complete a box

lbxs = l2b[l_no]

if all(side_cnts[b] < 2 for b in lbxs):

for b in lbxs:

side_cnts[b] += 1

yield from add_lines(l_no + 1, side_cnts, l_seq + (l_no,))

for b in lbxs:

side_cnts[b] -= 1

# try for solutions that exclude the current line

yield from add_lines(l_no + 1, side_cnts, l_seq)

# find the minimum and maximum length critical sequences

mn, mn_seq = 24, None

mx, mx_seq = 0, None

for s in add_lines(0, [0] * 9):

if (m := len(s)) < mn:

mn, mn_seq = m, s

if (m := len(s)) > mx:

mx, mx_seq = m, s

print(f"{mn + 2} {mn_seq} + 2")

print(f"{mx + 2} {mx_seq} + 2")

Sunday Times Teaser 3173 – Dots and Boxes

by Susan Bricket

Published Sunday July 16 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta