Enigmatic Code

Programming Enigma Puzzles

Puzzle #173: Knight moves

From New Scientist #3392, 25th June 2022 [link] [link]

My son is obsessed with chess, and has been acting out the game’s moves everywhere we go, running like a bishop and jumping like a knight on tiled floors. He was tickled to see that on the number pad of my keyboard he could type 27 using a knight’s move, because the move from 2 to 7 is an L-shape, like a knight moves on a chessboard.

Alas, he can’t make 27 using a bishop move. Bishops move diagonally any number of spaces, so a bishop, using multiple moves, could make a number like 484 or 9157. In a similar fashion, a knight could make numbers such as 167 or 8349.

Yesterday, he made a happy discovery: a three-digit knight number that is exactly 27 more than a three-digit bishop number. (Actually, I found I could put another digit, call it “X”, at the front of my son’s numbers, and still have a knight number that is exactly 27 more than a bishop number).

What numbers did my son find?

[puzzle#173]

3 responses to “Puzzle #173: Knight moves

  1. Jim Randell 25 June 2022 at 9:46 am

    This Python program runs in 60ms. (Internal runtime is 211µs).

    Run: [ @replit ]

    from enigma import (nconcat, printf)
    
    # adjacency matrices for knight moves and bishop moves
    knight = {
      1: [6, 8],
      2: [7, 9],
      3: [4, 8],
      4: [3, 9],
      5: [],
      6: [1, 7],
      7: [2, 6],
      8: [1, 3],
      9: [2, 4],
    }
    
    bishop = {
      1: [5, 9],
      2: [4, 6],
      3: [5, 7],
      4: [2, 8],
      5: [1, 3, 7, 9],
      6: [2, 8],
      7: [3, 5],
      8: [4, 6],
      9: [1, 5],
    }
    
    # generate k-length paths
    def path(k, adj, ds=[]):
      if k == 0:
        yield ds
      elif k > 0:
        # extend the path, or choose a starting digit
        for x in (adj[ds[-1]] if ds else adj.keys()):
          yield from path(k - 1, adj, ds + [x])
    
    # find 3-digit "knight" and "bishop" numbers
    numbers = lambda adj: set(nconcat(ds) for ds in path(3, adj) if ds[0] != 0)
    kns = numbers(knight)
    bns = numbers(bishop)
    
    # consider possible bishop numbers
    for b in bns:
      # is there a knight number that is 27 more?
      k = b + 27
      if k in kns:
        printf("b={b} k={k}")
    

    Solution: The bishop’s number is 591, and the knight’s number is 618.

    These numbers can be preceded with 1 or 7 to make 4-digit numbers with the same property.

  2. Frits 30 June 2022 at 1:14 pm

    Experimenting with operator import.

       
    from enigma import SubstitutedExpression
    from operator import ne, eq
    
    # check valid moves for bishop and knight
    def check(n, piece):  
      s = str(n)
      op = eq if piece == "knight" else ne
      for i in range(1, len(s)):
        prev, curr = int(s[i - 1]), int(s[i])
        
        # check odd/even
        if op(prev % 2, curr % 2): return False
        
        # disallow horizontal move
        if (curr - 1) // 3 == (prev - 1) // 3: return False
        # disallow vertical move
        if (curr - prev) % 3 == 0: return False
      
      return True
    
    # 7 8 9           knight = KNO
    # 4 5 6   
    # 1 2 3           bishop = BCD
      
    # the alphametic puzzle
    p = SubstitutedExpression(
      [
       "check(BCD, 'bishop')",
       "check(KNO, 'knight')",
       "check(XBCD, 'bishop')",
       "check(XKNO, 'knight')",
       # loop over KNO as we then have to loop less
       "KNO - 27 = BCD",
      ],
      answer="BCD, KNO, X",
      d2i=dict([(0, "KNOBCDX")] +
               [(5, "KNO")]),
      # a move has to take place   
      distinct=("XK", "KN", "NO", "XB", "BC", "CD"),
      env=dict(check=check),
      verbose=0,    # use 256 to see the generated code
    )
    
    d = dict()
    # group solutions by bishop and knight
    for _, s in p.solve():
      d[(s[0],s[1])] = 1
    
    # print answers
    for k in d.keys():
      print(f"bishop: {k[0]}, knight: {k[1]}")
    
  3. ILya ILba 15 July 2022 at 11:33 pm

    Analytical solution.
    Let b_2, b_1, b_0 and k_2, k_1, k_0 be the 100s, 10s and 1s digits of the knight and bishop number accordingly. Note that the digits of the bishop number must be either all odd, or all even. On the other hand, the digits of the knight number must alternate in parity, i.e. either odd/even/odd, or even/odd/even.
    We know that the bishop number plus 27 equals the knight number. Let’s consider adding digits one by one.
    1. k_0 = (b_0 + 7) \mod 10, so k_0 has parity which is opposite to b_0. As b_2, b_1 and b_0 all have the same parity, and k_2, k_1, k_0 must alternate in parity, therefore k_1 must have the same parity as b_1, and k_2 parity must be opposite to b_2.
    2. There should be no carry into the 10th digit, otherwise k_1 = (b_1 + 2 + 1) \mod 10 and b_1 parity is opposite to k_1. To avoid carry, b_0 \leq 2.
    3. There must be carry into the 100th digit, otherwise k_2 = b_2 and k_2 has the same parity as b_2. To have carry into the 100th digit, b_1 \geq 8. However, b_1=8 is impossible, because that gives k_1=(b_1+2) \mod 10=0, which is not a valid digit. So b_1 must be 9.

    From b_1=9, bishop can only go to 1 or 5; considering b_0 \leq 2, we get b_0=1. That gives k_0=8 and k_1=1.
    Bishop can get to b_1=9 from either b_2=1 or b_2=5. First is not valid, because it gives k_2=b2 + 1=2, from where there is no knight move to k_1=1. So that leaves only b_2=5 and k_2=6.

    So the answer is 618 for the knight number and 591 for the bishop number.

    Note: the information about X digit is redundant. To find X, consider that the knight can jump to 6 from either 7 or 1, and the bishop can jump to 5 from either 1, 3, 7 or 9. So X \in \{ 1, 7 \}.

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 )

Connecting to %s

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

%d bloggers like this: