5
$\begingroup$

In Naughty knights it’s asked to prove that it’s impossible to fit more than 32 knights such that no knight attacking other.

Can you find the minimum number of knights, filling the table in a way that fitting any other knight is impossible unless two attacking each other.

$\endgroup$
7
  • 1
    $\begingroup$ Are you asking for solution in which none of the knights attack another knight? (The minimal knight covering can be easily found online, but does not have such restriction.) $\endgroup$ Dec 23, 2023 at 16:11
  • $\begingroup$ Spoiler: this question on chess.SE has solutions that do not prohibit attacking occupied squares. $\endgroup$ Dec 23, 2023 at 16:15
  • $\begingroup$ @DanielMathias Both of those linked solutions contain attacking pairs. $\endgroup$
    – RobPratt
    Dec 23, 2023 at 16:58
  • $\begingroup$ @RobPratt As I stated. $\endgroup$ Dec 23, 2023 at 17:00
  • $\begingroup$ @DanielMathias OK, so by "Spoiler" you meant that the first solution provides a lower bound? $\endgroup$
    – RobPratt
    Dec 23, 2023 at 17:03

1 Answer 1

5
$\begingroup$

If the placed knights also cannot attack each other, you are asking for the independent domination number of the knight's graph that has a node for each cell and an edge for each pair of cells that are a knight's move apart. Via integer linear programming with a binary decision variable for each cell, the minimum turns out to be

14:

enter image description here

$\endgroup$
2
  • $\begingroup$ You could have made it symmetrical with C1 to A2 or H7 to F8. $\endgroup$ Dec 23, 2023 at 17:10
  • $\begingroup$ Yes, and it turns out that there are eight 180-degree rotationally symmetric solutions. $\endgroup$
    – RobPratt
    Dec 23, 2023 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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