Enigmatic Code

Programming Enigma Puzzles

Enigma 973: Choss, anyone?

From New Scientist #2128, 4th April 1998 [link]

The game of choss is played by two players, Black and White, on a board of 6 × 6 squares. Each player has a number of pieces which he or she moves one square horizontally or vertically. The players take it in turns to move one of their own pieces. A piece cannot move into a square already occupied by a piece of the same colour. If a piece moves into a square occupied by a piece of the opposite colour, that the other piece is captured and removed from the board. One White piece is larger than the other pieces and is called the Target. Black wins by taking the Target.

The layout of the board is as shown and it is Black’s move. She can in fact definitely win in three or fewer moves.

1. What should the first of these moves be?

That was the Enigma that I intended to set, but the editor thought it was too easy. He suggested that I change the board layout above by moving the Target to some other unoccupied square where it cannot be immediately taken by Black, but so that from the new layout Black can again definitely win in three or fewer moves. He then suggested that I asked Question 1 about this new layout.

Of course I shall have to choose the new position of the Target so that Question 1 has a unique answer.

2. To which position should I move the Target?

[enigma973]

One response to “Enigma 973: Choss, anyone?

  1. Jim Randell 14 February 2020 at 8:19 am

    This Python program examines moves for black such that whatever response white makes black is guaranteed a win in three moves.

    To analyse all the situations required by the puzzle text takes it 900ms.

    Run: [ @repl.it ]

    from itertools import product
    from enigma import unpack, irange, printf
    
    # flags for pieces
    (B, W, T) = (0, 1, 2)
    colour = lambda p: p & 1
    target = lambda p: p & 2
    
    # initial board position
    board = {
      # white pieces
      (2, 0): W,
      (3, 0): W,
      (5, 5): W | T,
      # black pieces
      (1, 0): B,
      (1, 2): B,
      (3, 3): B,
      (3, 4): B,
      (3, 5): B,
      (4, 2): B,
      (5, 3): B,
    }
    
    # new board with p -> q
    def move(b, p, q):
      b = b.copy()
      b[q] = b.pop(p)
      return b
    
    # possible moves for player g
    # return (x, y) -> (x1, y1), <capture>
    def moves(b, g):
      # examine the board for pieces to move
      for ((x, y), p) in b.items():
        if colour(p) != g: continue
        # attempt to move the piece
        for (x1, y1) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
          if x1 < 0 or x1 > 5 or y1 < 0 or y1 > 5: continue
          # is there a piece in the target square?
          t = b.get((x1, y1))
          if t is None or colour(t) != g:
            yield ((x, y), (x1, y1), t)
    
    # black's strategy to play the game to win in k moves
    def playB(b, k):
      # no moves remaining
      if k == 0: return
      # collect possible moves
      m = 0
      ms = list()
      for (p, q, t) in moves(b, B):
        m += 1
        # if we take the target then we have won
        if t is not None and target(t):
          yield ((p, q), 1)
        else:
          ms.append((p, q, t))
      # if there are no possible moves, we have lost
      if m == 0: yield (None, 0)
      # otherwise consider possible responses to each move
      for (p, q, t) in ms:
        # make the move
        b1 = move(b, p, q)
        # look at the outcome of every possible white response
        f = True
        for (p1, q1, t1) in moves(b1, W):
          # make the response
          b2 = move(b1, p1, q1)
          # does that stop black from winning in k-1 moves?
          if not any(w2 == 1 for (_, w2) in playB(b2, k - 1)):
            f = False
            break
        # is it a guaranteed win for black?
        if f: yield ((p, q), 1)
    
    # format a position on the board
    fmt = unpack(lambda x, y: "abcdef"[x] + "123456"[y])
    
    # can black win in 3 (or fewer) moves?
    for ((p, q), w) in playB(board, 3):
      printf("(1) {p} -> {q}", p=fmt(p), q=fmt(q))
    
    # consider possible other positions for the target
    for t in product(irange(0, 5), repeat=2):
      if t in board: continue
      # make a new board
      b1 = move(board, (5, 5), t)
      # black cannot win in 1 move
      if any(playB(b1, 1)): continue
      # but black can win in 3 (or fewer) moves
      ws = list(playB(b1, 3))
      # with a unique first move
      if len(ws) == 1:
        for ((p, q), w) in ws:
          printf("(2) {t} [{p} -> {q}]", t=fmt(t), p=fmt(p), q=fmt(q))
    

    Solution: (1) Black’s first move should be d5 → e5. (2) The Target should be placed at d2.

    For (2), if black moves d4 → d3, then they guarantee a win in three moves.

    If the Target were placed at c2, then black could still guarantee a win in three moves, but there are two options for the initial move (b1 → b2, or: b3 → b2), so this is ruled out as a solution, as we require a single initial move for black.

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: