7
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ How do you actually minimaze that? Do you use some program? $\endgroup$
    – nonuser
    Commented Feb 8, 2021 at 16:15
  • $\begingroup$ Yes, @Greedoid I used the MILP solver in SAS. $\endgroup$
    – RobPratt
    Commented Feb 8, 2021 at 16:18
  • $\begingroup$ As always, excellent work Rob! $\endgroup$
    – Dmitry Kamenetsky
    Commented Feb 8, 2021 at 22:25
  • $\begingroup$ Any way, are those computations doable by hand (in reasonable time)? $\endgroup$
    – nonuser
    Commented Feb 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$
    – RobPratt
    Commented Feb 9, 2021 at 15:19
5
$\begingroup$

@RobPratt's answer is correct. Here are the alternative arrangements I've found, all of which are only slightly different from each other.

enter image description here

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.

Improve this answer
$\endgroup$
11
  • 3
    $\begingroup$ This matches the count of inequivalent solutions in oeis.org/A006076 $\endgroup$
    – RobPratt
    Commented Feb 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$
    – daw
    Commented Feb 8, 2021 at 16:04
  • 1
    $\begingroup$ @daw Well spotted. Same for third row, first and fifth columns $\endgroup$
    – xhienne
    Commented Feb 8, 2021 at 16:18
  • $\begingroup$ @daw Thanks for pointing that out! I got one of the "volatile" knight positions wrong. Fix incoming :) $\endgroup$
    – Zoir
    Commented Feb 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$
    – xhienne
    Commented Feb 8, 2021 at 16:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.