#include <stdio.h>

#define SIZE 20

char veld[SIZE*SIZE];

#define ONBEKEND '?'
#define VOL      '*'
#define LEEG     ' '

#define LEN     11
char row[SIZE][LEN] = 
{
  { 5, 0, 0, 0, 0, 0, 0 },
  { 1, 1, 1, 5, 2, 0, 0 },
  { 8, 1, 1, 2, 1, 1, 0 },
  { 5, 6, 1, 1, 2, 0, 0 },
  { 8, 1, 1, 3, 3, 0, 0 },
  { 1, 3, 6, 1, 2, 0, 0 },
  { 1, 5, 1, 1, 0, 0, 0 },
  { 1, 5, 1, 1, 0, 0, 0 },
  { 4, 0, 0, 0, 0, 0, 0 },
  { 2, 3, 2, 0, 0, 0, 0 },
  { 1, 2, 2, 2, 1, 0, 0 },
  { 4, 1, 5, 0, 0, 0, 0 },
  { 4, 4, 0, 0, 0, 0, 0 },
  { 1, 2, 2, 3, 0, 0, 0 },
  { 2, 4, 0, 0, 0, 0, 0 },
  { 3, 6, 0, 0, 0, 0, 0 },
  { 3, 1, 5, 0, 0, 0, 0 },
  { 1, 1, 3, 0, 0, 0, 0 },
  { 1, 2, 1, 1, 0, 0, 0 },
  { 1, 0, 0, 0, 0, 0, 0 },
};
char col[SIZE][LEN] =
{
  { 8, 0, 0, 0, 0, 0, 0 },
  { 1, 3, 0, 0, 0, 0, 0 },
  { 8, 1, 3, 0, 0, 0, 0 },
  { 1, 6, 1, 1, 0, 0, 0 },
  { 8, 6, 0, 0, 0, 0, 0 },
  { 1, 1, 2, 7, 0, 0, 0 },
  { 6, 1, 2, 4, 0, 0, 0 },
  { 5, 2, 1, 0, 0, 0, 0 },
  { 1, 1, 1, 1, 1, 0, 0 },
  { 5, 2, 0, 0, 0, 0, 0 },
  { 1, 1, 1, 3, 0, 0, 0 },
  { 5, 4, 1, 0, 0, 0, 0 },
  { 1, 0, 0, 0, 0, 0, 0 },
  { 4, 1, 0, 0, 0, 0, 0 },
  { 3, 6, 0, 0, 0, 0, 0 },
  { 2, 1,11, 0, 0, 0, 0 },
  { 1, 1, 2, 9, 0, 0, 0 },
  { 1, 2, 1, 4, 0, 0, 0 },
  { 3, 1, 2, 1, 0, 0, 0 },
  { 3, 1, 1, 0, 0, 0, 0 },
};


void printsol()
{
    static int cnt = 0;
    cnt++;
    if (cnt < 6)
        return;
    cnt = 0;
    
    //printf("\nmodified = %d\n", modified);
    printf("--------------------\n");
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
            printf("%c", veld[i*SIZE+j]);
        printf("\n");
    }
    printf("--------------------\n");
}


char old_val[SIZE];
char new_val[SIZE];
bool full[SIZE];
bool empty[SIZE];
int modified;
int found;

