Problème

Considérons une grille carrée de 3 x 3 d'entiers non négatifs. Pour chaque ligne, ila somme des entiers est fixée à r_i. De même, pour chaque colonne, jla somme des entiers de cette colonne est définie sur c_j.

La tâche consiste à écrire du code pour énumérer toutes les différentes affectations possibles d'entiers à la grille compte tenu des contraintes de somme des lignes et des colonnes. Votre code doit générer une affectation à la fois.

Contribution

Votre code doit prendre 3 entiers non négatifs spécifiant les contraintes de ligne et 3 entiers non négatifs spécifiant les contraintes de colonne. Vous pouvez supposer que celles-ci sont valides, c'est-à-dire que les contraintes de somme ou de ligne sont égales à la somme des contraintes de colonne. Votre code peut le faire de la manière qui vous convient.

Production

Votre code doit générer les différentes grilles 2D qu'il calcule dans n'importe quel format lisible par l'homme de votre choix. Plus c'est joli, mieux c'est. La sortie ne doit pas contenir de grilles en double.

Exemple

Si toutes les contraintes de ligne et de colonne sont exactement 1alors il n'y a que 6des possibilités différentes. Pour la première ligne, vous pouvez mettre un 1dans l'une des trois premières colonnes, pour la deuxième ligne il y a maintenant des 2alternatives et la dernière ligne est maintenant complètement déterminée par les deux précédentes. Tout le reste de la grille doit être défini sur0 .

Supposons que l'entrée 2 1 0concerne les lignes et 1 1 1les colonnes. En utilisant le joli format de sortie d'APL, les grilles d'entiers possibles sont:

┌─────┬─────┬─────┐
│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│
└─────┴─────┴─────┘

Supposons maintenant que l'entrée 1 2 3concerne les lignes et 3 2 1les colonnes. Les grilles entières possibles sont:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│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 octets

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

Essayez-le en ligne!

Les usages ⎕IO←0 ce qui est par défaut sur de nombreux systèmes. L'autre élément dans l'en-tête est juste une jolie impression pour les matrices (affichage en boîte).

L'entrée est une liste de six valeurs, les sommes des lignes en premier, puis les sommes des colonnes.

Comment?

o←⍳1+⌈/⍵- oobtient la plage 0au maximum ( ⌈/) d'entrée

,o∘.,⊢- produit cartésien avec oet aplatir ( ,)

⍣8 - répété huit fois

3 3∘⍴¨ - façonnez chaque liste de 9 éléments en une matrice 3 × 3

¨o←- enregistrer ces matrices dans o, et pour chaque

+/,+⌿- vérifier si les lignes sommes ( +/) concaténées aux colonnes sommes ( +⌿)

⍵≡ - correspond à l'entrée

o/⍨- filtrer o(le tableau des matrices) par des valeurs véridiques

Coque , 20 17 octets

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

-3 octets grâce à @ H.PWiz

Prend l'entrée comme une liste xscodant les contraintes [r_1,r_2,r_3,c_1,c_2,c_3], essayez-le en ligne!

Explication

Approche par force brute: P Générez toutes les grilles 3x3 avec des entrées [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 octets

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

Essayez-le en ligne!

AVERTISSEMENT: PUISSANT SORTIE!Ne vous inquiétez pas, c'est toujours lisible par l'homme, je ne suis pas obligé de rendre compte de combien. ;)

Pour une raison quelconque, cela doit être beaucoup plus long que ce à quoi je m'attendrais pour avoir du sens (13 octets):

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

Cette dernière version, si elle fonctionnait, aurait plutôt pris l'entrée de la sortie (c'est-à-dire l'argument de ligne de commande).

Python 2 , 149 145 142 141 141 138 136 octets

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*

Essayez-le en ligne!

Prend la saisie sous forme de liste de listes: [[r1, c1], [r2, c2], [r3, c3]]

Haskell, 94 88 84 79 octets

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

Prend les sommes des lignes et des colonnes comme une seule liste plate à 6 éléments [r1,r2,r3,c1,c2,c3].

Essayez-le en ligne!

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

Comme les éléments des matrices à tester atteignent la somme de r, le code ne se termine pas dans un délai raisonnable pour les sommes de lignes / colonnes importantes. Voici une version qui monte au maximum rqui est plus rapide, mais 4 octets de plus: essayez-la en ligne!

Mathematica, 81 octets

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

trouve toutes les matrices 3x3 avec les éléments 0..Max et sélectionne les bonnes,
cela signifie que les (Max+1)^9matrices doivent être vérifiées

Essayez-le en ligne!

R , 115110 octets

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)

Essayez-le en ligne!

Prend l'entrée comme c(r1,r2,r3,c1,c2,c3)un seulvector et imprime les matrices sur la sortie standard.

C'est assez similaire à la réponse APL d' Uriel , mais elle génère les grilles 3x3 quelque peu différemment.

Laissant M=max(S), il génère le vecteur 0:M, puis le repmange 9 fois, soit [0..M, 0...M, ..., 0...M]neuf fois. Ensuite, il sélectionne toutes les combinaisons de ce nouveau vecteur prises 9 à la fois, en utilisant matrix, 3, 3pour convertir chaque combinaison 9 en une 3x3matrice, et en forçant simplify=Fà retourner une liste plutôt qu'un tableau. Il unifie ensuite cette liste et l'enregistre sousm .

Ensuite, il filtre m ceux dont les sommes de ligne / colonne sont identiques à l'entrée, en imprimant celles qui le sont et en ne faisant rien pour celles qui ne le sont pas.

Puisqu'il calcule choose(9*(M+1),9)différentes grilles possibles (plus que les (M+1)^9possibilités), il manquera de mémoire / temps plus rapidement que la réponse plus efficace (mais moins golfique) ci-dessous:

R , 159 octets

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

Essayez-le en ligne!

MATL , 35 22 octets

-13 octets grâce à Luis Mendo

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

Essayez-le en ligne!

Le lien est vers une version du code qui s'imprime un peu mieux; cette version imprimera simplement toutes les matrices avec une seule nouvelle ligne entre elles.

Prend l'entrée comme [c1 c2 c3 r1 r2 r3].

Évidemment, cela calcule la puissance cartésienne X^de l' 0...max(input)exposant 9et de la transposition !. Il boucle ensuite "sur les colonnes, remodelant chacune @comme une matrice 3x33e , les dupliquant t, les transposant !et les concaténant horizontalement h. Ensuite, il calcule les sommes des colonnes s, ce qui donnera le vecteur [c1 c2 c3 r1 r2 r3]. Nous faisons l'égalité élément par élément à l'entrée G=, et si ?tous sont différents de zéro, nous récupérons la matrice correcte en sélectionnant l'entrée de la fonction !à l'aide de 4M.

Lot, 367 octets

@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(

Le carré 2 × 2 en haut à gauche force le résultat, donc la meilleure approche consiste à générer toutes les valeurs pour l'entier supérieur gauche, toutes les valeurs valides pour la somme de l'entier supérieur gauche et supérieur, toutes les valeurs valides pour la somme du haut entier gauche et milieu gauche, puis calculez la plage de valeurs valides pour l'entier central, puis, après avoir parcouru toutes les plages appropriées, calculez les valeurs restantes à partir des contraintes.

Python 2 , 118 octets

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)

Essayez-le en ligne!

Python 2 , 123 octets

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

Essayez-le en ligne!