Does this addition pyramid puzzle have a unique solution?

Question

Given an addition pyramid \$P\$, determine whether it can be solved. An addition pyramid consists of layers, each having one number less than the one below it. Layer \$i\$ is symbolized as \$P_i\$. \$P_1\$ is the base layer, and \$P_{i+1}\$ is the layer atop \$P_i\$. The \$j\$th number of \$P_i\$ is denoted as \$P_{i,j}\$. \$P_{i,1}\$ is the leftmost number of \$P_i\$, and \$P_{i,j+1}\$ is the number to the right of \$P_{i,j}\$. You may visualize \$P_{i+1,j}\$ residing on top of \$P_{i,j}\$ and \$P_{i,j+1}\$ at the middle, hence the name "addition pyramid".

• \$\forall P_{i,j},P_{i,j}\in\mathbb N^*\$, that is, every number in the pyramid is a non-zero positive integer.
• \$\forall i>1,P_{i,j}=P_{i-1,j}+P_{i-1,j+1}\$, that is, every number not on the base layer of the pyramid is the sum of the two numbers below it.
• If \$P_1\$ has \$n\$ numbers, \$P_i\$ has \$n-i+1\$ numbers, therefore \$P_{i,n-i+1}\$ is the rightmost number of \$P_i\$. In simpler terms, each layer has one number less than the layer below it.

An addition pyramid puzzle \$Q\$ is an addition pyramid with some numbers removed (replaced with \$?\$). Its solution is an addition pyramid \$P\$, where \$\forall Q_{i,j}\ne{?},P_{i,j}=Q_{i,j}\$, that is, the numbers that were originally present in the puzzle have been left unchanged. Such a puzzle may have more than one solution.

Your job is, given an addition pyramid puzzle, to determine if it has exactly one solution.

Input

You can get input in any of the following forms, but be consistent:

• Array of layers.
• Array of layers, shaped like a pyramid using a consistent non-positive-integer value as a separator between elements (used only once each time) as well as left and right padding. The separator and the padding must be the same.
• Array of layers with a consistent valid right or left padding (you must be consistent and not mix right and left padding in this case).

Please note that a consistent value that's not a strictly positive integer must be used to represent a missing number; this value can't be used as padding. Also, you can take the layers concatenated (you can still separate them), and the ordering can either be from the base to the top or from the top to the base.

Output

One of two consistent distinct values, where one represents the presence of a unique solution and the other the absence of a solution or the presence of more than one solution.

Rules

• \$Q_{i+1,j}=Q_{i,j}+Q_{i,j+1}\$ will always be true if \$Q_{i,j},Q_{i,j+1},Q_{i+1,j}\in\mathbb N^*\$, that is, the input is guaranteed to not contain a number on top of two other numbers that isn't their sum if all three numbers are known.
• \$\exists Q_{i,j},Q_{i,j}\ne{?}\$, that is, the pyramid will contain at least one known number.
• Don't do these things.
• This is code-golf, so the shortest answer wins! However, don't let that discourage you from posting a solution just because your language is "too verbose".

Test cases

An array with the layers from the top to the base is used for these test cases, with 0 representing \$?\$.

[[10], [0, 0], [0, 2, 0], [0, 0, 0, 1]] -> True
[[32], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] -> True
[[0], [1, 1]] -> True
[[1], [0, 0]] -> False
[[10], [5, 5], [2, 3, 2], [0, 0, 0, 0]] -> False
[[5], [0, 0], [0, 0, 0]] -> False

Worked examples

The test cases are worked here.

Unique solution 1

$$\begin{array}c&&&10\\&&?&&?\\&?&&2&&?\\?&&?&&?&&1\end{array}$$

Step 1: \$x+y=2\leftrightarrow x=y=1\$.

$$\begin{array}c&&&10\\&&?&&?\\&?&&2&&?\\?&&\color{red}1&&\color{red}1&&1\end{array}$$

Step 2: \$x=y=1\leftrightarrow x+y=2\$.

$$\begin{array}c&&&10\\&&?&&?\\&?&&2&&\color{red}2\\?&&1&&1&&1\end{array}$$

Step 3: \$x=y=2\rightarrow x+y=4\$.

$$\begin{array}c&&&10\\&&?&&\color{red}4\\&?&&2&&2\\?&&1&&1&&1\end{array}$$

Step 4: \$x+4=10\leftrightarrow x=6\$.

$$\begin{array}c&&&10\\&&\color{red}6&&4\\&?&&2&&2\\?&&1&&1&&1\end{array}$$

Steps 5-6 are similar to 4.

$$\begin{array}c&&&10\\&&6&&4\\&\color{red}4&&2&&2\\\color{red}3&&1&&1&&1\end{array}$$

So here we have our unique solution.

Unique solution 2

$$\begin{array}c&&&&&32\\&&&&?&&?\\&&&?&&?&&?\\&&?&&?&&?&&?\\&?&&?&&?&&?&&?\\?&&?&&?&&?&&?&&?\end{array}$$

Step 1: There's no obvious approach here, so let's try using the minimum possible values.

$$\begin{array}c&&&&&32\\&&&&?&&?\\&&&?&&?&&?\\&&?&&?&&?&&?\\&?&&?&&?&&?&&?\\\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1\end{array}$$

Steps 2-5: It looks like the minimum values result in a solution, therefore this is the only solution and is therefore unique.

$$\begin{array}c&&&&&32\\&&&&\color{red}{16}&&\color{red}{16}\\&&&\color{red}8&&\color{red}8&&\color{red}8\\&&\color{red}4&&\color{red}4&&\color{red}4&&\color{red}4\\&\color{red}2&&\color{red}2&&\color{red}2&&\color{red}2&&\color{red}2\\1&&1&&1&&1&&1&&1\end{array}$$

