Number Pyramid algorithm: Numbers 1-15 in a pyramid where each number is the difference of the subjacent numbers

Question

first of all: sorry for the long title, but I'm finding it difficult to explain the problem in one sentence ;) . And yes, I also searched around (here and on google) and couldn't find a decent answer.

So, the problem is this:

The numbers 1-15 are to be put in a pyramid (represented by an array) like this:

       1
     2   3
   4   5   6
  7  8   9   10
11 12  13  14  15

...except not really like this, because this pyramid is wrong.

Every number "a" is supposed to be defined by the two numbers "b" and "c" below it with: a = |b - c|. So the first two rows are correct, because |2-3| = 1. But then the third row is of course wrong, because |4-5| = 1, but there's a 2 above those numbers. At the beginning, the pyramid is empty and the task is to look for an algorithm that fills this pyramid.

For me this seemed like a problem that could be solved using some kind of Backtracking algorithm, although I'm not really sure yet, what the trivial base case for the recursion would be.

That said though, I'm trying to help my nephew here and in his class at school they haven't heard anything about recursion yet - not to mention backtracking. So I'm currently trying to find a way how to solve this pyramid with some kind of nested for loops or something, but honestly... I'm currently hitting a wall and I just can't think of a decent solution.

Anyone got any ideas?

Cheers,

/tehK

P.s: Oh, I forgot... the language they're supposed to use is C# (and the pyramid's supposed to be an array), but I can also deal with any other languages, pseudo code or what have you. It's not about the coding, it's more about the algorithm.

Answer 1

There's 15*14*13*12*11=360360 possibilities for the bottom row. Once you have the bottom row the remainder of the pyramid is determined. So simply go through every possibility and see if it contains no repeated numbers. One could optimize this by backtracking, but you asked for no backtracking.

Here's example code:

import itertools

def pyramid():
    for b in itertools.combinations(range(1, 16), 5):
        for xs in itertools.permutations(b):
            rows = [xs]
            while len(rows[-1]) != 1:
                rows.append(tuple(abs(a-b) for a, b in zip(rows[-1], rows[-1][1:])))
            used = sum(rows, ())
            if all(1 <= i <= 15 for i in used) and len(set(used)) == 15:
                yield rows

for p in pyramid():
    for row in p[::-1]:
        print ' ' * 2*(5-len(row)) + '  '.join('% 2d' % n for n in row)
    print

Output:

         5
       4   9
     7   11   2
   8   1   12   10
 6   14   15   3   13

         5
       9   4
     2   11   7
   10   12   1   8
 13   3   15   14   6

The two solutions found are essentially the same (one is the mirror-image of the other).