Introduction

This task is a hard one. The solution is based on the "Hungarian theorem". Basing on the theorem, the problem can be reduced to finding a maximal matching in a bipartite graph. Maximum data size (~40\,000~ fields, i.e. ~40\,000~ vertices) requires best of known algorithms, e.g. Hopcroft-Karp's algorithm.

Problem Analysis

We will build a graph, whose vertices are the fields on the chessboard, and edges represent single moves of the knight. In a single move knight is always jumping from a white field onto a black one, or vice versa, hence the graph is a bipartite one. The maximal independent set of vertices is what we are looking for.

The completion of the independent set of vertices forms a vertex-covering of the graph. One of the formulations of the Hungarian theorem says, that in any bipartite graph the size of the smallest vertex-covering is equal to the size of the maximal matching. Hence, if ~M~ is a maximal matching in the graph, then the result is equal ~|V|-|M| = n^2-m-|M|~. So, the algorithmic part of the solution reduces to finding the maximal matching.

Note, that the maximal degree of each vertex is ~8~. Therefore, ~|E| \le 8|B|, 8|W|~, where ~W~ is the set of white fields, and ~B~ is the set of black fields, and hence ~|E| \le 4|V| = \mathcal O(|V|)~.

Intended Solution

The solution uses Hopcroft-Karp's algorithm.

Considering the big size of the graph, neither it nor the acyclic graph of extending paths can be represented in a straightforward way (at least not in DOS). However, we do not need to remember the set of edges ~E~, since all the moves are allowed. It is enough to remember which fields have been removed and which are present.

The implementation of the auxiliary acyclic graph is more complicated. It can be seen, that we do not need to represent the set of its vertices explicitly. The starting vertices are unmatched white fields of the board, and the rest of them can be accessed through the edges. The lists of incident vertices are represented in a compressed way – one bit per edge and one byte per vertex.

Since ~|E| = \mathcal O(|V|)~, the complexity of this algorithm is ~\mathcal O((|E|+|V|)\sqrt{|V|}) = \mathcal O(|V|^{2/3})~.

Other Solutions

We can find the maximal matching using Edmonds-Karp's algorithm to find the maximal flow. In our case, this algorithm runs in ~\mathcal O(|V|^2)~ time. It is simpler than the intended solution, however it is significantly slower.

We can improve this algorithm. Instead of searching each time for the shortest extending path, we store the list of unmatched white fields and search for extending paths starting from each of these fields. There is no guarantee that we find the shortest path, but if we find a patch quick enough, and it is short, then we can extend the match doing only a few steps instead of ~\Theta(|V|)~.

We can improve this algorithm even further, starting the next search from the field next to the one where the previous extending path started. Proceeding in such a way, if there were no extending paths starting from fields ~A_1, A_3, A_5, A_7, A_9~ and there was such a path starting from ~A_{11}~, then fields ~A_1, A_3, A_5, A_7~ and ~A_9~ will be considered last. Such an improvement gives practically very good algorithm, that sometimes behaves better than the intended one. Moreover, such a solution can be devised even without the knowledge of Hopcroft-Karp's algorithm.

Wrong Solution

One can approximate the solution as maximum of numbers of white and black fields. Such a solution is correct, for example, for chessboards of size not greater than ~3~. Such a solution would score ~0~ points.