Summon the sevens

Question

You are given a \$3\times3\$ square matrix where each cell is any digit between \$0\$ and \$9\$ except \$7\$. Your task is to figure out the minimum number of digits that must be replaced with \$7\$'s so that the sums of the digits in each row and each column are the same.

NB: There is no constraint whatsoever on the diagonals, so we end up with a semi-magical square.

Examples

Here is a matrix where three digits need to be turned into \$7\$'s so that all sums are \$20\$:

$$\begin{pmatrix}8&6&6\\1&5&8\\6&9&5\end{pmatrix}\rightarrow\begin{pmatrix}\color{red}7&6&\color{red}7\\\color{red}7&5&8\\6&9&5\end{pmatrix}$$

In this one, only one digit needs to be replaced with a \$7\$ so that all sums are \$13\$:

$$\begin{pmatrix}9&2&2\\0&9&4\\4&2&9\end{pmatrix}\rightarrow\begin{pmatrix}9&2&2\\0&9&4\\4&2&\color{red}7\end{pmatrix}$$

And for this one, our only option is to replace all digits with \$7\$'s:

$$\begin{pmatrix}0&6&8\\3&6&1\\8&4&0\end{pmatrix}\rightarrow\begin{pmatrix}\color{red}7&\color{red}7&\color{red}7\\\color{red}7&\color{red}7&\color{red}7\\\color{red}7&\color{red}7&\color{red}7\end{pmatrix}$$

So the expected outputs for the above examples are \$3\$, \$1\$ and \$9\$ respectively.

Rules

• Because the size of the matrix is fixed, you may take input as a flattened array or 9 distinct arguments.
• Because we're dealing with digits exclusively, you may also take a string of 9 characters.
• The input matrix may already fulfill the sum constraints, in which case the expected answer is \$0\$.
• This is code-golf.

Test cases

[[9,4,3],[3,4,9],[4,8,4]] -> 0
[[5,1,3],[3,1,5],[1,2,1]] -> 1
[[3,9,6],[8,5,5],[8,4,0]] -> 2
[[5,3,5],[1,9,5],[3,3,3]] -> 2
[[8,3,0],[8,0,8],[0,8,4]] -> 3
[[1,5,2],[5,9,5],[6,5,3]] -> 4
[[3,0,8],[1,8,0],[1,3,8]] -> 4
[[3,3,0],[5,1,9],[9,9,5]] -> 5
[[2,4,5],[5,3,4],[4,4,8]] -> 6
[[3,0,3],[8,3,5],[8,3,4]] -> 9

Answer 1

Brachylog, 29 bytes

∧ℕ≜.&{|∧7}ᵐ²{+ᵛS&\+ᵛS&c{7}ˢl}

Try it online!

Or the much faster version with the last two constraint flipped for +2 bytes:

∧ℕ≜.&{|∧7}ᵐ²{c{7}ˢl.&+ᵛS&\+ᵛS∧}

Try it online!

A problem for Brachylog is that the usual way to try the different 7s {|∧7}² would lead to the following search sequence:

[[5,3,5],[1,9,5],[3,3,3]]
[[5,3,5],[1,9,5],[3,3,7]]
[[5,3,5],[1,9,5],[3,7,3]]
[[5,3,5],[1,9,5],[3,7,7]]

so it would try two 7s before every possible one 7. So we could either just try them all, sort them, and be happy. Or we do something more fancy:

• ∧ℕ≜. we try a natural number (starting with 0). This will be our output .. Also we label it ≜. So instead of back-unification ("later the square has two 7s, so the output must have been 2"), we already fix the value of the output.
• {|∧7}ᵐ² for every value in the square: try it unmodified or replaced by a 7.
• c{7}ˢl all digits concatenated, with only the 7s selected, have the length equal to the output.
• +ᵛS&\+ᵛS the sum of each row must unify with the sum of each column.

Answer 2

R, 131 130 118 113 bytes

Edit: -1 byte thanks to pajonk, and -4 bytes thanks to Giuseppe, which led to another -1 byte too.

