In the chessboard, how many movements are required by a queen (or a
rook)
to visit each of the all $8\times 8$ squares on the board at least once?
In general, given an $m\times n$ rectangle board, we consider
the minimum number $r(m,n)$ (resp., $q(m,n)$) of movements required
by a rook (resp., a queen)
to cover all the $m\times n$ squares.
For an $n\times n$ square board, we also consider
the minimum number $r_{\mathrm{dia}} (n)$ (resp., $q_{\mathrm{dia}}
(n)$)
of movements required by a rook (resp., a queen)
to cover all the $2n$ or $2n-1$ diagonal squares in the board.
As a relaxed version of each of these problems, we regard a given $m\
times n$ rectangle board
as part of the infinite grid board, and
denote by $r^{\ast}(m,n)$
the minimum number of movements required by a rook
to cover all the $m\times n$ squares,
possibly visiting the exterior of the rectangle board.
Similarly define $q^{\ast}(m,n)$, $r_{\mathrm{dia}}^{\ast}(n)$
and $q_{\mathrm{dia}}^{\ast}(n)$ as the corresponding versions
of $q(m,n)$, $r_{\mathrm{dia}}(n)$
and $q_{\mathrm{dia}}(n)$ on the infinite grid board.
In this paper, we determine
$r(m,n)$, $r^{\ast}(m,n)$, $q(m,n)$, $q^{\ast}(m,n)$,
$r_{\mathrm{dia}} (n)$, $r_{\mathrm{dia}}^{\ast}(n)$,
$q_{\mathrm{dia}} (n)$ and $q_{\mathrm{dia}}^{\ast}(n)$
as functions of $n$ for all integers $m\geq n$.
We also show the NP-completeness of
the problem of determining the minimum number of movements
by a queen or rook to cover a target set of squares
without going outside a specified gird area.