[Question]
  [
In the game of sudoku, many players like to "pencil in" possible numbers that can go in each square:
[![Sudoku row](https://i.stack.imgur.com/6RQ7U.png)](https://i.stack.imgur.com/6RQ7U.png)
The above row can be represented as an array:
```
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]
```
Now, notice that there is only 1 place where a `4` can go. This effectively lets us simplify the above list to:
```
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]
```
**The goal of this challenge is to take a list of possible numbers in a permutation, and deduce which possibilities can be eliminated**.
As another example, lets say you have the following array of possibilities:
```
[[0,1,3], [0,2,3], [1,2], [1,2]]
```
The last two places *must* be filled with 1 and 2. Therefore, we can remove those possibilities from the first two elements in the array:
```
[[0,3], [0,3], [1,2], [1,2]]
```
As another example:
```
[[0,1,2,3], [0,2], [0,2], [0,2]]
```
Its *impossible* to construct a permutation from the above possibilities, as there's only 1 location for both `1` and `3`, and you would want to return an empty array.
**You need to input a list of possibilities and output the remaining possibilities after the maximum number of possibilities have been eliminated.**
* If a particular array is impossible, you either need to return an empty array, or an array where one of the subarrays is empty.
* You may assume that the array will be well-formed, and have at least 1 element.
* Given an array of size `N`, you can assume the numbers in the subarray will always be in the range `[0:N)`, and that `N <= 10`
* You may not assume that every number from `0` to `N-1` will be present
* You may assume that numbers within a single subarray are unique.
* If a subarray contains only a single possibility, you can either represent the possibility in an array or by itself. `[[1],[2],[0]]`, `[1,2,0]`, `[[1,2],0,[1,2]]` are all valid.
* You may accept the array either in a reasonable string format or in list/array format.
* Subarrays can be in any order.
* Instead of dealing with ragged arrays, you can pad empty places with `-1`.
# Test cases
```
[[0]]                                         -> [[0]]
[[1],[0]]                                     -> [[1],[0]]
[[1],[1]]                                     -> []
[[1],[0,1]]                                   -> [[1],[0]]
[[0,1,2],[1,2],[1,2]]                         -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]]                           -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]]                           -> []
[[0,3],[2,1],[3,0],[3,2]]                     -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]]                   -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]]                       -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []
```
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so make your answers as short as possible!
  
[Answer]
# [Brachylog](http://github.com/JCumin/Brachylog), 21 bytes
```
:1fz:da|,[]
:2a#d
:Am
```
[Try it online!](http://brachylog.tryitonline.net/#code=OjFmejpkYXwsW10KOjJhI2QKOkFt&input=W1s4XTpbODowOjY6NTo3OjI6NDoxXTpbODo2Ojk6Mzo1OjA6N106WzM6OToxOjBdOls5XTpbOToyOjZdOlsyOjg6M106WzM6MTo2Ojg6Ml06WzZdOls2OjQ6NTozOjA6N11d&args=Wg&debug=on)
[Try it online!](http://brachylog.tryitonline.net/#code=OjFmejpkYXwsW10KOjJhI2QKOkFt&input=W1s4OjE6MF06WzU6ODo3OjY6MjowXTpbNjo4OjJdOlsyOjQ6MDo5XTpbNDoxOjc6Mzo2OjhdOls4OjFdOls4OjA6M106WzA6ODoyXTpbMDo4OjNdOlsxOjg6MF1d&args=Wg&debug=on)
## 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
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 10 bytes
```
Œp⁼Q$ÐfZQ€
```
[Try it online!](http://jelly.tryitonline.net/#code=xZJw4oG8USTDkGZaUeKCrA&input=&args=W1s4XSxbOCwwLDYsNSw3LDIsNCwxXSxbOCw2LDksMyw1LDAsN10sWzMsOSwxLDBdLFs5XSxbOSwyLDZdLFsyLDgsM10sWzMsMSw2LDgsMl0sWzZdLFs2LDQsNSwzLDAsN11d)
```
Œp⁼Q$ÐfZQ€   Main chain, argument: z
Œp           Cartesian product
  ⁼Q$Ðf      Filter for those that remain unchanged when uniquified
       Z     Transpose
        Q€   Uniquify each subarray
```
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 11 bytes
```
{MC{I#.nM*F
```
[Try it online!](http://pyth.herokuapp.com/?code=%7BMC%7BI%23.nM%2aF&input=%5B%5B8%5D%2C%5B8%2C0%2C6%2C5%2C7%2C2%2C4%2C1%5D%2C%5B8%2C6%2C9%2C3%2C5%2C0%2C7%5D%2C%5B3%2C9%2C1%2C0%5D%2C%5B9%5D%2C%5B9%2C2%2C6%5D%2C%5B2%2C8%2C3%5D%2C%5B3%2C1%2C6%2C8%2C2%5D%2C%5B6%5D%2C%5B6%2C4%2C5%2C3%2C0%2C7%5D%5D&debug=0)
```
{MC{I#.nM*F
         *F  reduce by Cartesian product
             produces nested arrays
      .nM    flatten each
   {I#       filter for invariant under deduplication
  C          transpose
{M           deduplicate each
```
[Answer]
## Haskell, 100 bytes
```
import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]
```
[Answer]
# [Actually](http://github.com/Mego/Seriously), 27 bytes
```
Rd╗R`╜∙"♂i"£M╗`MX╜`;╔=`░┬♂╔
```
[Try it online!](http://actually.tryitonline.net/#code=UmTilZdSYOKVnOKImSLimYJpIsKjTeKVl2BNWOKVnGA74pWUPWDilpHilKzimYLilZQ&input=W1szLDUsMl0sWzAsMiw0XSxbNCwwXSxbMCwxLDMsNV0sWzIsMV0sWzIsNF1d)
[Answer]
# Python 3, ~~101~~ 99 bytes
*Thanks to @TLW for -2 bytes*
```
from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))
```
An anonymous function that takes input via argument of a list of lists and returns a list of sets.
**How it works**
```
from itertools import*        Import Python's library for iterator generation
lambda x                      Anonymous function with input possibilities x as a
                              list of lists
...for i in product(*x)...    For i in the Cartesian product of x, ie all candidate
                              arrangements:
[...if len(i)==len(set(i))]    Filter into list by non-duplicity (set removes
                               duplicates, so there are no duplicates if the length
                               of i is the same as the length of the set of
                               the elements of i)
zip(*...)                     Unpack and take the transpose, leaving the modified
                              possibilities with duplicates
map(set,...)                  Remove duplicates
:list(...)                    Return the modified possibilities as a list of sets
```
[Try it on Ideone](http://ideone.com/RS6smt)
[Answer]
# Mathematica, 46 bytes
```
Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&
```
[Answer]
# PHP, ~~245~~ 231 bytes
~~131~~ 117 for the cartesian product function, 114 for the other stuff
```
function c($a){if ($a){if($u=array_pop($a))foreach(c($a)as$p)foreach($u as$v)yield $p+[count($p)=>$v];}else yield[];}
function p($a){foreach(c($a)as$i)if(max(array_count_values($i))<2)foreach($i as$k=>$v)$r[$k][$v]=$v;return$r?:[];}
```
I ran into memory issues on some of the test cases, with a recursive function for the cartesian product. Worked better with [this generator class](https://gist.github.com/martinezdelariva/621553a2b8bef8cd6f2b/) and `function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}`.  
But [my generator](https://stackoverflow.com/questions/6311779/finding-cartesian-product-with-php-associative-arrays/39174062#39174062) is shorter and does the same job.
The larger examples, however, result in an Internal Server Error (both with the iterator and the generator) after a while on my machine. Currently no time to check the server logs, unfortunately.
]