void reason(char *rowcol, int nr, int pos, int off, char *numbers)
{
#define V(I) veld[pos+off*(I)]

    for (int i = 0; i < SIZE; i++)
        old_val[i] = veld[pos + off * i];

    int mod = 0;

    int fnr = 0;
    int lnr = 0;
    while (numbers[lnr] != 0)
        lnr++;
    lnr--;

    int fp = 0;
    int lp = 19;
    while (fnr <= lnr)
    {
        // skip possible zero's
        for(bool has_empty = true; fp <= lp && has_empty;)
        {    has_empty = false;
            for (int i = 0; i < numbers[fnr]; i++)
                if (V(fp+i) == LEEG)
                {    has_empty = true;
                    for (int j = 0; j < i; j++)
                        if (V(fp+j) == ONBEKEND)
                        {    V(fp+j) = LEEG;
                            modified++;
                            mod++;
                        }
                        else if (V(fp+j) == VOL)
                        {    printf("Error3!");
                            exit(1);
                        }
                    fp += i+1;
                    break;
                }
        }
            
        int i = 0;
        while (fp <= lp && V(fp) == VOL)
        {
            fp++;
            i++;
        }

        if (i == 0)
            break;
        
        while (i < numbers[fnr])
        {
            if (V(fp) == LEEG)
            {
                printf("Error1!");
                exit(1);
            }
            if (V(fp) == ONBEKEND)
            {    
                V(fp) = VOL;
                modified++;
                mod++;
            }
            i++;
            fp++;
        }
        if (fp <= lp)
        {
            if (V(fp) == VOL)
            {
                printf("Error2!");
                exit(1);
            }
            if (V(fp) == ONBEKEND)
            {
                V(fp) = LEEG;
                modified++;
                mod++;
            }
        }
        i++;
        fp++;
        
        fnr++;
    }
    if (fnr <= lnr)
    {
        bool is_full = false;
        for (int i = 1; i < numbers[fnr]; i++)
            if (V(fp+i) == LEEG)
            {    printf("Error13!");
                goto err;
            }
            else if (V(fp+i) == VOL)
                is_full = true;
            else if (is_full)
            {    V(fp+i) = VOL;
                mod++;
                modified++;
            } 
    }
    
    while (fnr <= lnr)
    {
        // skip possible zero's
        for(bool has_empty = true; fp <= lp && has_empty;)
        {    has_empty = false;
            for (int i = 0; i < numbers[lnr]; i++)
                if (V(lp-i) == LEEG)
                {    has_empty = true;
                    for (int j = 0; j < i; j++)
                        if (V(lp-j) == ONBEKEND)
                        {    V(lp-j) = LEEG;
                            modified++;
                            mod++;
                        }
                        else if (V(lp-j) == VOL)
                        {    printf("Error4!");
                            exit(1);
                        }
                    lp -= i+1;
                    break;
                }
        }
            
        int i = 0;
        while (fp <= lp && V(lp) == VOL)
        {
            lp--;
            i++;
        }

        if (i == 0)
            break;
        
        while (i < numbers[lnr])
        {
            if (V(lp) == LEEG)
            {
                printf("Error1!");
                exit(1);
            }
            if (V(lp) == ONBEKEND)
            {    
                V(lp) = VOL;
                modified++;
                mod++;
            }
            i++;
            lp--;
        }
        if (fp <= lp)
        {
            if (V(lp) == VOL)
            {
                printf("Error2!");
                exit(1);
            }
            if (V(lp) == ONBEKEND)
            {
                V(lp) = LEEG;
                modified++;
                mod++;
            }
        }
        i++;
        lp--;
        
        lnr--;
    }
    if (fnr <= lnr)
    {
        bool is_full = false;
        for (int i = 1; i < numbers[lnr]; i++)
            if (V(lp-i) == LEEG)
            {    printf("Error14!");
                goto err;
            }
            else if (V(lp-i) == VOL)
                is_full = true;
            else if (is_full)
            {    V(lp-i) = VOL;
                mod++;
                modified++;
            } 
    }

    if (fp <= lp)
    {
        if (fnr > lnr)
        {
            for (int i = fp; i <= lp; i++)
                if (V(i) == ONBEKEND)
                {    V(i) = LEEG;
                    modified++;
                    mod++;
                }
                else if (V(i) == VOL)
                {    printf("Error5!");
                    exit(1);
                }
        }
        else
        {
            int space = lp - fp + 1;
            int block = -1;
            for (int i = fnr; i <= lnr; i++)
                block += numbers[i] + 1;
            if (block > space)
            {    printf("Error9!");
                exit(1);
            }
            if (block == space)
            {    for (int i = fnr; i <= lnr; i++)
                {
                    for (int j = 0; j < numbers[i]; j++, fp++)
                        if (V(fp) == ONBEKEND)
                        {    V(fp) = VOL;
                            modified++;
                            mod++;
                        }
                        else if (V(fp) == LEEG)
                        {    printf("Error7!");
                            exit(1);
                        }
                    if (fp <= lp)
                    {    if (V(fp) == ONBEKEND)
                        {    V(fp) = LEEG;
                            modified++;
                            mod++;
                        }
                        else if (V(fp) == VOL)
                        {    printf("Error8!");
                            exit(1);
                        }
                        fp++;
                    }
                }
            }
            else
            {    for (int i = fnr; i <= lnr; i++)
                {
                    for (int j = 0; j < numbers[i]; j++, fp++)
                        if (j >= space - block)
                        {    if (V(fp) == ONBEKEND)
                            {    V(fp) = VOL;
                                modified++;
                                mod++;
                            }
                            else if (V(fp) == LEEG)
                            {    printf("Error11!");
                                exit(1);
                            }
                        }
                    fp++;
                }
            }            
        }
    }    
        
    if (mod)
    {
    err:
        printf("re %8s %2d: ", rowcol, nr);
        for (int j = 0; j < SIZE; j++)
            printf("%c", old_val[j]);
        printf(" -> ");
        for (int j = 0; j < SIZE; j++)
            printf("%c", veld[pos + off * j]);
        printf(" %d (reason)\n", mod);
        printsol();
    }
}

