Problem

Rozważ kwadratową siatkę 3 na 3 liczb całkowitych nieujemnych. Dla każdego wiersza iustawiana jest suma liczb całkowitych r_i. Podobnie dla każdej kolumny justawiana jest suma liczb całkowitych w tej kolumnie c_j.

Zadanie polega na napisaniu kodu wyliczającego wszystkie możliwe różne liczby całkowite do siatki, biorąc pod uwagę ograniczenia sumy wierszy i kolumn. Twój kod powinien wyświetlać jedno zadanie na raz.

Wejście

Twój kod powinien przyjąć 3 nieujemne liczby całkowite określające ograniczenia wiersza i 3 nieujemne liczby całkowite określające ograniczenia kolumny. Możesz założyć, że są one poprawne, tzn. Że ograniczenia sumy lub wiersza są równe sumie ograniczeń kolumny. Twój kod może to zrobić w dowolny dogodny sposób.

Wynik

Twój kod powinien wypisywać różne siatki 2D, które oblicza, w dowolnym formacie czytelnym dla człowieka. Im ładniejsza, tym lepiej. Dane wyjściowe nie mogą zawierać zduplikowanych siatek.

Przykład

Jeśli wszystkie ograniczenia wierszy i kolumn są dokładnie takie same, 1istnieją tylko 6inne możliwości. W pierwszym rzędzie możesz umieścić a 1w dowolnej z pierwszych trzech kolumn, w drugim rzędzie są teraz 2alternatywy, a ostatni rząd jest teraz całkowicie określony przez poprzednie dwa. Wszystko inne w siatce powinno być ustawione na 0.

Powiedzmy, że dane wejściowe dotyczą 2 1 0wierszy i 1 1 1kolumn. Używając pięknego formatu wyjściowego APL, możliwe są następujące liczby całkowite:

┌─────┬─────┬─────┐
│0 1 1│1 0 1│1 1 0│
│1 0 0│0 1 0│0 0 1│
│0 0 0│0 0 0│0 0 0│
└─────┴─────┴─────┘

Powiedzmy teraz, że dane wejściowe dotyczą 1 2 3wierszy i 3 2 1kolumn. Możliwe siatki liczb całkowitych to:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 1│0 0 1│0 0 1│0 1 0│0 1 0│0 1 0│0 1 0│1 0 0│1 0 0│1 0 0│1 0 0│1 0 0│
│0 2 0│1 1 0│2 0 0│0 1 1│1 0 1│1 1 0│2 0 0│0 1 1│0 2 0│1 0 1│1 1 0│2 0 0│
│3 0 0│2 1 0│1 2 0│3 0 0│2 1 0│2 0 1│1 1 1│2 1 0│2 0 1│1 2 0│1 1 1│0 2 1│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

APL (Dyalog) , 42 bajty

{o/⍨(⍵≡+/,+⌿)¨o←3 3∘⍴¨(,o∘.,⊢)⍣8⊢o←⍳1+⌈/⍵}

Wypróbuj online!

Używa ⎕IO←0ustawień domyślnych w wielu systemach. Inne elementy w nagłówku to po prostu drukowanie matryc (wyświetlanie w ramkach).

Dane wejściowe to lista sześciu wartości, najpierw sumy wierszy, a następnie sumy kolumn.

W jaki sposób?

o←⍳1+⌈/⍵- opobiera zakres 0do maksimum ( ⌈/) wejścia

,o∘.,⊢- produkt kartezjański zi ospłaszczony ( ,)

⍣8 - powtarzane osiem razy

3 3∘⍴¨ - uformuj każdą listę 9-elementową w matrycę 3 × 3

¨o←- zapisz te macierze oi dla każdego

+/,+⌿- sprawdź, czy sumy wierszy ( +/) są połączone z sumami kolumn ( +⌿)

⍵≡ - korespondują z danymi wejściowymi

o/⍨- filtruj o(tablica macierzy) według prawdziwych wartości

Łuska , 20 17 bajtów

fȯ=⁰mΣS+Tπ3π3Θḣ▲⁰

-3 bajty dzięki @ H.PWiz

