Visualizing Rook Placement Problem for Pen and Paper

Problem Explanation:

I currently don't have the link or the name of the problem. This problem is from https://brilliant.org.

The problem is given an N x N chessboard place minimum number of rooks such that all white squares are covered. The opposite could be said too. In chess rooks move vertically and horizontally.

Some Thoughts:

This post is not about ways to solve the problem but to look at it differently. I currently lack the capability to mathematically analyze this problem. Though some things are obvious.

The best way to first understand this problem is to do bottom up construction with 2x2 board, here N = 2.

  Board:
    D W
    W D

Here, placing a rook in a W square would result in cost of 2, since two rooks are required to cover all the white squares. Now placing in the dark square D will result in cost of 1, since it covers all the white squares. So this is the least number of rooks to place in the board to cover all white squares.

Since rooks move vertically and horizontally, placing two rooks in the same row or, column is waste of piece. Here is how I did it on a piece of paper for, N = <1,2,...,8>
Mirroring it will provide a few more non unique solutions.