My solution: It is obvious that atleast one rook will be left in the end. We assert that we can remove $ 63 $ rooks. Label the squares of the chessboard in the usual way with $ a1 $ etc. We first remove the $ h2 $ rook, and then the $ h1$ rook. Similarly, we remove the $ h4 $ rook then the $h3$ rook. Similarly following, we empty the $h$-file. By a similar strategy, empty next the $g,f,e,d,c,b$ files. Finally, remove the $a1,a2,a3,a4,a5,a6,a7$ rooks successively. We are left with exactly one rook, as claimed.

@AdithyaBhaskar: You cannot remove the h1 rook, as it attacks exactly 2 rooks (the one on g1 and the one on h3). The correct answer is 59, or more generally: On an $n \times n$ chess board with $n \ge 3$ you can remove rooks as described in the problem description until you have 5 rooks left, but not further. I'll use normal matrix notation with brackets to denote a given chessboard square or rook (so [1,1] is the top left square, R[1,n] the rook on the top right square, a.s.o). I'll note the number of currently attacked other rooks in parenthesis (so R[n,1](2) means that the rook on the bottem left attacks exactly 2 other rooks at the moment). Let's first see why you cannnot go below 4 rooks. That's because you cannot ever remove the 4 rooks in the 4 corners. They are on extreme positions in both their row and column, so each of them can potentially attack at most 2 other rooks and they start out attacking exactly 2 other rooks. As long as all 4 rooks in the corner are on the board, you cannnot remove one of them. That's because (for example) the R[1,1] will always attack exactly one rook on row 1. It may be the R[1,2] (if it's still on the board), or R[1,3],..., but as long as R[1,n] stays on the board, there will be another rook on row 1 that R[1,1] attacks. The same goes for R[1,1] and column 1 (as long as R[n,1] is on the board). Of course the same is true by symmetry for all 4 rooks. Because there can never be a "first corner rook removed", there can never be a corner rook removed. If $n \ge 3$, there are more chess squares than the 4 corners. If you could remove rooks from all of them except for the 4 corner rooks, consider the last removal from 5 to the 4 corner rooks. The last rook to be removed is not in a corner (already established). If it is on a side of the chess board it is therefore on exactly one side. Hence it attacks exactly 2 rooks on that side (the corner rooks of that side) and excatly 0 rooks on the other direction, which contradicts the rule of only removing rooks that attack an odd number of other rooks. If the last rook to be removed is in the interior of the board, it attacks 0 other rooks, also creating a contradiction. So we have established that 5 rooks must at least remain on the board. I'll show by induction how to actually keep only 5 rooks on the board. What I'm about to prove is: For $n \ge 3$, on an $n \times n$ chessboard starting with a rook on every chessboard square except on [n,n-1], you can remove rooks according to the rule of the problem until you have only 5 left. (1) Proof: Inductuion start: $n=3$, we start with RRR RRR R RWe now remove R[2,1](3), R[1,2](3) and finally R[2,3](3) to get R R R R R Induction step: We have an $n+1 \times n+1$ board, the last 2 rows and 3 columns look like RR ... RRR ... RR ... RRR RR ... R RWe remove R[1,n](3), R[2,n](3),...R[n-1,n](3), vacating the second to last column except for the remaining R[n,n]: RR ... R R ... RR ... R R RR ... RRR RR ... R RNow we remove R[n,n+1](3), then R[n,1](3), R[n,2](3),...R[n,n-2](3) ($n \ge 3$ makes sure the last entry is meaningfull). We have vacated the second to last row except for 2 rooks: RR ... R R ... RR ... R R ... RR RR ... R RWe finally empty both the second to last row and column by removing R[n,n](1), R[n+1,n-1](3) and R[n,n-1](1): RR ... R R ... RR ... R R ... RR ... R The result is a board with row and column n empty and an additional empty square at [n+1,n-1]. An empty row or column can be discarded. There are no rooks in there that might in the future be removed and there are no rooks in there that can be attacked (or prevent another rook from being attacked). If you have an empty column, simply move all rooks to the right of the empty column 1 square to the left, an nothing has changed with respect to attacks. The same goes for an empty row, simply move all rooks below it 1 square up. If one does that for row n and column n in the situation above, one gets an $n \times n$ board full of rooks except on [n,n-1] (this is where empty square [n+1,n-1] end up when removing empty row n). This is exactly the inital board configuration on our induction assumption, so we know we can continue to remove rooks until only 5 are left. q.e.d. The "missing rook" in (1) is due to a technicality in the induction step, but since R[n,n-1] attacks exactly 3 other rooks in the "full board of rooks" starting configuration, we can remove it as the first step immediately and then apply (1) to show that also the "full board of rooks" starting configuration can be reduced to 5 rooks.

