// A308468 - "Trapezoidal numbers": numbers k such that the integers from 1 to k can be arranged in 
// a trapezoid of H lines containing respectively L, L-1, L-2, ..., L-H+1 numbers from top to bottom. 
// The rule is that from the second line, each integer is equal to the absolute value of the 
// difference between the two numbers above it. 
// C++ program by Bert Dobbelaere

#include <cstdio>
#include <cassert>
#include <cstring>

// Max problem dimensions
#define MAXK 100
#define MAXL 32
#define MAXH 16

#define SKIP_ODD_K_SEARCH // comment out to show odd value solutions
// #define SHOW_ALL_SOLUTIONS // uncomment if needed

// Current problem dimensions
int K, H, L;

// Playing field and 'used' markers.
int c[MAXH][MAXL];
bool isused[MAXK+1];

// Set H and return true iff we can arrange n numbers in a trapezoid of width l.
bool findH(int n, int l)
{
    H=2;
    n-= 2*l - 1;
    l-=2;
    while((n>0) && (l>0))
    {
        n-=l;
        H++;
        l--;
    } 
    return (n==0);
}

// Absolute difference
int diff(int a, int b)
{
    return (a>b) ? a-b : b-a;
}

void dumpSolution()
{
    assert(L>0);
    if(c[0][0]>c[0][L-1])
        return; // We already encountered a symmetric solution - don't report.
    
    for(int h=0;h<H;h++)
    {
        for(int i=0;i<h;i++)
            printf("  ");
        for(int l=0;l<(L-h);l++)
            printf("%2d  ",c[h][l]);
        printf("\n");
    }
    printf("\n");
}

// Recursive core routine: attempt to add an element to the top row and its implied differences on the other rows
// 'lvl' is the number of elements that are already filled.
// returns true iff one or more solutions were found
bool solve(int lvl)
{
    bool found=false;;
    
    if(lvl==L)
    {
        dumpSolution();
        return true;
    }
    
    for(int v=1;v<=K;v++)
        if(!isused[v])
        {
            c[0][lvl]=v; // Fill top row number
            isused[v]=true;
            int h=1;
            int l=lvl-1;
            bool ok=true;
            while((h<H) && (l>=0)) // Fill differences and mark them 'used'
            {
                int d=diff(c[h-1][l+1], c[h-1][l]);
                if(isused[d])
                {
                    ok=false;
                    break;
                }
                c[h][l]=d;
                isused[d]=true;
                h++;l--;
            }
            if(ok) // No conflicts with previously filled numbers
            {
                found |= solve(lvl+1); // Go one level deeper

                h=0;
                l=lvl;
                while((h<H) && (l>=0)) // Clean up the 'used' markers
                {
                    isused[c[h][l]]=false;
                    h++;l--;
                }                
            }
            else // Just clean up what we already marked
            {
                int hstop=h;
                h=0;
                l=lvl;
                while((h<hstop) && (l>=0))
                {
                    isused[c[h][l]]=false;
                    h++;l--;
                }                
            }
#ifndef SHOW_ALL_SOLUTIONS        
            if(found)
                break;
#endif
        }
    return found;
}


int main()
{
    int n=0; // sequence index
    
    for(K=2;K<=MAXK;K++)
    {
        bool foundsolution=false;

#ifdef SKIP_ODD_K_SEARCH        
        if(K%2)  // Shortcut. Solution must exist for all odd k>=3. 
        {
            foundsolution=true;
        }
        else
#endif
        {
            // Attempt all trapezoid dimensions. Show 1st solution only.
            for(L=1;L<=((K+1)/2);L++)
                if(findH(K,L))
                {
                    assert(H<=MAXH);
                    assert(L<=MAXL);
                    printf("Searching k=%d H=%d L=%d\n",K,H,L);
                    memset(isused,false,sizeof(isused));
                    foundsolution |= solve(0);
#ifndef SHOW_ALL_SOLUTIONS                    
                    if(foundsolution)
                        break;
#endif                    
                }
        }
        if(foundsolution)
        {
            n++;
            printf("A308468(%d) = %d\n",n,K);
        }
    }

    return 0;
}