Enumerate all possible grids of integers with constraints

Question

Problem

Consider a square 3 by 3 grid of non-negative integers. For each row i the sum of the integers is set to be r_i. Similarly for each column j the sum of integers in that column is set to be c_j.

The task is to write code to enumerate all possible different assignments of integers to the grid given the row and column sum constraints. Your code should output one assignment at a time.

Input

Your code should take 3 non-negative integers specifying the row constraints and 3 non-negative integers specifying the column constraints. You can assume that these are valid, i.e. that the sum or row constraints equals the sum of column constraints. Your code can do this in any way that is convenient.

Output

Your code should output the different 2d grids it computes in any human readable format of your choice. The prettier the better of course. The output must not contain duplicate grids.

Example

If all the row and column constraints are exactly 1 then there are only 6 different possibilities. For the first row you can put a 1 in any of the first three columns, for the second row there are now 2 alternatives and the last row is now completely determined by the previous two. Everything else in the grid should be set to 0.

Say the input is 2 1 0 for the rows and 1 1 1 for the columns. Using APL's lovely output format, the possible integers grids are:

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

Now say the input is 1 2 3 for the rows and 3 2 1 for the columns. The possible integer grids are:

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

Answer 1

APL (Dyalog), 42 bytes

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

Try it online!

Uses ⎕IO←0 which is default on many systems. The other stuff in the header is just pretty printing for the matrices (boxed display).

Input is list of six values, rows sums first, then column sums.

How?

o←⍳1+⌈/⍵ - o gets the range 0 to the maximum (⌈/) of input

,o∘.,⊢ - cartesian product with o and flatten (,)

⍣8 - repeated for eight times

3 3∘⍴¨ - shape every 9-items list into a 3×3 matrix

¨o← - save these matrices to o, and for each

+/,+⌿ - check if the rows sums (+/) concatenated to the column sums (+⌿)

⍵≡ - correspond with the input

o/⍨ - filter o (the matrices array) by truthy values

Answer 2

Husk, 20 17 bytes

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

-3 bytes thanks to @H.PWiz

Takes input as a list xs encoding the constraints [r_1,r_2,r_3,c_1,c_2,c_3], try it online!

Explanation

Brute force approach :P Generate all 3x3 grids with entries [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

Answer 3

Brachylog, 17 bytes

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

Try it online!

WARNING: UGLY OUTPUT! Don't frick out, it's still human-readable, I'm not required to account for how much. ;)

For some reason it has to be much longer than what I'd expect to make sense (13 bytes):

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

This latter version, if it worked, would have taken input from the output (i.e. command-line argument) instead.

Answer 4

Python 2, 149 145 142 141 138 136 bytes

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*

Try it online!

Takes input as a list of lists: [[r1, c1], [r2, c2], [r3, c3]]

Answer 5

Haskell, 94 88 84 79 bytes

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

Takes the sums of the rows and columns as a single flat 6-element list [r1,r2,r3,c1,c2,c3].

Try it 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

As the elements of the matrices to test go up to the sum of r, the code does not finish in reasonable time for large row/column sums. Here's a version that goes up to the maximum of r which is faster, but 4 bytes longer: Try it online!

Answer 6

Mathematica, 81 bytes

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

finds all 3x3 matrices with elements 0..Max and selects the right ones
this means that (Max+1)^9 matrices have to be checked

Try it online!

Answer 7

R, 115 110 bytes

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)

Try it online!

Takes input as c(r1,r2,r3,c1,c2,c3), a single vector, and prints the matrices to stdout.

It's quite similar to Uriel's APL answer, but it generates the 3x3 grids somewhat differently.

Letting M=max(S), it generates the vector 0:M, then repeats it 9 times, i.e., [0..M, 0...M, ..., 0...M] nine times. Then it selects all combinations of that new vector taken 9 at a time, using matrix, 3, 3 to convert each 9-combination into a 3x3 matrix, and forcing simplify=F to return a list rather than an array. It then uniquifies this list and saves it as m.

Then it filters m for those where row/column sums are identical to the input, printing those that are and doing nothing for those that aren't.

Since it computes choose(9*(M+1),9) different possible grids (more than the (M+1)^9 possibilities), it'll run out of memory/time faster than the more efficient (but less golfy) answer below:

R, 159 bytes

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

Try it online!

Answer 8

MATL, 35 22 bytes

-13 bytes thanks to Luis Mendo

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

Try it online!

Link is to a version of the code that prints a little more nicely; this version will just print all the matrices with a single newline between them.

Takes input as [c1 c2 c3 r1 r2 r3].

Obviously, this computes the cartesian power X^ of 0...max(input) with exponent 9, and transposing !. It then loops " over the columns, reshaping each @ as a 3x3 matrix 3e, duplicating t, transposing !, and horizontally concatenating them h. Then it computes the column sums s, which will result in the vector [c1 c2 c3 r1 r2 r3]. We do elementwise equality to the input G=, and if ? all are nonzero, we recover the correct matrix by selecting the input to the function ! by using 4M.

Answer 9

Batch, 367 bytes

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

The top left 2×2 square forces the result, so the best approach is to generate all values for the top left integer, all valid values for the sum of the top left and top middle integer, all valid values for the sum of the top left and middle left integer, and calculate the range of valid values for the middle integer, then, having looped through all the appropriate ranges, calculate the remaining values from the constraints.

Answer 10

Python 2, 118 bytes

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)

Try it online!

---

Python 2, 123 bytes

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

Try it online!