Im Sudoku-Spiel "zeichnen" viele Spieler gerne mögliche Zahlen ein, die in jedes Feld passen:

Die obige Zeile kann als Array dargestellt werden:

[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]

Beachten Sie nun, dass es nur einen Ort gibt, an den ein 4gehen kann. Auf diese Weise können wir die obige Liste effektiv vereinfachen, um:

[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]

Ziel dieser Herausforderung ist es, eine Liste möglicher Zahlen in einer Permutation aufzunehmen und daraus abzuleiten, welche Möglichkeiten beseitigt werden können .

Nehmen wir als weiteres Beispiel an, Sie haben die folgenden Möglichkeiten:

[[0,1,3], [0,2,3], [1,2], [1,2]]

Die letzten beiden Stellen müssen mit 1 und 2 gefüllt sein. Daher können wir diese Möglichkeiten aus den ersten beiden Elementen im Array entfernen:

[[0,3], [0,3], [1,2], [1,2]]

Als weiteres Beispiel:

[[0,1,2,3], [0,2], [0,2], [0,2]]

Es ist unmöglich , eine Permutation aus den oben genannten Möglichkeiten zu konstruieren, da es nur eine Position für beide 1und 3gibt und Sie ein leeres Array zurückgeben möchten.

Sie müssen eine Liste von Möglichkeiten eingeben und die verbleibenden Möglichkeiten ausgeben, nachdem die maximale Anzahl von Möglichkeiten beseitigt wurde.

• Wenn ein bestimmtes Array nicht möglich ist, müssen Sie entweder ein leeres Array oder ein Array zurückgeben, in dem eines der Subarrays leer ist.
• Sie können davon ausgehen, dass das Array wohlgeformt ist und mindestens 1 Element enthält.
• Gegeben eine Reihe von Größe N, können Sie die Zahlen in dem Sub - Array übernehmen werden immer im Bereich [0:N), und dassN <= 10
• Sie können nicht davon ausgehen, dass jede Nummer von 0bis N-1vorhanden sein wird
• Sie können davon ausgehen, dass Zahlen in einem einzelnen Subarray eindeutig sind.
• Wenn ein Subarray nur eine einzige Möglichkeit enthält, können Sie die Möglichkeit entweder in einem Array oder für sich selbst darstellen. [[1],[2],[0]], [1,2,0], [[1,2],0,[1,2]]Sind alle gültig.
• Sie können das Array entweder in einem angemessenen Zeichenfolgenformat oder in einem Listen- / Arrayformat akzeptieren.
• Subarrays können in beliebiger Reihenfolge angeordnet werden.
• Anstatt mit zerlumpten Arrays umzugehen, können Sie leere Stellen mit auffüllen -1.

Testfälle

[[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]] -> []

Dies ist ein Code-Golf, also machen Sie Ihre Antworten so kurz wie möglich!

Brachylog , 21 Bytes

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

Probieren Sie es online!

Probieren Sie es online!

Prädikat 0 (Hauptprädikat)

: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.

Prädikat 1 (Hilfsprädikat 1)

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

Prädikat 2 (Hilfsprädikat 2)

:Am     Output is member of Input

Gelee , 10 Bytes

Œp⁼Q$ÐfZQ€

Probieren Sie es online!

Œ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

Pyth , 11 Bytes

{MC{I#.nM*F

Probieren Sie es online!

{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

Haskell, 100 Bytes

import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]

Eigentlich 27 Bytes

Rd╗R`╜∙"♂i"£M╗`MX╜`;╔=`░┬♂╔

Probieren Sie es online!

Python 3, 101 99 Bytes

Danke an @TLW für -2 Bytes

from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))

Eine anonyme Funktion, die Eingaben über das Argument einer Liste von Listen entgegennimmt und eine Liste von Mengen zurückgibt.

Wie es funktioniert

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

Probieren Sie es auf Ideone

Mathematica, 46 Bytes

Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&

PHP, 245 231 Bytes

131 117 für die kartesische Produktfunktion, 114 für die anderen Sachen

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?:[];}

Bei einigen Testfällen sind Speicherprobleme aufgetreten, und zwar mit einer rekursiven Funktion für das kartesische Produkt. Arbeitete besser mit dieser Generatorklasse und function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}.
Aber mein Generator ist kürzer und macht den gleichen Job.

Die größeren Beispiele führen jedoch nach einer Weile auf meinem Computer zu einem internen Serverfehler (sowohl mit dem Iterator als auch mit dem Generator). Momentan leider keine Zeit die Server Logs zu überprüfen.