Fill the grid subject to product, sum and knight move constraints

Question

Using the numbers 2, 3, 4, ... 19 each exactly once, fill some of the empty squares in the grid with a number so that the product of the numbers in each row is as shown, as is the sum of the numbers in each column.

Also a chess knight starting on the square numbered 1 must be able to make a valid move and land on the square numbered 2 and from there it must be able to make a valid move and land on the square numbered 3 then jump to 4 then 5 ... finally landing on the square numbered 20.

---

Attribution: June 2024 issue of MathsJam Shout. (Puzzle by Paul Taylor)

Answer 1

The obvious first step is to list the prime factorization of each product. Red cells mark the prime factors that are already used. Also, let's subtract the placed numbers from the sums for easier tracking.

The prime factors 11, 13, 17, and 19 appear exactly once in the range from 1 to 20. Therefore, we know that 17 appears in R2, 19 in R3, and 11 and 13 in R4. We can immediately place 19, which must be a knight away from the given 20.

Let's draw a checkerboard. Since a knight's move connects a white cell and a green cell, all odd numbers appear on green cells and all even numbers appear on white. Now we can place 17: it can only go to either R2C1 or R2C3, but it cannot go to C1 since the remaining sum is not large enough, so it goes to R2C3. 18 goes to the only remaining cell that is a knight away from both 17 and 19, which is R4C4.

15 can only appear on R3 because R5 does not have the prime factor 3. Since there is only one green cell left on R3, 15 goes there. There are two cells that are a knight away from both 17 and 15: R1C5 and R4C2. Since R4 does not contain enough 2s, 16 goes to R1C5.

At this point, we can identify which numbers go to which row. There are two multiples of 5 remaining (5 and 10), both of which go to R5 (by the prime factors 5), and since 2 cannot be on R5 (too far away from 1), the remaining number must be 14. R1 must have 2 and 7, which places 2 immediately (only one white cell left) and 3 (only one cell left that is a knight away from 2).

On R3, only white (even) cells are available, so the remaining number must be a single 6. 8 must be a knight away from 7, which places it on R2 (because R3 is not available). The other cell on R2 becomes 12.

The remaining numbers are 4 and 9, which fit the remaining product 2^2 3^2 on R4. 4 goes to the only white cell left.

Placing 7 on C2 makes the C2 sum impossible (because 1 is already used), so it goes to C4. 8 goes to C2 by a knight move from 7, and 12 goes to C4. By C4 sum, 5 goes to C4 as well.

There is only one way to make the sum of 9 using the remaining numbers: 9 itself. So 9 goes to C1. 10 and 11 are placed by knight's moves; 13 and 14 go to the only remaining cell with nonzero sums respectively; 6 goes to C5 to make the final sum correct.

Answer 2

First find a place for 19:

19 is a factor of 1710 = 19 x 90, this puts 19 in row 3. It must be a knight's move from 20, in column 2. Number 19 is placed in row 3, column 2.

Then for 17:

17 is a factor of 4896 = 17 x 288, this puts 17 in row 2. It cannot be in column 1, as this would exceed the given sum. Column 3 is the only other odd cell available in row 2. Number 17 is placed in row 2, column 3.

Then for 18:

18 must be a knight's move from both 17 and 19. Number 18 is placed in row 4, column 4.

For 11, 12, 13:

11 and 13 are factors of 92664 = 11 x 13 x 648. They are both in row 4. Neither can be in column 1, so they must be in columns 3 and 5. The number 12 must be a knight's move from each: Number 12 is placed in row 2, column 4.

For 14, 15, 16:

With 13 in row 4, 14 must be in row 5, column 3 or 5. From either of those cells, number 15 is placed in row 3, column 4. With 15 and 17 in place, 16 must be a knight's move from both. The column sum would be exceeded in column 2, so number 16 is placed in row 1, column 5.

Continuing:

