Can you place 21 knights on a 11x11 chess board, such that every empty cell is under attack? Good luck!
Here is a similar question for 10x10: Knights covering a 10x10 chess board
$\begingroup$
$\endgroup$
0
asked Feb 8, 2021 at 10:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
You can solve the problem via integer linear programming as follows. Define a graph with one node per cell and an edge for each pair of cells that are a knight's move away from each other. For node $i\in N$, let $N_i \subset N$ be the neighbors of $i$, and let binary decision variable $x_i$ indicate whether node $i$ is selected. The problem is to minimize $\sum_{i\in N} x_i$ subject to $$x_i + \sum_{j\in N_i} x_j \ge 1 \quad \text{for $i\in N$}.$$ The constraint enforces that either node $i$ or one of its neighbors is selected.
Here's one optimal solution:
. . . . . . . . . . . . . X . . . . . X . . . X X X . . X X X X . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . X . X . . . X X . . . X . . . . . X X . . . X . X . . X . . . . . . . . . . . . . .
The minimum such domination number for an $n \times n$ board is in OEIS A006075.
-
$\begingroup$ How do you actually minimaze that? Do you use some program? $\endgroup$– nonuserFeb 8, 2021 at 16:15
-
$\begingroup$ Yes, @Greedoid I used the MILP solver in SAS. $\endgroup$– RobPrattFeb 8, 2021 at 16:18
-
-
$\begingroup$ Any way, are those computations doable by hand (in reasonable time)? $\endgroup$– nonuserFeb 9, 2021 at 14:45
-
$\begingroup$ @Greedoid There are 121 variables, 121 constraints, and 841 constraint coefficients. Tiny for a MILP solver, but nothing I'd want to do by hand. $\endgroup$– RobPrattFeb 9, 2021 at 15:19
$\begingroup$
$\endgroup$
11
@RobPratt's answer is correct. Here are the alternative arrangements I've found, all of which are only slightly different from each other.
Picking exactly one white knight from each color group will lead to a valid arrangement, giving a total of $5 \cdot 5 \cdot 2 \cdot 2 \cdot 8 = 100$ arrangements unique up to reflection and rotation.
-
3$\begingroup$ This matches the count of inequivalent solutions in oeis.org/A006076 $\endgroup$– RobPrattFeb 8, 2021 at 15:55
-
2$\begingroup$ Are you sure the picture is correct? Last row, third column - this field is only attacked by one of the blue knights and by no black one. $\endgroup$– dawFeb 8, 2021 at 16:04
-
1$\begingroup$ @daw Well spotted. Same for third row, first and fifth columns $\endgroup$– xhienneFeb 8, 2021 at 16:18
-
$\begingroup$ @daw Thanks for pointing that out! I got one of the "volatile" knight positions wrong. Fix incoming :) $\endgroup$– ZoirFeb 8, 2021 at 16:20
-
1$\begingroup$ @Zoie. There is still a problem with the third row (see my comment above). Knight in (3,2) is necessary. $\endgroup$– xhienneFeb 8, 2021 at 16:30