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

$\endgroup$
0
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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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