Minimum queens to reach $8 \times 8$ squares as a graph problem

Question

A homework problem asks

What is the minimum number of queens to reach all squares on a $8 \times 8$ chess board?

We are expected to solve this by somehow casting the problem as a graph problem (e.g. Minimum Spanning Tree, Vertex Cover, Independent Set, ...)

How would you reduce this problem to a graph problem, and which graph problem is the most straightforward to reduce this to?

(My first try at this problem was to reason that the number of different squares that a queen can reach is at most $\small 8 + (8-1) + (8-1) + (7-1) = 28$. This is from assuming $8 \times 8$ squares and choosing to place the queen at one of the $4$ center squares. I don't know if this approach can lead to a solution.)

Answer 1

Graph theoretically, you are looking for the domination number of the graph $G=(V,E)$ where $V$ is the set of squares, and with two squares adjacent if a queen can legally move from one to the other.

Answer 2

While I don't know the answer, the problem can be solved by modelling it as a set cover problem.

• The board can be modelled as $B:=\{(a,b)\,|\,1\leq a,b\leq 8\}$.
• For each square $(a,b)\in B$ let $r(a,b)\in 2^B$ be the set of squares, reachable by a queen positioned at $(a,b)$ within one move.
• Let $S=\{r(a,b)\,|\,1\leq a,b\leq 8\}$.

Now, we obviously have $\bigcup S = B$. WHat you're looking for now, is a minimum cardinality cover $C\subseteq S$ such that $\bigcup C = B$.