# Enigmatic Code

Programming Enigma Puzzles

## Puzzle #173: Knight moves

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
if k == 0:
yield ds
elif k > 0:
# extend the path, or choose a starting digit
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",
],
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

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 \}$.

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