Pobiera dane wejściowe jako listę xskodującą ograniczenia [r_1,r_2,r_3,c_1,c_2,c_3], spróbuj online!

Wyjaśnienie

Podejście brutalnej siły: P Wygeneruj wszystkie siatki 3x3 z wpisami [0..max xs]:

f(=⁰mΣS+T)π3π3Θḣ▲⁰  -- input ⁰, for example: [1,1,1,1,1,1]
                ▲⁰  -- max of all constraints: 1
               ḣ    -- range [1..max]: [1]
              Θ     -- prepend 0: [0,1]
            π3      -- 3d cartesian power: [[0,0,0],...,[1,1,1]]
          π3        -- 3d cartesian power: list of all 3x3 matrices with entries [0..max] (too many)
f(       )          -- filter by the following predicate (eg. on [[0,0,1],[1,0,0],[0,1,0]]):
      S+            --   append to itself, itself..: [[0,0,1],[1,0,0],[0,1,0],..
        T           --   .. transposed:             ..[0,1,0],[0,0,1],[1,0,0]]
      mΣ            --   map sum: [1,1,1,1,1,1]
    =⁰              --   is it equal to the input: 1

Brachylog , 17 bajtów

{~⟨ṁ₃{ℕᵐ+}ᵐ²\⟩≜}ᶠ

Wypróbuj online!

OSTRZEŻENIE: Brzydkie wyjście! Nie szukaj, to wciąż jest czytelne dla człowieka, nie muszę rozliczać się z tego, ile. ;)

Z jakiegoś powodu musi być znacznie dłuższy niż to, co miałbym sens (13 bajtów):

⟨ṁ₃{ℕᵐ+}ᵐ²\⟩ᶠ

Ta ostatnia wersja, jeśli zadziała, pobierałaby dane wejściowe z danych wyjściowych (tj. Argument wiersza poleceń).

Python 2 , 149 145 142 141 138 136 bajtów

lambda s:[i for i in product(range(max(sum(s,[]))+1),repeat=9)if[map(sum,(i[j:j+3],i[j/3::3]))for j in 0,3,6]==s]
from itertools import*

Wypróbuj online!

Pobiera dane wejściowe jako listę list: [[r1, c1], [r2, c2], [r3, c3]]

Haskell, 94 88 84 79 bajtów

q=mapM id.(<$"abc")
f r=[k|k<-q$q$[0..sum r],(sum<$>k)++foldr1(zipWith(+))k==r]

Sumuje wiersze i kolumny jako pojedynczą płaską 6-elementową listę [r1,r2,r3,c1,c2,c3].

Wypróbuj online!

q=mapM id.(<$"abc")         -- helper function 

f r =                       -- 
  [k | k <-   ,    ]        -- keep all k
    q$q$[0..sum r]          --   from the list of all possible matrices with
                            --   elements from 0 to the sum of r
                            -- where
    (sum<$>k) ++            --   the list of sums of the rows followed by
    foldr1(zipWith(+))k     --   the list of sums of the columns
    == r                    -- equals the input r

Ponieważ elementy testowanych macierzy dochodzą do sumy r, kod nie kończy się w rozsądnym czasie dla dużych sum wierszy / kolumn. Oto wersja, która zwiększa się do maksimum, rjest szybsza, ale o 4 bajty dłuższa: Wypróbuj online!

Mathematica, 81 bajtów