function(x,`-`=rowSums,j=expand.grid(rep(list(0:1),9)))min(-j[apply(j,1,function(k)!sd(c(-t(m<-7*k+x*!k),-m))),])

Try it online!

How?
j=expand.grid(rep(list(0:1),9)) generates a matrix j with 512 rows, corresponding to all possible placements of 7s in a 9-element matrix.
We then apply the function !sd(c(-t(m<-7*k+x*!k),-m)) to each row, to determine which ones would yield a semi-magic square if 7s were placed at those positions in the input matrix x.
From these rows, output the minimum row sum, which was the number of 7s we needed to place.

(Note that for golfing motives, the short - operator is re-assigned to the longer-named rowSums function to save bytes, making the code a little difficult to read...)

Answer 3

Jelly, 19 bytes

JŒPµ³7⁸¦s3§;SEƲµƇḢL

Try it online!

Takes a flattened list.

Unfortunately, it's not possible to test this with all test cases at once because it uses ³.

Explanation

JŒPµ³7⁸¦s3§;SEƲµƇḢL   Main monadic link
J                     Indices ([1..9])
 ŒP                   Power set, ordered by length
                Ƈ     Filter by
   µ                  (
    ³                   The input
       ¦                At indices
      ⁸                   given by the argument,
     7                    replace the element with a 7
        s3              Split into groups of 3
              Ʋ         (
          §               Sum of each row
           ;              Join with
            S               Sum of rows (i.e. sum of each column)
             E            All equal?
              Ʋ         )
               µ      )
                 Ḣ    First element
                  L   Length

Answer 4

Haskell, 157 143 136 134 132 bytes

f z=minimum[sum[1|7<-v]|v<-foldr((<*>).(:[(7:)]).(:))[[]]z,e[sum$(v!!).((4-d)*x+).(d*)<$>l|d<-[1,3],x<-l]]
l=[0..2]
e(x:z)=all(x==)z

Try it online!

Takes a flat list of nine numbers.

Shortened by 11 bytes thanks to ovs (143 should have been 147).

Shortened additionally by 4 bytes.

Explanation

f z=minimum[sum[1|7<-v]|              -- count 7s for all solutions and take minimum
  v<-foldr((<*>).(:[(7:)]).(:))[[]]z, -- generate squares with all possible substitutions
  e                                   -- all sums must be equal
    [sum$                             -- compute sums of rows and columns
      (v!!).((4-d)*x+).(d*)<$>l|      -- transform [0..2] to index list and apply to v
        d<-[1,3],x<-l]]               -- parameters for index lists
l=[0..2]                              -- abbreviation, used in two places
e(x:z)=all(x==)z                      -- check whether all numbers in list are equal

Answer 5

Python 3.8 (pre-release), 159 152 140 bytes

-7 bytes thanks to Donat
-4 bytes thanks to Donat

