A $$12 × 12$$ board is divided into $$144$$ unit squares by drawing lines parallel to the sides. Two
rooks placed on two unit squares are said to be non attacking if they are not in the same
column or same row. Find the least number $$N$$ such that if $$N$$ rooks are placed on the unit
squares, one rook per square, we can always find $$7$$ rooks such that no two are attacking
each other.

Associate each of the $$12$$ rows with a vertex set $$R=\{r_1,r_2,\dots ,r_{12}\}$$ and each of the $$12$$ columns with another vertex set $$C=\{c_1,c_2,\dots ,c_{12}\}$$. Placing a rook in the square at row $$r_i$$ and column $$c_j$$ is the same as drawing an edge $$r_i c_j$$ in the bipartite graph $$K_{12,12}$$.

A collection of rooks is mutually non-attacking precisely when their edges form a matching, i.e. all chosen edges have pairwise distinct end-points. Thus the problem asks for the smallest $$N$$ such that every bipartite graph on the two $$12$$-element parts with $$N$$ edges must contain a matching of size $$7$$.

Let $$m(G)$$ denote the size of a largest matching in a bipartite graph $$G$$. Define

$$f(7)=\max\{\,|E(G)|:\;G\subseteq K_{12,12},\;m(G)\le 6\,\}.$$

If we can compute $$f(7)$$, then

$$N_{\min}=f(7)+1$$

because with $$f(7)$$ edges there exists a placement without a $$7$$-matching, while with one more edge every placement must contain one.

Step 1: Bounding the number of edges when $$m(G)\le 6$$
For bipartite graphs, Kőnig’s theorem states
 size of a maximum matching = size of a minimum vertex cover.
Hence if $$m(G)\le 6$$, there exists a vertex cover of size at most $$6$$. Such a cover consists of
 $$r$$ rows and $$6-r$$ columns, where $$0\le r\le 6$$.

All edges must be incident to at least one vertex of the cover, i.e. they must lie in one of the following squares:
 • any of the chosen $$r$$ rows (all $$12$$ columns possible), or
 • any of the chosen $$6-r$$ columns (all $$12$$ rows possible).

The only squares forbidden to edges are those whose row is not in the chosen $$r$$ rows and whose column is not in the chosen $$6-r$$ columns. The count of such forbidden squares is

$$\bigl(12-r\bigr)\bigl(12-(6-r)\bigr)=(12-r)(6+r)=72+6r-r^{2}.\tag{-1}$$

Consequently, the maximum number of allowed squares (and hence of edges) for a cover with $$r$$ rows is

$$144-\bigl(72+6r-r^{2}\bigr)=r^{2}-6r+72.\tag{-2}$$

Compute this quantity for $$r=0,1,\dots ,6$$:

$$\begin{aligned} r&\phantom{=}0\quad&: &\;0^{2}-0+72=72\\ r&=1&: &\;1-6+72=67\\ r&=2&: &\;4-12+72=64\\ r&=3&: &\;9-18+72=63\\ r&=4&: &\;16-24+72=64\\ r&=5&: &\;25-30+72=67\\ r&=6&: &\;36-36+72=72 \end{aligned}$$

The largest value is $$72$$ (attained for $$r=0$$ or $$r=6$$). Therefore

$$f(7)=72.\tag{-3}$$

Step 2: Realising the bound
To show the bound is tight, construct a placement with $$72$$ rooks but no $$7$$ mutually non-attacking rooks: fill all squares of any fixed $$6$$ rows (or, symmetrically, any fixed $$6$$ columns). All rooks now lie in only $$6$$ rows, so a non-attacking set can use at most one rook from each of those rows, giving size at most $$6$$. Hence a matching of size $$7$$ is impossible, and $$72$$ rooks indeed avoid it.

Step 3: The required minimum $$N$$
With $$72$$ or fewer rooks one can avoid a $$7$$-matching; with $$72+1=73$$ rooks it is forced. Hence

$$N_{\min}=72+1=73.$$

Answer: 73