void tryplace(int i, char *numbers)
{
    if (numbers[0] == 0)
    {
        bool can_place = true;
        for (int j = i; j < SIZE; j++)
        {
            if (old_val[j] == VOL)
            {    can_place = false;
                break;
            }
            new_val[j] = LEEG;
        }
        if (can_place)
        {
            for (int j = 0; j < SIZE; j++)
                if (new_val[j] == VOL)
                    empty[j] = false;
                else
                    full[j] = false;
            found++;
        }
        return;
    }
    
    int ib = i == 0 ? i : i+1;
    int ie = ib + numbers[0]-1;
    for (; ie < SIZE; ib++, ie++)
    {
        bool can_place = true;
        for (int j = i; j < ib; j++)
            if (old_val[j] == VOL)
            {    can_place = false;
                break;
            }
        if (can_place)
        {            
            for (int j = ib; j <= ie; j++)
                if (old_val[j] == LEEG)
                {    can_place = false;
                    break;
                }
                
            if (can_place)
            {
                for (int j = i; j < ib; j++)
                    new_val[j] = LEEG;
                for (int j = ib; j <= ie; j++)
                    new_val[j] = VOL;
            
                tryplace(ie+1, numbers + 1);
            }
        }
    }
}

void all_combinations(char *rowcol, int nr, int pos, int off, char *numbers)
{
    if (modified > 0)
        return;

    for (int i = 0; i < SIZE; i++)
    {    old_val[i] = veld[pos + off * i];
        full[i] = true;
        empty[i] = true;
    }
    
    found = 0;
    tryplace(0, numbers);
    
    if (found == 0)
        return;
    
    
    int mod = 0;
    for (int i = 0; i < SIZE; i++)
    {    if (   full[i] && !empty[i]
            && veld[pos + off * i] == ONBEKEND)
        {    veld[pos + off * i] = VOL;
            modified++;
            mod++;
        }
        if (   !full[i] && empty[i]
            && veld[pos + off * i] == ONBEKEND)
        {    veld[pos + off * i] = LEEG;
            modified++;
            mod++;
        }
    }
    
    if (mod)
    {    
        printf("ac %8s %2d: ", rowcol, nr);
        for (int j = 0; j < SIZE; j++)
            printf("%c", old_val[j]);
        printf(" -> ");
        for (int j = 0; j < SIZE; j++)
            printf("%c", veld[pos + off * j]);
        printf(" %d (%d)\n", mod, found);
        printsol();
    }
}


void main()
{
    // testen invoer correct
    int som_row = 0;
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < LEN; j++)
            if (row[i][j] == 0)
                break;
            else
                som_row += row[i][j];
    int som_col = 0;
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < LEN; j++)
            if (col[i][j] == 0)
                break;
            else
                som_col += col[i][j];

    if (som_row != som_col)
    {
        printf("row (%d) and col (%d) differ\n", som_row, som_col);
        return 0;
    }
    
    for (int i = 0; i < SIZE*SIZE; i++)
        veld[i] = ONBEKEND;
    
    do
    {
        modified = 0;
        
        for (int r = 0; r < SIZE; r++)
            reason("rij", r+1, r*SIZE, 1, row[r]);
        for (int c = 0; c < SIZE; c++)
            reason("colom", c+1, c, SIZE, col[c]);             

        if (modified == 0)
        {
            for (int r = 0; r < SIZE; r++)
                all_combinations("rij", r+1, r*SIZE, 1, row[r]);
            for (int c = 0; c < SIZE; c++)
                all_combinations("colom", c+1, c, SIZE, col[c]);             
        }
    }
    while (modified > 0);
    
    printf("\n--------------------\n");
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
            printf("%c", veld[i*SIZE+j]);
        printf("\n");
    }
    printf("--------------------\n");
    
}