Department of Applied Mathematics & Physics, Kyoto University

### Technical Report 2015-007 (December 22, 2015) Queen Sweeping Rectangle Boards by Hiroshi Nagamochi

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.