Detecting resource allocation conflict Definitions
We have grids of n by n cells. The columns are named A, B, C, etc. In each cell of each row the column letter could be on or off. We define two grid types - Type 0 and Type 1. Here are three examples:
     a b - - -      a - -      - - - d
     - b c d -      a - c      a - - -
     - - c - e      - b -      - b c -
     a - c - e                 - - - d
     a - c d -
     ---------------------------------
       5 x 5        3 x 3       4 x 4

A Type 1 grid is a grid where we can assign a unique letter to each row, otherwise we have a Type 0 grid.
In the examples above, the first two grids are Type 1, but the third one is Type 0. For the first grid it is possible to use abced as unique row selections. For the second grid we have acb, but with the last grid we could use d either for the first row or the last one. So no unique row letter could be found for all rows.
The problem
Is there a method to identify the type of a grid without searching for a working solution?
A proposed solution - Interest vs. Redundancy
After giving some thought to the problem it would look as if we could determine the type of a grid by comparing the number of times each letter appears in the grid and the number of times it could be substituted. So we define two characteristics:


*

*Interest factor

*Redundancy factor


Every time a given letter appears in a row we say an interest has been shown to use that letter and we increment the interest variable for that letter. If that row has more letters besides the letter under inspection we say that the letter is also being redundant for that row and we increment redundancy variable for that letter. After we have counted interest and redundancy for all letters we say we have a Type 1 grid if for no letter Interest - Redundancy is greater than 1.
So for the 5 x 5 grid above we have:
L  I  R  I-R
a  3  3  0
b  2  2  0
c  4  4  0
d  2  2  0
e  2  2  0

However for the last grid we have:
L  I  R  I-R
a  1  0  1
b  1  1  0
c  1  1  0
d  2  0  2

So, here, twice an interest has been shown to use d, and neither times it has been redundant or replaceable.
Unfortunately, this simple method sometimes produces false positives. Take a look at this grid for instance:
     a b c -
     - - c d
     - - c d
     - - c -

Using the method described earlier we have:
L  I  R  I-R
a  1  1  0
b  1  1  0
c  4  3  1
d  2  2  0

The values in I-R column suggest that we have a Type 1 grid, but the grid is actually a Type 0 one. The problem here is, we are making c redundant 2 times on account of d, but in fact we could only use one of those. So, we need to make sure we do not use the same letter twice to mark another letter redundant.
At this point however, I suspect if I have reduced the complexity at all. Am I not chasing my tail? Should I continue this path and find a way to calculate yet another variable (Usable redundancy)?
My questions 


*

*Is this a known problem, and if so what is its name, has it been solved?

*Is calculating Usable redundancy any simpler than the original problem?

*Could we avoid backtracking and inspecting permutations at all?

 A: Well, may as well tap my inner Boba Fett and flesh out my comment.
What I think you are saying is that a grid is of Type 1 if you can find a set of $n$ "on" entries with exactly one of these entries in every row and exactly one in every column. 
From an $n\times n$ grid $G$, form a bipartite graph $B(G)$ with vertex set $R\cup C = \{r_1,\ldots,r_n\}\cup\{c_1,\ldots,c_n\}$ and edges consisting of precisely those $(r_i,c_j)$ in which the $(i,j)$-entry in $G$ is "on".
For example, your first grid corresponds to: 

What I think is fairly clear is the following
Lemma: $G$ is of Type $1$ if and only if $B(G)$ has a perfect matching: a set of $n$ edges, no two of which share a common vertex.
So, again for your first example, your "unique row selection" demonstrating that the grid is of Type 1 corresponds to the perfect matching consisting of the red edges:

There is a famous necessary and sufficient condition to decide if a bipartite graph has a perfect matching. For a subset $R^\prime$ of $R$, let $N(R^\prime)$ be the set of all vertices in $C$ which are adjacent to some vertex in $R^\prime$.
Hall's Marriage Theorem: $B(G)$ has a perfect matching if and only if every $R^\prime\subseteq R$ satisfies $|R^\prime|\leq |N(R^\prime)|$.
For example, your third grid example corresponds to 

If we choose $R^\prime=\{r_1,r_4\}$ then $N(R^\prime)=\{c_4\}$ so that $|R^\prime|>|N(R^\prime)|$. By Hall's Theorem, the graph has no perfect matching and hence the grid is of Type $0$. That is basically the same as reasoning you gave above. You can switch the roles of $C$ and $R$ above if you prefer. Thus the grid is of type $0$ since $C^\prime=\{c_2,c_3\}$ has more vertices than $N(C^\prime)=\{r_3\}$. .
In terms of the grid data itself, you can translate Hall's Theorem into the following:
Theorem. A grid is of type $1$ if and only if for all $k\in\{1,2,\ldots,n\}$ and every subset of $k$ rows, there are at least $k$ columns in those rows with at least one "on" entry. 
So in general you still have to check around $2^n$ conditions.  Actually it would usually be much faster (polynomial time in $n$) to just run one of the standard algorithms that will actually find a perfect matching/"unique row selection" if one exists.
