Numerical pyramid puzzle algorithm needed

Question

Is there any general algorithm to solve this kind of puzzle?

https://i.stack.imgur.com/PNH5Q.jpg

Any sub O(N^3) solution will be greatly appreciated <3

Answer 1

It is assumed that each cell in the pyramid is the sum of the two immediately below it.

Theorem

For any sub-pyramid P, let the array r be any row in P of length n+1. Then the sum

C(n,0)*r[0] + C(n,1)*r[1] + ... + C(n,n)*r[n]

is constant for each row of P. (C(i,j) is the binomial coefficient.)

---

For example, let P be the whole pyramid. For the top row, we have:

C(0,0) * 223 = 223

For the bottom row, we have:

C(4,0)*7 + C(4,1)*12 + C(4,2)*x + C(4,3)*18 + C(4,4)*6 = 133 + 6*x

where x is the unknown value in the bottom row.

Applying the above theorem:

223 = 133 + 6*x

from which it follows that x = 15.

As a demonstration for the consistency of this theorem, one can take P' as the 3-row sub-pyramid whose peak is 60. Then

C(0,0)*60 = C(2,0)*12 + C(2,1)*x + C(2,2)*18

from which it again follows that x = 15.

Once one row is completely known, all rows above it follow directly.

Answer 2

Sounds like https://en.wikipedia.org/wiki/Constraint_satisfaction to me - you pose the problem as a set of arithmetical equations, typically with small integer unknowns, and build a data-structure that works out when you know enough about some of the unknowns in one of the equations to deduce others. Then you start a tree search over the possible solutions, using the data structure to work out enough of the unknowns from the assumptions so far to make the tree search feasible and/or to rule out partial solutions that can't possibly work early.

Some time ago I worked in the same office as a group using ILOG Solver for scheduling, and noticed that its manual had a number of examples of using it to solve simple logical/numerical problems - I think https://en.wikipedia.org/wiki/Verbal_arithmetic was one. (They eventually gave up on the scheduling in favour of a much simpler approach. The stated reason was that the ILOG Solver scheduling was not transparent enough for users to see why unsatisfiable schedules were unsatisfiable and thereby work out what constraints needed to be relaxed).