The Permutation Pigeon-hole Principle
Brachylog, 21 bytes

:1fz:da|,[]
:2a#d
:Am


Try it online!

Try it online!

Predicate 0 (main predicate)

:1fz:da|,[]
:1f            Find all solutions of Predicate 1 using Input as Input.
   z           Transpose
    :da        Deduplicate each.
       |,[]    If there is no solution, return [] instead.


Predicate 1 (auxiliary predicate 1)

:2a#d
:2a     Each element of Output satisfies Predicate 2 with each element of Input as Input
   #d   Each element is different


Predicate 2 (auxiliary predicate 2)

:Am     Output is member of Input