The answer is $59$. Proof. [Proof $\ge 5$ rooks always remain] To show that $5$ rooks must remain, observe first that the four corners may never be deleted (as long as all four corners are present, these rooks attack exactly $2$ others). Moreover, if there are $5$ rooks left on the board, the non-corner rook cannot be removed by inspection. $\blacksquare$ Here is the construction. Each cell is labeled with the time it is removed. They are color coded for convenience. \[ \begin{array}{cccccccc} {\bigstar} & 1 & 2 & 3 & 4 & 5 & 6 & {\bigstar} \\ 13 & 50 & 51 & 52 & 53 & 54 & 55 & 7 \\ 14 & 15 & 16 & 17 & 18 & 19 & 56 & 8 \\ 20 & 21 & 22 & 23 & 24 & 25 & 57 & 9 \\ 26 & 27 & 28 & 29 & 30 & 31 & 58 & 10 \\ 32 & 33 & 34 & 35 & 36 & 37 & 59 & 11 \\ 38 & 39 & 40 & 41 & 42 & 43 & {\bigstar} & 12 \\ {\bigstar} & 44 & 45 & 46 & 47 & 48 & 49 & {\bigstar} \end{array} \]

Really cool problem. Also darn the construction is really painful. The answer is $59$ rooks. Proof of Bound: Notice that all four corner rooks will always see each other or some rook between them, so they always see exactly two rooks. As a result, they can never be removed. To show that a fifth rook must also be present, notice that it is impossible for any rook to be removed in the configuration of the four corner rooks and that rook. Thus, there are at most $59$ rooks removed. Construction: We proceed in three steps. Step One: Remove all the rooks in the first column, except for the two corner rooks. For the next four columns, remove the rook in rows 2 through 6 in that order and then the rooks in rows 1 and 8. The rook in row 7 can also now be removed because it only attacks one rook. Step Two: Remove the rook in row 8, column 6. Keep the rook in row 8, column 7: we will call this the sacrificial rook for simplicity. Now, for each row between 3 and 7, starting from row 7, remove the rook in column 8, the rook in column 7 (as it attacks the sacrificial rook), and then the rook in column 6 (as it only attacks one rook.) Step Three: We are left with a $2 \times 3$ array of rooks in the top-right corner. Remove the rooks in the following order: The rook in row 2, column 8; it attacks three rooks. The rook in row 1, column 7: it attacks three rooks. The rook in row 1, column 6: it attacks three rooks. The rook in row 2, column 6: it attacks only the rook in row 2, column 7. The rook in row 2, column 7: it attacks only the sacrificial rook. This leaves us with only the four corner rooks and the sacrificial rook, as desired.

Note that the last $4$ corners cannot be removed and that at least $5$ must remain. Thus, at most $59$ rooks can be removed. Our construction is to first completely take all rooks from $2$ adjacent "sides" of the square, then to remove the first square from the second row, and to take all the rooks from each row after that (except rooks on the 2nd rightmost column). Finally, take the remaining rooks, going from top left to bottom right. Remark. The construction is significantly harder to find than to find+prove the bound.

Claim 1: It is not possible to remove any of the corner rooks. Proof: Assume FTSOC it is possible. Consider the first corner rook we are removing. Suppose WLOG it is the top right one. The top left and bottom right rooks will still be in their places. So the top right rook is attacking exactly 2 rooks, and cannot be removed. Claim 2: It is possible to remove all the rooks except 5. Proof: Label the columns from left to right as $1,2, \ldots 8$. Similarly label the rows from top to bottom. These numbers will be used as `coordinates for rooks'. Pick some rook with coordinates $(x,y)$ which is not one of the corner rooks. Highlight the column $x$ and the row $y$. They divide the board into 4 `quadrants'. First consider the top right quadrant. Take its rightmost column (the one closest to the highlighted column) and remove each of the rooks, starting from the top and going downwards. Repeat the procedure for the column to its left, and so on till you reach the leftmost column of the quadrant (and the board). For this one, ignore the corner rook and just delete from the rook below it. Repeat a symmetric procedure to remove all the rooks except those in the highlighted row and column and the corner rooks. Colour the rook at the intersection of the highlighted row and column blue. Now start at the top of the highlighted column and start deleting rooks (going downwards) until you reach the blue rook (don't delete it). Do the same from the bottom. Repeat a similar process for the row. You are left with just the blue rook and the corner rooks. Claim 3: It is impossible to be left with just the 4 corner rooks. Proof: Assume FTSOC that it is possible. Consider the last rook that is removed. If it was in an edge row or column, it was attacking 2 rooks. It it was not in an edge row or column, it was attacking 0 rooks. Either way, it was attacking an even number of rooks, so contradiction. From claims, 1, 2 and 3, it is clear that the maximum number of rooks that can be removed is $64-5 = \boxed{59}$.

The answer is $\boxed{59}.$ Notice that the four corners will always remain as they always attack $2$ other rooks. To end up with the final corner rooks, there must be $5$ rooks previously and the non-corner rook is removed. However, this is evidently impossible by inspection. Thus, there are at least $5$ rooks remaining. This is possible with the following configuration: $$ \begin{bmatrix} R&1&2&3&4&5&6&R \\ 13&50&51&52&53&54&55&7 \\ 14&15&16&17&18&19&56&8 \\ 20&21&22&23&24&25&57&9 \\ 26&27&28&29&30&31&58&10 \\ 32&33&34&35&36&37&59&11 \\ 38&39&40&41&42&43&R&12 \\ R&44&45&46&47&48&49&R \end{bmatrix} $$