lambda l:min(i.count(7)for j in range(512)if 2>len({sum((i:=[(7,L)[M<'1']for L,M in zip(l,f'{j:9b}')])[k%7::k//6])for k in[-5,6,21,22,23]}))

Try it online!

Takes input as a flat list. Solves by brute-forcing each possible set of 7's. When checking the sums of rows/columns, skips the last row.

f=lambda l:                     # l is flat list (9 elements)
  min(                          #
    i.count(7)                  # what we're trying to minimize (the number of 7's used)
    for j in range(512)         # 512=2^9
    if 2>len({                  # check if the len of the set of row/column sums is 1 (it's at least 1 for sure)
      sum(                      # get the sum of a row/column
        (i:=[(7,L)[M<'1']       # Choose the original number or 7 based on whether the binary digit is 1
                                #     (the alternative for the digit is ' ' or '0', which are both < '1')
          for L,M in zip(l,     # 
            f'{j:9b}')])        # gets length 9 binary string
        [k%7::k//6])            # Slice the array to get a row or column
      for k in                  #
      [-5,6,21,22,23]}))        # corresponding slices are i[2::-1] i[6::1] i[0::3] i[1::3] i[2::3]

Answer 6

Java, 257 246 210 200 195 190 188 186 181 bytes

a->{int r=9,i=512,j,e,s,k,x,z,b,c=9;for(;i-->0;r=e!=0|r<c?r:c)for(j=s=e=0;j<3;s=j++<1?x:s,e|=x-s)for(k=x=c=0;k<9;z=b>0?7:a[k],x+=k/3==j?z:0,x+=k++%3==j?30*z:0)c+=b=i>>k&1;return r;}

Saved 11 bytes thanks to ceilingcat.

Saved 46 bytes thanks to Olivier Grégoire.

Saved 19 bytes thanks to Donat.

Takes a flat array as input. This method tries all 512 (2⁹) possibilities by using the binary representations of the integers from 0 to 511. On each iteration, it sets the values at all indexes where i has a set bit to 7. Then, it checks if the current array is valid, in which case the answer is updated.

Try it online!

Answer 7

MATL, 23 bytes

nW:qB!"G7@(t!hsd~?@svX<

Try it online! Or verify all test cases.

Explanation

n         % Implicit input. Number of elements: gives 9
W         % 2 raised to that
:q        % Range, minus 1 element-wise. Gives the 1×512 vector [0 1 2 ... 511]     
B!        % Binary, transpose. Gives a 9×512 matrix where each colum is the binary
          % expansion of a number in the above vector
"         % For each column, c (9×1 vector of zeros and ones)
  G       %   Push input
  7       %   Push 7
  @       %   Push current c
  (       %   Write 7 in the input at the entries specified by ones in c
  t!h     %   Duplicate, transpose, concatenate horizontally. Gives a 3×6 matrix
  s       %   Sum of each column
  d~      %   Consecutive differences, negate. Gives a 1×5 vector containing zeros
          %   and ones. If all values are one we have found a solution
  ?       %   If all entries are nonzero
    @s    %     Push c, sum. This is the number of sevens that were written
    vX<   %     Concatenate with any previous results and take the minimum
          %   End (implicit)
          % End (implicit)
          % Display (implicit)

Answer 8

Charcoal, 48 bytes

Ｆφ«≔⭆θ⎇＆ιＸ²λ7κη≔⁺⪪η³Ｅ³⭆⪪糧μκζ≦Σζ¿⁼⌈ζ⌊ζ⊞υ№η7»Ｉ⌊υ

Try it online! Link is to verbose version of code. Takes input as a string of 9 digits. Explanation:

Ｆφ«

Loop over all possible replacements of digits with 7, and then some.

≔⭆θ⎇＆ιＸ²λ7κη

Get the next possible replacement of digits with 7.

≔⁺⪪η³Ｅ³⭆⪪糧μκζ

Split into rows and concatenate with the transpose.

≦Σζ

Sum the rows and columns.

¿⁼⌈ζ⌊ζ

If they are all the same, then...

⊞υ№η7

... save the number of 7s.

»Ｉ⌊υ

Print the minimum number of 7s required.

Answer 9

Retina 0.8.2, 97 bytes

^
:
+`:(.)
$1:$%'¶$%`7:
%(`:
$`$`
6`...
$&¶
8O$#`.
$.%`
18`.
$*
)`¶
,
G`\b(1+,)\1{5}
%M`7
O`.
¶.

Try it online! Takes input as a string of 9 digits, but link includes test suite that splits on newlines and deletes non-digits for convenience. Explanation:

^
:
+`:(.)
$1:$%'¶$%`7:

Create all possible combinations of replacing a digit with a 7.

%(`
)`

Process each combination separately.

:
$`$`

Triplicate the string of digits.

6`...
$&¶

Split the first two copies into rows.

8O$#`.
$.%`

Transpose the first three columns into rows.

18`.
$*

Take the sum of each column or row.

¶
,

Concatenate the results.

G`\b(1+,)\1{5}

Keep only those that are semimagic.

%M`7

Count the number of 7s used.

O`.

Sort by number of 7s used.

¶.

Keep only the smallest number of 7s used.

Answer 10

Pyth, 23 bytes

lhf!t{ssMMCBc:JQT7 3yU9

Test suite

Takes input as a flattened list.

Translation of xigoi's Jelly answer.

Answer 11

Python 3, ^{200 \$\cdots\$ 183} 181 bytes

def f(a,R=range):
 for b,n in sorted((bin(i).count('1'),i)for i in R(512)):
  c=[[a[i],7][n>>i&1]for i in R(9)]
  if len({(sum(c[3*i:3*i+3]),sum(c[i:9:3]))for i in R(3)})<2:return b

Try it online!

Inputs a flat list of \$9\$ integers and returns the minimum number of elements that must be replaced with \$7\$s so that the sums of the rows and columns of the corresponding \$3\times3\$ matrix are the same.

Answer 12

Ruby, 126 123 116 bytes

->m{(0..510).map{|x|[120,345,678,360,147,258].map{|a|a.digits.sum{|z|x[z]>0?7:m[z]}}.uniq[1]?9:x.digits(2).sum}.min}

Try it online!

Answer 13

Wolfram Language (Mathematica), 84 bytes

q0//.k_/;!Or@@(Equal@@Tr/@Join[w=MapAt[7&,q,#],w]&/@{1,2,3}~Tuples~{k,2}):>k+1

Try it online!

-30 bytes from @att

Answer 14

JavaScript (Node.js), 151 148 145 142 140 bytes

a=>{r=9;for(i=512;i--;r=e|r<c?r:c)for(j=e=0;j<3;a.map((z,k)=>x+=(i>>k&1&&++c?7:z)*(!(~~(k/3)-j)+30*!(k%3-j))),j++?e|=x-s:s=x)c=x=0;return r}

Try it online!

2 byte reduced thanks to Arnauld

Explanation:

a=>{r=9;                 // initial value for minimum
for(i=512;i--;           // i is a bitmask for indexes to replace by 7
 r=e|r<c?r:c)            // minimum of valid squares, e is false if valid
  for(j=e=0;j<3;         // for three rows/columns
   a.map((z,k)=>         // body: compute sum(row) + 30*sum(column)
    x+=                  // current partial sum
      (i>>k&1&&++c?7:z)* // number in current cell, maybe replaced by 7
                         // ++c is always true, here only for counting 7s
      (!(~~(k/3)-j)+     // 1 for current row, else 0
       30*!(k%3-j))),    // 30 for current column, else 0
   j++?e|=x-s:s=x)       // compare sums (s is sum in first iteration)
  c=x=0;                 // initialize number of 7s and sums
return r}                // result

Note: We compare the sums of rows and columns only separately. But if the sums of all rows are equal and the sums of all columns are equal, they must be all equal to each other. The sum of the sums of all rows equals the sum of the sums of all columns.

Answer 15

APL(Dyalog Unicode), 53 bytes ^SBCS

⌊/+/¨7=,¨a/⍨1=≢¨(∪+/,+⌿)¨a←⎕∘{3 3⍴7@(⍸⍵⊤⍨9/2)⊢⍺}¨⍳512

Try it on APLgolf!

A tradfn submission which takes a flat array as input from STDIN.

loops over 512 combinations and finds the minimum.

Answer 16

Stax, 25 bytes

ü+üF∙░╔┴!╜U╙],wøT╥B╠╓l6â°

Run and debug it

yet another powerset answer

Answer 17

JavaScript (Node.js), 152 bytes

p=(m,l=0)=>(q=l=>([a,b,c,d,e,f,g,h,i]=m,l)?m.some((v,j)=>q(l-1,m[j]=7)||(m[j]=v,0)):new Set([a+b+c,d+e+f,g+h+i,a+d+g,b+e+h,c+f+i]).size<2)(l)?l:p(m,l+1)

Try it online!

Take input as a flatten array.

Answer 18

JavaScript (Node.js), 152 bytes

f=(a,m)=>[b=0,1].map(d=>a.map((r,i)=>b|=r.map((n,j)=>s+=d?n:a[j][i],s=0)|1<<s))|b&b-1&&a.map(r=>r.map((n,x)=>r[n-7&&(r[x]=7,v=f(a),v>m?0:m=v),x]=n))|m+1

-8 bytes thanks to @Arnauld!

Try it online!

Takes a matrix of numbers.

Answer 19

Perl 5, 138 bytes

sub{(sort map{$i=$_;%e=map{//;$c=$x=$k=0;$x+=($i>>$k&1&&++$c?7:$_)*(!(~~($k/3)-$')+30*!($k++%3-$'))for@_;($x,1)}0..2;%e>1?9:$c}0..511)[0]}

Try it online!

Answer 20

Wolfram Language (Mathematica), 73 bytes

lMin[Pick[#~t~2,t[w=l+7#-l#]⋃t/@w,{_}]&/@{0,1}~Tuples~{3,3}]
t=Total

Try it online!

Input a 3x3 matrix.

Answer 21

Haskell, ¹⁰⁰ 95 bytes

• -5 bytes thanks to Donat.

f m=minimum[sum[1|7<-n]|n<-g m,a$sum.(g n!!)<$>[7,56,73,146,448]]
g=mapM(:[7])
a(x:y)=all(==x)y

Try it online!

The relevant function is f, which takes the flattened matrix m as input as list of Int's.

How?

The real star of this answer is g=mapM(:[7]). What is this Haskell magic? Let's start by describing what mapM does. mapM takes as input a function f::a->[b] and a list l::[a], applies f to every element of l (thus obtaining a list of lists ::[[b]]), and then returns the cartesian product of these lists. To get a better intuition, consider what happens when we call mapM(:[7])[2,3,4]. First we apply (:[7]) to each element of [2,3], getting [[2,7],[3,7],[4,7]] as a result; then we take the cartesian product, resulting in

[[2,3,4],[2,3,7],[2,7,4],[2,7,7],[7,3,4],[7,3,7],[7,7,4],[7,7,7]]

It should be clear from this example that the function g, applied to a list l, returns all the lists that can be obtained from l by replacing some elements with a 7. Unsurprisingly, this is exactly what we need for the first step of the solution (i.e. applying g to the flattened input matrix m); however, a bit more surprisingly, the function g will also come in handy later.

---

Now that we know how to summon the sevens, we need a way to check if the rows and columns of a given matrix all have the same sum. Dealing with row/column sums in a flattened matrix can be surprisingly cumbersome in Haskell, so we'll have to be somewhat creative. The relevant piece of code is

a$sum.(g n!!)<$>[7,56,73,146,448]

a is simply a function to check whether all the elements of a list are the same (defined later as a(x:y)=all(==x)y, not particularly exciting). The interesting part of the code is

a$sum.(g n!!)<$>[7,56,73,146,448]

, which is basically finding the sum of some specific lists in g n (namely, the one in position 7, the one in position 56 and so on). What's so special about these positions? Assuming n≡[n0,n1,...,n7,n8], the 7-th element of g n is [n0,n1,n2,n3,n4,n5,7,7,7]. Similarly, here is a list of the elements of g n we are considering.

i	i-th element of g n
7	[n0,n1,n2,n3,n4,n5,7 ,7 ,7 ]
56	[n0,n1,n2,7 ,7 ,7 ,n6,n7,n8]
73	[n0,n1,7 ,n3,n4,7 ,n6,n7,7 ]
146	[n0,7 ,n2,n3,7 ,n5,n6,7 ,n8]
448	[7 ,7 ,7 ,n3,n4,n5,n6,n7,n8]

With some algebra, it's easy to see that the sums of these five lists are all equal if and only if the sums of all the rows and columns of n are equal.

---

Sorry, the clever part is over, the definition of f is moderately boring.

f m=                                    -- f is a function that takes a flattened matrix m
    minimum[                            -- and returns the minimum of
    sum[1|7<-n]|                        -- the numbers of 7's in n (sum 1 for each 7 in n), where
    n<-g m,                             -- n is an element of g m
    a$sum.(g n!!).fromEnum<$>"?ÛŭƶLJǸ"]  -- all the sums of rows and columns of n are equal

To compensate, here is a fun fact: most of the other solutions posted here have a time complexity of \$O(2^{n^2})\$ (up to a polynomial in \$n\$), while this answer runs in \$O(4^{n^2})\$, where \$n\$ is the number of rows/columns of the input matrix.