Hint: There's a theorem about addition pyramid puzzles related to this puzzle that you can prove if you think hard enough.

Unique solution 3

$$\begin{array}c&?\\1&&1\end{array}$$

Step 1: \$x=y=1\rightarrow x+y=2\$.

$$\begin{array}c&\color{red}2\\1&&1\end{array}$$

This is an obviously unique solution.

No solution 1

$$\begin{array}c&1\\?&&?\end{array}$$

\$\min\mathbb N^*=1\rightarrow x,y\ge1\rightarrow x+y\ge2>1\$, so there is no solution.

No solution 2

$$\begin{array}c&&&10\\&&5&&5\\&2&&3&&2\\?&&?&&?&&?\end{array}$$

Steps 1-2: \$x+y=2\leftrightarrow x=y=1\$.

$$\begin{array}c&&&10\\&&5&&5\\&2&&3&&2\\\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1\end{array}$$

From there, it follows that \$1+1=3\$, which is a contradiction, therefore there's no solution.

Non-unique solution

$$\begin{array}c&&5\\&?&&?\\?&&?&&?\end{array}$$

Two solutions:

$$\begin{array}c&&5&&&&&&&5\\&2&&3&&&&&3&&2\\1&&1&&2&&&2&&1&&1\end{array}$$

Since there are at least two solutions, there's no unique solution.

Answer 1

Jelly, 18 16 bytes

FṀ‘ṗLSƝƬ€Ṗ€a@ċ⁼1

Try it online!

A monadic link that takes the pyramid in reverse order and returns 1 for true and 0 for false. Generates all possible pyramids with a base up to the max number in the pyramid and checks whether there is one unique match for the input.

Thanks to @Arnauld for pointing out that this failed for [[1,0],[0]]; now corrected.

Thanks to @JonathanAlan for saving 2 bytes!

Explanation

F                | Flatten
 Ṁ               | Maximum
  ‘              | Increase by 1
   ṗ             | Cartesian power of this with:
    L            | - Length of input
        €        | For each:
       Ƭ         | - Repeat the following until no change
     SƝ          |   - Sum of neighbours
         Ṗ€      | Remove last element from each list
           a@    | Logical and input with each list
             ċ   | Count times input appears
              ⁼1 | Check if equal to 1

Answer 2

C# (Visual C# Interactive Compiler), 303 227 bytes

n=>{int i=n.Max(x=>x.Max()),j=n.Count,t=0,k,m=0,z;for(;t<Math.Pow(i,j);){k=t++;var s=n.Select(_=>(a:k%i+1,k/=i).a).ToList();if(n.All(x=>(z=0,b:x.All(o=>o==s[z++]|o<1),s=s.Skip(1).Select((a,b)=>a+s[b]).ToList()).b))m++;}m/=m-1;}

Throws exception if true, runs normally if false.

Try it online!

Answer 3

Wolfram Language (Mathematica), 85 88 bytes

Count[l=Length@#;NestList[2#~MovingMedian~2&,#,l-1]&/@Range@Max@#~Tuples~l,#/. 0->_]==1&

Try it online!

+3 fixed.

Brute force: for all bases with values 1..(sum of all numbers), see if the resulting pyramid matches the given form, and check if the total number of matches is 1. Takes input as a list of levels, base first, with 0 representing missing numbers.

Answer 4

05AB1E, 25 bytes

ZÌLsgãε©.Γü+}¨®š.S*˜O_}OΘ

Takes the pyramid layers in upside down order, base to tip (i.e. [[0,0,0,1],[0,2,0],[0,0],[10]]).

Also, there seems to be a bug somewhere in 05AB1E with .Γ inside a map.. The ©...®š should just be ...yš for -1 byte..

Try it online or verify a few more test cases.

A minor equal-bytes alternative for ©.ΓüO}®š could be [Ðg#üO}\): Try it online.

Explanation:

Z        # Get the flattened maximum of the (implicit) input (without popping)
 Ì       # Increase it by 2
  L      # Create a list in the range [1, max+2]
   sg    # Swap to get the input again, and get the length (amount of layers)
     ã   # Create a cartesian product of this list repeated that many times
ε        # Map each inner list to:
 ©       #  Store it in variable `®` (without popping)
  .Γ     #  Collect all results until the following doesn't change anymore:
    ü    #   Get the pairwise:
     +   #    Sums
   }®š   #  After we've collected all, prepend the original list `®`
 .S      #  Now compare this potential pyramid with the (implicit) input-pyramid
         #  (-1 if a<b; 0 if a==b; 1 if a>b)
   *     #  Multiply that with the (implicit) input-pyramid
    ˜O   #  Then take the flattened sum
      _  #  And check that this sum equals 0 (1 if truhy; 0 if falsey)
}O       # After the map, take the sum to get the amount of truthy values
  Θ      # And trutify it (== 1), since we must output distinct values instead of truthy/falsey
         # (after which the result is output implicitly)

Answer 5

Haskell, 106 bytes

z=zipWith
a#b=a*b==a*a
f x=[1|t<-mapM(\_->[1..sum(sum<$>x)])x,all and$z(z(#))x$iterate(z(+)=<<tail)t]==[1]

Takes an upside down pyramid, e.g. [[0,0,0,1],[0,2,0],[0,0],[10]].

Try it online!

The brute force approach in Haskell:

• create all possible base layers t (mapM(\_->[1..sum(sum<$>x)])x), where the numbers go from 1 to the sum of all numbers in the input pyramid
• create a pyramid from t (iterate(z(+)=<<tail)t)
• compare each layer element-wise with the input (z(z(#))x). The comparison function a # b returns True if both numbers are equal or a is zero (a*b==a*a).
• take a 1 for every pyramid that matches and compare the resulting list to the singleton list [1].