Find the rows which make each column have one True (was: Knuth's Algorithm X) Task
Given a Boolean matrix, find one (or optionally more) subset(s) of rows which have exactly one True in each column. You may use any algorithm, but must support very large matrices, like the last example.
One possible algorithm (Knuth's Algorithm X)
While there is no requirement to use this algorithm, it may be your best option.

If the matrix A has no columns, the current partial solution is a valid solution; terminate successfully.
Otherwise choose a column c.
Choose* a row r such that Ar, c = 1.
Include row r in the partial solution.
For each column j such that Ar, j = 1,
 for each row i such that Ai, j = 1,
  delete row i from matrix A.
 delete column j from matrix A.
Repeat this algorithm recursively on the reduced matrix A.

* Step 3 is non-deterministic, and needs to be backtracked to in the case of a failure to find a row in a later invocation of step 3.
Input
Any desired representation of the minimum 2×2 matrix A, e.g. as a numeric or Boolean array
1 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 0
0 1 1 0 0 1 1
0 1 0 0 0 0 1

or as Universe + Set collection
U = {1, 2, 3, 4, 5, 6, 7}
S = {
    A = [1, 4, 7],
    B = [1, 4],
    C = [4, 5, 7],
    D = [3, 5, 6],
    E = [2, 3, 6, 7],
    F = [2, 7]
    }

or as 0 or 1 indexed sets;
{{1, 4, 7}, {1, 4}, {4, 5, 7}, {3, 5, 6}, {2, 3, 6, 7}, {2, 7}}.
Output
Any desired representation of one (or optionally more/all) of the solutions, e.g. as numeric or Boolean array of the selected rows
1 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 0 0 0 1

or as Boolean list indicating selected rows {0, 1, 0, 1, 0, 1} or as numeric (0 or 1 indexed) list of selected rows {2, 4, 6} or as list of set names ['B', 'D', 'F'].
More examples
In:
1 0 1
0 1 1
0 1 0
1 1 1

Out: 1 3 or 4 or 1 0 1 0 or 0 0 0 1 or [[1,3],[4] etc.

In:
1 0 1 0 1
0 1 0 1 0
1 1 0 0 1
0 1 0 1 1

Out: 1 1 0 0 etc.

In:
0 1 0 1 1 0 1
1 1 0 0 1 1 1
0 1 0 0 1 0 0
1 1 1 0 0 0 1
0 0 0 1 1 1 0

Out: 0 0 0 1 1 etc.

In:
0 1 1
1 1 0

Out: Nothing or error or faulty solution, i.e. you do not have to handle inputs with no solution.

In: http://pastebin.com/raw/3GAup0fr
Out: 0 10 18 28 32 38 48 61 62 63 68 86 90 97 103 114 120 136 148 157 162 174 177 185 186 194 209 210 218 221 228 243 252 255 263 270 271 272 273 280 291 294 295 309 310 320 323 327 339 345 350 353 355 367 372 373 375 377 382 385 386 389 397 411 417 418 431 433 441 451 457 458 459 466 473 479 488 491 498 514 517

In: https://gist.github.com/angs/e24ac11a7d7c63d267a2279d416bc694
Out: 553 2162 2710 5460 7027 9534 10901 12281 12855 13590 14489 16883 19026 19592 19834 22578 25565 27230 28356 29148 29708 30818 31044 34016 34604 36806 36918 39178 43329 43562 45246 46307 47128 47906 48792 50615 51709 53911 55523 57423 59915 61293 62087 62956 64322 65094 65419 68076 70212 70845 71384 74615 76508 78688 79469 80067 81954 82255 84412 85227
Haskell, 100 93 92 87 83 80 bytes

Knuth's algorithm:


g&amp;c=filter(g.any(`elem`c))
(u:v)%a=[c:s|c&lt;-id&amp;u$a,s&lt;-(not&amp;c)v%(not&amp;c$a)]
x%_=[x]


Calculates all covers nondeterministically depth-first in the list monad. Use head to calculate only one since Haskell is lazy. Usage:

*Main&gt; [[1],[2],[3],[4],[5],[6],[7]]%[[1, 4, 7], [1, 4], [4, 5, 7], [3, 5, 6], [2, 3, 6, 7], [2, 7]]
[[[1,4],[2,7],[3,5,6]]]


For more speed by using Knuth's suggestion of selecting column with least ones, use this: (115 bytes, flat list for universe). Finds first solution to the large pentomino cover problem in under a minute when compiled.

import Data.List
[]%_=[[]]
w%a=[c:s|c&lt;-a,c\\(head.sortOn length.group.sort$w:a&gt;&gt;=id)/=c,s&lt;-(w\\c)%[b|b&lt;-a,c\\b==c]]


Thanks to @Zgarb for saving 1+3 bytes!

Thanks to @ChristianSievers for his sage advice and saving 5 bytes and some.

Ungolfed (with flat list universe):

knuthX [] _ = [[]]
knuthX (u:niverse) availableRows = --u chosen deterministically
  [ chosen:solution
  | let rows = filter (elem u) availableRows
  , chosen &lt;- rows  --row chosen nondeterministically in list monad
  , solution &lt;- knuthX
                  (filter (not.(`elem`chosen)) niverse)
                  (filter (not.any(`elem`chosen)) availableRows)
  ]