The following graph represents the positions at Castle Dragonstone. Each edge indicates that the positions are within sight of each other. This is not transitive; i.e., you can't see all the way along a row or column; you can see only the adjacent positions.

Dragonstone castle grid

King Aerion is putting dragons in his castle. He has a condition that every position in the above graph has to be either occupied by a dragon or within the sight of a dragon. Find the smallest number of dragons that he would need in order to meet this condition.

  • $\begingroup$ Is it right to say that the goal is essential to partition the graph in subgraphs with a maximum diameter of 2 in such a way that you have the least amount of subgraphs? $\endgroup$
    – Ivo
    Jan 26, 2017 at 14:57
  • $\begingroup$ What do you mean it won't work? $\endgroup$
    – Ivo
    Jan 26, 2017 at 15:01
  • $\begingroup$ each such a subgraph has a single dragon on it then $\endgroup$
    – Ivo
    Jan 26, 2017 at 15:04
  • $\begingroup$ A 3x3 grid doesn't have diameter 2. it actually has diameter 4. to get from the topleft position to the bottomright requires 4 steps. A position with a dragon on it with all positions in its sight are allways graphs of diameter 2 $\endgroup$
    – Ivo
    Jan 26, 2017 at 15:09
  • 1
    $\begingroup$ Vertex Cover? :P $\endgroup$ Jan 27, 2017 at 10:10

3 Answers 3


The smallest number of dragons needed is:


This problem boils down into finding:

The minimum vertex cover of the 13 x 13 grid-graph. Another term for minimum vertex cover is "Dominating Set". The domination number for a 13 x 13 grid graph is 40. Here is an example covering.

enter image description here
See OEIS article for the domination number

  • $\begingroup$ Damn... thought I'd got this one... +1 $\endgroup$ Jan 27, 2017 at 14:08
  • $\begingroup$ @BrentHackers Your answer was great, except math. :) $\endgroup$
    – LeppyR64
    Jan 27, 2017 at 14:28
  • $\begingroup$ Harsh... I'm Maths-phobic... $\endgroup$ Jan 27, 2017 at 14:53

My answer:

enter image description here 43 dragons (the number 2's in diagram). The general pattern is optimal as its a tesselated cross shape (see right), resulting in 20% of squares with dragons in an infinite grid. It's optimal because every square is either a dragon or is only adjacent to one dragon. Then it's a matter of choosing a 13x13 sub-grid in this infinite tesselated grid such that the number of additional edge dragons needed (the red 2's in diagram) is minimised. Wherever you place the 13x13 subgrid, you can't get less than 9 of these, and there will always be 34 tesselated dragons.


I got


by starting at the centre and working out...

enter image description here

but I could have that wrong...

Here's a slightly better formatted picture:

![enter image description here


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.