algorithm - バックトラッキングのあるサムピラミッド

Question

私はこの問題を解決しようとしていますが、バックトラッキング アルゴリズムは初めてです。問題は、このようなピラミッドを作成して、2 つの数値の上にある数値がそれらの合計になるようにすることです。ピラミッド内のすべての数値は異なり、100 未満である必要があります。次のように:

     88
   39  49
  15  24  25
 4  11  13  12
1  3   8   5   7 

バックトラッキングを使用してこれを行う方法についての指針はありますか?

Answer 1

必ずしもバックトラックする必要はありませんが、要求しているプロパティは、興味深いことにPascalTriangleプロパティと非常によく似ています。

とりわけ二項係数の効率的な計算に使用されるパスカルの三角形（http://en.wikipedia.org/wiki/Pascal's_triangle）は、数値が上記の2つの数値の合計に等しいピラミッドです。トップが1である。

ご覧のとおり、反対のプロパティを求めています。ここで、数値はその下の数値の合計です。

                1
              1   1
            1   2   1
          1   3   3   1
        1   4   6   4   1
      1   5  10  10   5   1
    1   6  15  20  15   6   1
  1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1

たとえば、上記のパスカルの三角形で、ピラミッドの上部を56にしたい場合、ピラミッドは56から始まるパスカルの三角形の下部から再構築され、次のようになります。

                 56
              21    35
            6    15    20
         1     5    10    10

繰り返しになりますが、これはバックトラックソリューションではなく、これは注目に値する興味深い近似であると思いましたが、すべてのNに対して十分なソリューションが得られない可能性があります。