The knight attack graph has one vertex per chessboard square and an edge between squares linked by a knight move. A nonattacking placement is an independent set. Colouring squares by the parity of the coordinate sum makes this a bipartite graph, because every knight move changes that parity. Every vertex has degree at most eight, with fewer attacks near the boundary.
Articles by others on the same topic
There are currently no matching articles.