Problem 4. (4 points) A chess piece moves 8 or 9 squares in a horizontal or vertical direction on a $15 \times 15$ board, with each square being visited at most once. What is the maximum number of squares the piece can visit? (There is no restriction on which square the piece starts from.)
Solution: We will prove that at most 196 squares can be visited.

We associate each square with a pair of numbers $(i, j), i, j=1, \ldots, 15$, where the first is the vertical coordinate (from top to bottom), and the second is the horizontal coordinate (from left to right).

Let's start the traversal from the square $(9,7)$ according to the following rules:

1) From a square in the upper half of the board, we move either 8 squares to the right or 9 squares to the left, if at least one of these moves is possible (since $9+8>15$, both cannot be possible!). If neither is possible, we move 9 squares down.
2) From a square in the lower half of the board, we move either 9 squares to the right or 8 squares to the left, if possible. If not, we move 8 squares up.

It is easy to verify that this way we will visit all the squares on the board, except for the squares of the form $(i, 8)$ and $(8, j)$ (forming a "cross"), i.e., a total of 196 squares.

If at any point during the traversal we land on a square from the "cross," it is clear that both the previous and the next move are also "on the cross." This means that the traversal includes no more than 29 squares. Therefore, 196 is the maximum number of visited squares.