Row 2 contains 17, 12 and 1. The product of the remaining numbers in this row is 24. This requires two numbers, one of which must be odd. This can only be 3 x 8.
Number 3 is placed in row 2, column 1.
Number 8 is placed in row 2, column 2. Number 7 is placed in row 1, column 4.

Row 3 contains 19 and 15. The product of the remaining numbers in this row is 6. Number 3 is already placed in row 2, so the only other number in row 3 is 6.
Number 2 is placed in row 1, column 3. (A knight's move from both 3 and 1)
Number 4 is placed in row 4, column 2.
Number 5 is placed in row 5, column 4.

Number 9 is placed in row 4, column 1.
Number 10 is placed in row 5, column 3.
Number 11 is placed in row 4, column 5.
Number 13 is placed in row 4, column 3.
Number 14 is placed in row 5, column 5.
Number 6 is placed in row 3, column 5.

The completed grid:

 20 ..  2  7 16
  3  8 17 12  1
 .. 19 .. 15  6
  9  4 13 18 11
 .. .. 10  5 14
 

Answer 3

You can solve the problem via integer linear programming as follows. For $i,j\in\{1,\dots,5\}$ and $k\in\{1,\dots,20\}$, let binary decision variable $x_{ijk}$ indicate whether cell $(i,j)$ takes values $k$. Let $c_j$ be the required sum of column $j$, and let $r_i$ be the required product of row $i$. For prime $p\in\{2,3,5,7,11,13,17,19\}$, let $\nu_p(n)$ be the $p$-adic valuation of $n$, that is, the exponent of $p$ in the prime factorization of $n$. Let $N_{ij}=\{(i',j'):|i-i'| \cdot |j-j'|=2\}$ be the set of knight's move neighbors of cell $(i,j)$. The constraints are \begin{align} x_{1,1,20} &= 1 \tag1\label1 \\ x_{2,5,1} &= 1 \tag2\label2 \\ \sum_k x_{ijk} &\le 1 && \text{for all $i,j$} \tag3\label3 \\ \sum_i \sum_j x_{ijk} &= 1 && \text{for all $k$} \tag4\label4 \\ \sum_i \sum_k k x_{ijk} &= c_j && \text{for all $j$} \tag5\label5 \\ \sum_j \sum_k \nu_p(k) x_{ijk} &= \nu_p(r_i) && \text{for all $i, p$} \tag6\label6 \\ x_{ijk} &\le \sum_{(i',j') \in N_{ij}} x_{i',j',k+1} && \text{for all $i,j$ and $k < 20$} \tag7\label7 \end{align} Constraints \eqref{1} and \eqref{2} enforce the given locations of $20$ and $1$. Constraint \eqref{3} assigns at most one value to each cell. Constraint \eqref{4} assigns each value to exactly one cell. Constraint \eqref{5} enforces the column sums. Constraint \eqref{6} enforces the row products. Constraint \eqref{7} enforces the knight's move restriction.

The unique solution turns out to be

\begin{matrix} 20 &. &2 &7 &16 \\3 &8 &17 &12 &1\\. &19 &. &15 &6\\9 &4 &13 &18 &11\\. &. &10 &5 &14\end{matrix}

Answer 4

It isn't necessary to have all the column sums for a unique solution. You only need the third or fifth, plus the parity of the second or fourth.

    20 .. .. .. .. | 2 2 2 2 2 X2 X2 X5 7
    .. .. .. .. 01 | 2 2 2 2 2 3 3 17
    .. .. .. .. .. | 2 3 3 5 19
    .. .. .. .. .. | 2 2 2 3 3 3 3 11 13
    .. .. .. .. .. | 2 2 5 5 7
 

Product rules put the 17 on second row, 19 and 15 on third, 11 and 13 on fourth. The only way to put the 19 on third and be a knight's move from the 20 is R3C2.

    20 .. .. .. .. | 2 2 2 2 2 7
    .. .. .. .. 01 | 2 2 2 2 2 3 3 : 17
    .. 19 .. .. .. | 2 3 : 15
    .. .. .. .. .. | 2 2 2 3 3 3 3 : 11 13
    .. .. .. .. .. | 2 2 5 5 7

The 18 can't be on row 1 or 5 because those rows aren't divisible by 3. It can't be on rows 2 or 3 because those rows can't be a knight's move from the 17 or 19, respectively. The only place on row 4 that's a knight's move from 19 is R4C4. The only place on row 2 that's a knight's move from R4C4 that isn't already occupied is R2C3.

    20 .. .. .. .. | 2 2 2 2 2 7
    .. .. 17 .. 01 | 2 2 2 2 2 3 3 :
    .. 19 .. .. .. | 2 3 : 15
    .. .. .. 18 .. | 2 2 3 3 : 11 13
    .. .. .. .. .. | 2 2 5 5 7
 

The only place that's a knight's move from 17 and is on a row divisible by 16 in R1C5. The only unused place that's a knight's move from 16 is R3C4.

    20 .. .. .. 16 | 2 7
    .. .. 17 .. 01 | 2 2 2 2 2 3 3 :
    .. 19 .. 15 .. | 2 3 :
    .. .. .. 18 .. | 2 2 3 3 : 11 13
    .. .. .. .. .. | 2 2 5 5 7
 

14 can't go on row 1 (it's not a knight's move from 13), so it's on the other line divisible by 14 (row 5). 2 and 3 can't go on the same row, so row 3 must use 6. 5 and 10 can only go on row 5 (only row divisible by them). 14 isn't on row 1, so it must hold 2 and 7.

    20 .. .. .. 16 | : 2 7
    .. .. 17 .. 01 | 2 2 2 2 2 3 3 :
    .. 19 .. 15 .. | :  6
    .. .. .. 18 .. | 2 2 3 3 : 11 13
    .. .. .. .. .. | : 5 10 14

3 can only go on row 2 (row 4 isn't a KM from the 2 on row 1). 4 must go on row 4. 8 goes on row 2 (only row divisible). 9 goes on row 4 (only row divisible). 12 goes on row 2 (only row divisible)

    20 .. .. .. 16 | : 2 7
    .. .. 17 .. 01 | : 3 8 12
    .. 19 .. 15 .. | : 6
    .. .. .. 18 .. | : 4 9 11 13
    .. .. .. .. .. | : 5 10 14
 

KM and row constraints force positions of 2 through 5. The only way to place the 10 a KM from two different cells on row 4 is in R5C3; 9 and 11 are in R4C1 and R4C5 in some order, forcing R4C3 as 13. 14 must now go in R5C5.

    20 .. 02 .. 16 | : 7
    03 .. 17 .. 01 | : 8 12
    .. 19 .. 15 .. | : 6
    .. 04 13 18 .. | : 9 11
    __ __ 10 05 14 | :
 

And that's what you can get while ignoring the column constraints.

The unknown cells in R4 are odd; the unknown cells in R2, R3, and R5 are even or empty. If the 7 is in R1C2, then all columns will have even sum. If the 7 is in R1C4, then C1, C3, and C5 have even sum and C2 and C4 have odd sum. Since we were given they were odd, that forces 7 to R1C4, and KMs force 8-12:

    20 __ 02 07 16 | :
    03 08 17 12 01 | :
    .. 19 .. 15 .. | : 6
    09 04 13 18 11 | :
    __ __ 10 05 14 | :
 

Finally, the sum of C3 or C5 gives the position of the 6.

    20 __ 02 07 16 | :
    03 08 17 12 01 | :
    __ 19 __ 15 06 | :
    09 04 13 18 11 | :
    __ __ 10 05 14 | :
 

Looking back, the sum of C5 is enough to solve the puzzle.

Alternately, if instead of the column sums, we were just given that C2 or C4 had an even sum, that would be enough to force the whole grid.