Select[0~Range~Max[s=#,t=#2]~g~3~(g=Tuples)~3,(T=Total)@#==s&&T@Transpose@#==t&]&

znajduje wszystkie macierze 3x3 z elementami 0..Max i wybiera odpowiednie,
co oznacza, że (Max+1)^9macierze muszą zostać sprawdzone

Wypróbuj online!

R , 115 110 bajtów

function(S)for(m in unique(combn(rep(0:max(S),9),9,matrix,F,3,3)))if(all(c(rowSums(m),colSums(m))==S))print(m)

Wypróbuj online!

Pobiera dane wejściowe jako c(r1,r2,r3,c1,c2,c3)pojedynczy vectori wypisuje macierze na standardowe wyjście.

Jest dość podobny do odpowiedzi APL Uriela , ale generuje siatki 3x3 nieco inaczej.

Pozwalając M=max(S), generuje wektor 0:M, a następnie repje 9 razy, czyli [0..M, 0...M, ..., 0...M]dziewięć razy. Następnie wybiera wszystkie kombinacje tego nowego wektora pobranego 9 na raz, używając matrix, 3, 3do konwersji każdej 9 kombinacji na 3x3macierz i zmuszając simplify=Fdo zwrócenia listy zamiast tablicy. Następnie ujednolica tę listę i zapisuje ją jako m.

Następnie filtruje mte, w których sumy wierszy / kolumn są identyczne z danymi wejściowymi, drukując te, które są, i nie robiąc nic dla tych, które nie są.

Ponieważ oblicza choose(9*(M+1),9)różne możliwe siatki (więcej niż (M+1)^9możliwości), zabraknie pamięci / czasu szybciej niż bardziej wydajna (ale mniej golfowa) odpowiedź poniżej:

R , 159 bajtów

function(S,K=t(t(expand.grid(rep(list(0:max(S)),9)))))(m=lapply(1:nrow(K),function(x)matrix(K[x,],3,3)))[sapply(m,function(x)all(c(rowSums(x),colSums(x))==S))]

Wypróbuj online!

MATL , 35 22 bajtów

-13 bajtów dzięki Luisowi Mendo

X>Q:q9Z^!"@3et!hsG=?4M

Wypróbuj online!

Link jest wersją kodu, która drukuje się trochę ładniej; ta wersja po prostu wydrukuje wszystkie macierze z jedną nową linią między nimi.

Pobiera dane wejściowe jako [c1 c2 c3 r1 r2 r3].

Oczywiście, to oblicza kartezjański moc X^o 0...max(input)z wykładnikiem 9i transpozycji !. Następnie zapętla się "nad kolumnami, przekształcając każdą z nich @w matrycę 3x3 3e, kopiując t, transponując !i konkatenując w poziomie h. Następnie oblicza sumy kolumn s, co da wektor [c1 c2 c3 r1 r2 r3]. Robimy elementarną równość względem danych wejściowych G=, a jeśli ?wszystkie są niezerowe, odzyskujemy prawidłową macierz, wybierając dane wejściowe do funkcji !za pomocą 4M.

Partia, 367 bajtów

@echo off
for /l %%i in (0,1,%1)do for /l %%j in (%%i,1,%1)do for /l %%k in (%%i,1,%4)do call:c %* %%i %%j %%k
exit/b
:c
set/a"a=%1-%8,c=%4-%9,f=%8-%7,g=%9-%7,l=%5-f,m=%2-g,l^=m-l>>31&(m^l),m=%5+c-%3-f,m&=~m>>31
for /l %%l in (%m%,1,%l%)do set/a"b=%2-g-%%l,d=%5-f-%%l,e=%6-a-b"&call:l %7 %%l
exit/b
:l
echo %1 %f% %a%
echo %g% %2 %b%
echo %c% %d% %e%
echo(

Lewy górny kwadrat 2 × 2 wymusza wynik, więc najlepszym podejściem jest wygenerowanie wszystkich wartości dla lewej górnej liczby całkowitej, wszystkich prawidłowych wartości dla sumy lewej górnej i górnej środkowej liczby całkowitej, wszystkich prawidłowych wartości dla sumy górnej lewą i środkową lewą liczbą całkowitą i oblicz zakres prawidłowych wartości dla środkowej liczby całkowitej, a następnie, po przejściu przez wszystkie odpowiednie zakresy, oblicz pozostałe wartości z ograniczeń.

Python 2 , 118 bajtów

def f(v,l=[],i=0):n=len(l);V=v*1;V[~n/3]-=i;V[n%3]-=i;return[l][any(V):]if n>8else V*-~min(V)and f(V,l+[i])+f(v,l,i+1)

Wypróbuj online!

Python 2 , 123 bajty

V=input()
n=max(V)+1
for k in range(n**9):
 m=[];exec"m+=[k%n,k/n%n,k/n/n%n],;k/=n**3;"*3
 if map(sum,m+zip(*m))==V:print m

Wypróbuj online!