/*  mega_nono.cpp

    Experimental Nonogram solver. The command line options are:
        <filename> [<filename2>]
    
    The file 'filename' is expected to contain a description of a nonogram.
    This description constist of:
    - a line starting with "width " followed by a number giving the width
    - a line starting with "height " followed by a number giving the height
    - a line starting with "rows" followed by lines which specify one row each
    - a line starting with "columns" followed by lines which specify one column each
    The specification of a row or column either consists of "0" or a sequences
    of numbers followed by a comma and a space.
    
    The (optional) file 'filename2' contains a partial solution of the
    nonogram. 
    
    On the output the program will give a trace of the actions taken.
    The file mega_nono_results.txt will be produced, which contains
    the progressive results of the solution found.
    
    This program is refered to at http://www.iwriteiam.nl/D0908.html#18
    
    Copyright (C) 2009 Frans Faase

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
    
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

GNU General Public License:
    http://www.iwriteiam.nl/GNU.txt
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

typedef unsigned char byte;

class Alarm
{
public:
    Alarm() : _alarm_time(0), _went_off(false) {}
    
    void set_alarm(long seconds)
    {
        if (seconds == 0)
            _alarm_time = 0;
        else
            _alarm_time = clock() + CLK_TCK * seconds;
        _went_off = false;
    }
    void clear_alarm()
    {
        _alarm_time = 0;
        _went_off = false;
    }
    
    bool alarm()
    {
        if (_alarm_time > 0 && clock() > _alarm_time)
        {
            _went_off = true;
        }
        return _went_off;
    }
    bool went_off() { return _went_off; }

private:
    clock_t _alarm_time;
    bool _went_off;
};    


#define MAX_SIZE 100
#define MAX_SIZE_D8 ((MAX_SIZE+7)/8)

struct Need
{
    void reset() { _need = 0; }
    bool needed(int type) { return (_need & (1 << type)) == 0; }
    void done(int type) { _need |= (1 << type); }

private:
    int _need;         
};

struct Piece
{
    int size;
    int min;
    int max;
    bool pos[MAX_SIZE];

    void clear(int size)
    {
        min = size;
        max = 0;
    }
    bool empty() { return min >= max; }
    void init(int p, int s)
    {
        min = p;
        max = p + s;
        for (int i = 0; i < MAX_SIZE; i++)
            pos[i] = min <= i && i < max;
    }
    void assign(const Piece& p)
    {
        size = p.size;
        min = p.min;
        max = p.max;
        for (int i = 0; i < MAX_SIZE; i++)
            pos[i] = p.pos[i];
    }
    void update(const Piece& p, bool& changed)
    {
        min = p.min;
        max = p.max;
        for (int i = 0; i < MAX_SIZE; i++)
            if (pos[i] && !p.pos[i])
            {
                pos[i] = false;
                changed = true;
            }
    }
    bool reset(int i)
    {
        if (pos[i])
        {
            pos[i] = false;
            if (i == min)
            {
                min++;
                while (min < max && !pos[min])
                    min++;
            }
            else if (i == max-1)
            {
                max--;
                while (min < max && !pos[max-1])
                    max--;
            }
        }
        return min < max;
    }
    bool limit_min(int i)
    {
        while (min < i && min < max)
            reset(min);
        return min < max;
    }
    bool limit_max(int i)
    {
        while (i < max && min < max)
            reset(max-1);
        return min < max;
    }
    bool set(int i)
    {
        pos[i] = true;
        if (i < min)
            min = i;
        if (i+1 > max)
            max = i+1;
    }
};

class Numbers
{
public:
    int min;
    int max;
    bool set[MAX_SIZE];

    Numbers() : min(-1), max(-1)
    {
        for (int i = 0; i < MAX_SIZE; i++)
        {
            set[i] = false;
            _trans[i] = -1;
        }
    }

    bool empty() { return min == max; }
    void add(int i)
    {
        if (i >= MAX_SIZE)
        {
            printf("add(%d)\n", i);
            exit(1);
        }
        set[i] = true;
        if (i < min || min == -1)
            min = i;
        if (max <= i)
            max = i + 1;
    }
    int trans(int i) const
    {
        if (i < 0 || i >= MAX_SIZE || !set[i] || _trans[i] == -1)
        {
             printf("ill index\n"); 
             exit(1); 
        }
        return _trans[i];
    }

    class Iterator
    {
    public:
        Iterator(const Numbers& numbers) : _numbers(numbers), value(numbers.min) {}
        void init() { value = _numbers.min; }
        bool more() { return value < _numbers.max; }
        void next()
        {
            for (value++; value < _numbers.max; value++)
                if (_numbers.set[value])
                    return;
        }
        operator int() { return value; }
        int value;
        int trans() { _numbers.trans(value); }
    private:
        const Numbers& _numbers;
    };
    
    int init_trans(int step)
    {
        int c = 0;
        for (Iterator it(*this); it.more(); it.next())
            _trans[it] = (c++) * step;
        return c;
    }
    
private:
    int _trans[MAX_SIZE];
};

struct Pieces
{
    int nr;
    Piece pieces[MAX_SIZE];
    Need need;

    Pieces()
    {
        fnr = 0;
        filled[fnr++] = false;
    }
        
    void add(int v)
    {
        pieces[nr++].size = v;
        for (int i = 0; i < v; i++)
            filled[fnr++] = true;
        filled[fnr++] = false;
    }
    
    void init(int size)
    {
        need.reset();
        
        int sum = 0;
        for (int i = 0; i < nr; i++)
            sum += pieces[i].size;
        
        int left = size - (sum + nr - 1);
        if (left < 0)
            left = 0;
        
        int p = 0;
        for (int i = 0; i < nr; i++)
        {
            pieces[i].init(p, left+1);
            p += pieces[i].size + 1;
        }
    }
    void assign(const Pieces& ps)
    {
        need.reset();
        
        nr = ps.nr;
        for (int i = 0; i < nr; i++)
            pieces[i].assign(ps.pieces[i]);
            
        fnr = ps.fnr;
        for (int i = 0; i < fnr; i++)
            filled[i] = ps.filled[i];            
    }
    void update(const Pieces& ps, bool changed)
    {
        for (int i = 0; i < nr; i++)
            pieces[i].update(ps.pieces[i], changed);
    }
    void getNumbers(int at, Numbers &numbers)
    {
        int nr_nrs = 0;    
        int prev_min = 0;
        for (int i = 0; i < nr; i++)
        {
            Piece& piece = pieces[i];
            if (prev_min <= at && at < piece.max-1)
                numbers.add(nr_nrs);
            nr_nrs++;
            
            for (int j = 0; j < piece.size; j++, nr_nrs++)
                if (at-j >= 0 && piece.pos[at-j])
                    numbers.add(nr_nrs);
                
            prev_min = piece.min + piece.size;
        }
        if (prev_min <= at)
            numbers.add(nr_nrs);
        nr_nrs++;
        
        if (nr_nrs != fnr)
        {
            printf("nr(%d) != fnr(%d)\n", nr_nrs, fnr);
            nr_nrs = 0;
            prev_min = 0;
            for (int i = 0; i < nr; i++)
            {
                Piece& piece = pieces[i];

                printf("  n[%d] = %d <= %d && %d < %d = %d\n", nr_nrs++, prev_min, at, at, piece.max-1, prev_min <= at && at < piece.max-1);
                
                printf("  %d: %d-%d:", i, piece.min, piece.max);
                for (int j = piece.min; j < piece.max; j++)
                    printf("%d", piece.pos[j]);
                    
                printf("\n");
                for (int j = 0; j < piece.size; j++)
                    printf("  n[%d] = pos %d = %d\n", nr_nrs++, at-j, at-j >= 0 && piece.pos[at-j]);
                    
                prev_min = piece.min + piece.size;
            }
            printf("  n[%d] = %d <= %d = %d\n", nr_nrs++, prev_min, at, prev_min <= at);
            exit(1);
        }
        
        //for (Numbers::Iterator it(numbers); it.more(); it.next())
        //    printf("%d,", it.value);

        if (numbers.empty())
        {
            printf("empty\n");
            nr_nrs = 0;
            prev_min = 0;
            for (int i = 0; i < nr; i++)
            {
                Piece& piece = pieces[i];

                printf("  n[%d] = %d <= %d && %d < %d = %d\n", nr_nrs++, prev_min, at, at, piece.max-1, prev_min <= at && at < piece.max-1);
                
                printf("  %d: %d-%d:", i, piece.min, piece.max);
                for (int j = piece.min; j < piece.max; j++)
                    printf("%d", piece.pos[j]);
                    
                printf("\n");
                for (int j = 0; j < piece.size; j++)
                    printf("  n[%d] = pos %d = %d\n", nr_nrs++, at-j, at-j >= 0 && piece.pos[at-j]);
                    
                prev_min = piece.min + piece.size;
            }
            printf("  n[%d] = %d <= %d = %d\n", nr_nrs++, prev_min, at, prev_min <= at);
        }
    }
    int fnr;
    bool filled[MAX_SIZE];
};

int n;
int m;
int nm;

#define UNKNOWN  '?'
#define FULL     '*'
#define EMPTY    '_'



struct Clues
{
    Pieces row[MAX_SIZE];
    Pieces col[MAX_SIZE];

    void assign(const Clues& clues)
    {
        for (int i = 0; i < n; i++)
            row[i].assign(clues.row[i]);
        for (int i = 0; i < m; i++)
            col[i].assign(clues.col[i]);
    }
    
};



struct Board
{
    Need rowneeds[MAX_SIZE];
    Need colneeds[MAX_SIZE];
    
    int nr_unknown;

    char operator[](const int i) const { return _b[i]; }
    
    void clear()
    {
        for (int i = 0; i < nm; i++)
            _b[i] = UNKNOWN;
        nr_unknown = nm;
    }
    
    void copy(const Board& board)
    {
        for (int i = 0; i < nm; i++)
            _b[i] = board._b[i];
        nr_unknown = board.nr_unknown;
        
        resetneeds();
    }
        
    void clone(const Board& board)
    {
        for (int i = 0; i < nm; i++)
            if (board._b[i] == UNKNOWN)
                _b[i] = ' ';
            else
                _b[i] = board._b[i];
        nr_unknown = 0;
        
        resetneeds();
    }
    
    void assign(const int i, const int v)
    {
        if (v == UNKNOWN)
        {
            if (_b[i] != UNKNOWN)
                nr_unknown++;
        }
        else
        {
            if (_b[i] == UNKNOWN)
                nr_unknown--;
        }
        _b[i] = v;
    }
    
    void combine(const int i, const int v)
    {
        if (_b[i] == ' ')
        {
            _b[i] = v;
            if (v == UNKNOWN)
                nr_unknown++;
        }
        else if (_b[i] != v && _b[i] != UNKNOWN)
        {
            _b[i] = UNKNOWN;
            nr_unknown++;
        }
    }
    void combine(const Board& board)
    {
        for (int i = 0; i < nm; i++)
            combine(i, board[i]);
    }
    
    void intergrate(const int i, const int val, int &modified)
    {
        if (_b[i] == UNKNOWN && (val == FULL || val == EMPTY))
        {
            modified++;
            _b[i] = val;
            rowneeds[i%n].reset();
            colneeds[i/n].reset();
            nr_unknown--;
        }
    }
    void intergrate(const Board& board, int &modified)
    {
        for (int i = 0; i < nm; i++)
            intergrate(i, board[i], modified);
    }
    
    void resetneeds()
    {
        for (int i = 0; i < MAX_SIZE; i++)
        {
            rowneeds[i].reset();
            colneeds[i].reset();
        }
    }
    
    int count_unknown()
    {
        int result = 0;
        for (int i = 0; i < nm; i++)
            if (_b[i] == UNKNOWN)
                result++;
        return result;
    }    

private:
    char _b[MAX_SIZE*MAX_SIZE];
};

void read_line(FILE* f, char *line, bool &more)
{
    if (fgets(line, 299, f) == 0)
    {
        more = false;
        return;
    }
    
    if (line[strlen(line)-1] == '\n')
        line[strlen(line)-1] = '\0';
    more = true;
}

bool read_clues(char *fn, Clues &clues)
{
    FILE* f = fopen(fn, "rt");
    
    char line[300];
    bool more;
    
    read_line(f, line, more);
    while (more && strncmp(line, "width ", 6) != 0)
        read_line(f, line, more);
    if (!more)
    {    fclose(f);
        printf("E1\n");
        return false;
    }
    m = atoi(line+6);

    read_line(f, line, more);
    while (more && strncmp(line, "height ", 7) != 0)
        read_line(f, line, more);
    if (!more)
    {    fclose(f);
        printf("E2\n");
        return false;
    }
    n = atoi(line+7);
    
    read_line(f, line, more);
    while (more && strcmp(line, "rows") != 0)
        read_line(f, line, more);
    if (!more)
    {    fclose(f);
        printf("E3\n");
        return false;
    }
    for (int i = 0; i < n; i++)
    {
        read_line(f, line, more);
        if (!more)
        {    fclose(f);
            printf("E4\n");
            return false;
        }

        clues.row[i].nr = 0;
        int sum = 0;
                
        if (strcmp(line, "0") != 0)
        {
            char *s = line;
            
            while (*s != '\0')
            {
                int v = 0;
                for (; isdigit(*s); s++)
                    v = 10 * v + *s - '0';
                
                for(; *s == ',' || *s == ' '; s++)
                    ;
                
                clues.row[i].add(v);
            }
        }
        
        clues.row[i].init(m);
    }

    read_line(f, line, more);
    while (more && strcmp(line, "columns") != 0)
        read_line(f, line, more);
    if (!more)
    {    fclose(f);
        printf("E5\n");
        return false;
    }
    for (int i = 0; i < m; i++)
    {
        read_line(f, line, more);
        if (!more)
        {    fclose(f);
            printf("E6\n");
            return false;
        }

        clues.col[i].nr = 0;
        
        int k = 0;
        if (strcmp(line, "0") != 0)
        {
            char *s = line;
            
            while (*s != '\0')
            {
                int v = 0;
                for (; isdigit(*s); s++)
                    v = 10 * v + *s - '0';
                
                for(; *s == ',' || *s == ' '; s++)
                    ;
                
                clues.col[i].add(v);
            }
        }
        
        clues.col[i].init(n);
    }
    nm = n * m;
    
    fclose(f);
    
    return true;
}

void write_pieces(const Clues& clues)
{
    for (int i = 0; i < n; i++)
    {
        printf("row %d:", i+1);
        
        const Pieces& ps = clues.row[i];
        
        for (int j = 0; j < ps.nr; j++)
        {
            const Piece& p = ps.pieces[j];
            printf(" %d (%d %d)", p.size, p.min, p.max);
        }
        printf("\n");
    }
    for (int i = 0; i < m; i++)
    {
        printf("col %d:", i+1);
        
        const Pieces& ps = clues.col[i];
        
        for (int j = 0; j < ps.nr; j++)
        {
            const Piece& p = ps.pieces[j];
            printf(" %d (%d %d)", p.size, p.min, p.max);
        }
        printf("\n");
    }
}



void read_prev_board(char* fn, Board &board)
{
    FILE *f = fopen(fn, "rt");
    if (f == 0)
    {
        printf("cannot open file '%s'\n", fn);
        return;
    }
        
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            char ch = (char)fgetc(f);
            if (ch != FULL && ch != EMPTY && ch != UNKNOWN)
                goto error;
            board.assign(i+n*j, ch);
        }
        char ch = (char)fgetc(f);
        if (ch != '\n')
            goto error;
    }
    fclose(f);

    printf("continue with:\n");
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            printf("%c", board[i+n*j]);
        printf("\n");
    }
    return;

error:
    fclose(f);
    board.clear();
}

void printsol(Board &board)
{
    rename("mega_nono_2.sol", "mega_nono_2.sol2");
    FILE *g = fopen("mega_nono_2.sol", "w");    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            fprintf(g, "%c", board[i+n*j]);
        fprintf(g,"\n");
    }
    fclose(g);
}

void dumpboard(Board &board)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            printf("%c", board[i+n*j]);
        printf("\n");
    }
}

#define HOT 3

void dump(char* msg, char *line, int size, Pieces &ps)
{
    printf("%s ", msg);
    for (int i = 0; i < size; i++)
        printf("%c", line[i]);
    printf(" ");
    for (int i = 0; i < ps.nr; i++)
        printf(" %d (%d-%d)", ps.pieces[i].size, ps.pieces[i].min, ps.pieces[i].max);
    printf("\n");
}

bool reason(char *line, int size, Pieces &ps)
{
    for (bool go = true; go; )
    {
        go = false;
    
        bool notempty[MAX_SIZE];
        for (int i = 0; i < size; i++)
            notempty[i] = false;
    
        for (int i = 0; i < ps.nr; i++)
        {
            Piece& p = ps.pieces[i];
            
            for (int j = p.min; j < p.max; j++)
                if (p.pos[j])
                {
                    int e = j + p.size;
                    
                    bool possible =    (j == 0 || line[j-1] != FULL)
                                    && (e == size || line[e] != FULL);
                                    
                    for (int k = 0; k < p.size && possible; k++)
                        if (line[j+k] == EMPTY)
                            possible = false;
                    
                    if (possible)
                    {
                        for (int k = 0; k < p.size; k++)
                            notempty[j+k] = true;
                    }
                    else
                    {
                        go = true;
                        if (!p.reset(j))
                        {
                            //printf("x1\n");
                            return false;
                        }
#ifdef DEBUG_REASON
                        printf("piece %d: %d impossible: %d-%d\n", i, j, p.min, p.max);
#endif
                    }
                }
        }
        
        for (int i = 1; i < ps.nr; i++)
        {
            int min = ps.pieces[i-1].min + ps.pieces[i-1].size + 1;
            Piece& p = ps.pieces[i];
            
            if (min > p.min)
            {
                if (!p.limit_min(min))
                {
                    //printf("x2\n");
                    return false;
                }
                go = true;
#ifdef DEBUG_REASON
                printf("piece %d: limit min %d: %d-%d\n", i, min, p.min, p.max);
#endif
            }
        }

        for (int i = ps.nr - 2; i >= 0; i--)
        {
            int max = ps.pieces[i+1].max - ps.pieces[i].size - 1;
            Piece& p = ps.pieces[i];

            if (max < p.max)
            {
                if (!p.limit_max(max))
                {
                    //printf("piece %d: limit max %d: %d-%d\n", i, max, p.min, p.max);
                    //printf("x3\n");
                    return false;
                }
                go = true;
#ifdef DEBUG_REASON
                printf("piece %d: limit max %d: %d-%d\n", i, max, p.min, p.max);
#endif
            }
        }
        
        for (int i = 0; i < ps.nr; i++)
        {
            Piece& p = ps.pieces[i];

            bool pp = false;
                        
            for (int k = p.max - 1; k < p.min + p.size; k++)
            {
                if (line[k] == EMPTY)
                {
                    //printf("x4\n");
                    return false;
                }
                if (line[k] != FULL)
                {
                    line[k] = FULL;
                    go = true;
#ifdef DEBUG_REASON
                    if (!pp) printf("line FULL");
                    pp = true;
                    printf(" %d", k);
#endif
                }
            }
#ifdef DEBUG_REASON
            if (pp)
                printf("\n");
#endif
        }
        
        bool pp = false;
        
        for (int i = 0; i < size; i++)
            if (!notempty[i])
            {
                if (line[i] == FULL)
                {
                    //printf("x5\n");
                    return false;
                }
                if (line[i] != EMPTY)
                {
                    line[i] = EMPTY;
                    go = true;
#ifdef DEBUG_REASON
                    if (!pp) printf("line EMPTY");
                    pp = true;
                    printf(" %d", i);
#endif
                }
            }
#ifdef DEBUG_REASON
        if (pp)
            printf("\n");
#endif

        if (!go)
        {            
            for (int i = 0; i < size; i++)
                if (line[i] == FULL)
                {
                    char tline[MAX_SIZE];
                    int nr_pieces_overlap = 0;
                    int nr_piece_overlap;
                    
                    for (int j = 0; j < size; j++)
                        tline[j] = UNKNOWN;
                        
                    for (int j = 0; j < ps.nr; j++)
                    {
                        Piece& p = ps.pieces[j];
                        
                        for (int k = p.min; k < p.max; k++)
                            if (p.pos[k] && k <= i && i < k+p.size)
                            {
                                if (nr_pieces_overlap == 0 || nr_piece_overlap != j)
                                {
                                    nr_pieces_overlap++;
                                    nr_piece_overlap = j;
                                }
                                
                                for (int l = 0; l < k-1; l++)
                                    tline[l] = ' ';
                                if (k > 0)
                                {
                                    if (tline[k-1] == UNKNOWN)
                                        tline[k-1] = EMPTY;
                                    else if (tline[k-1] != EMPTY)
                                        tline[k-1] = ' ';
                                }
                                for (int l = 0; l < p.size; l++)
                                {
                                    if (tline[k+l] == UNKNOWN)
                                        tline[k+l] = FULL;
                                    else if (tline[k+l-1] != FULL)
                                        tline[k+l] = ' ';
                                }
                                if (k + p.size < size)
                                {
                                    if (tline[k + p.size] == UNKNOWN)
                                        tline[k + p.size] = EMPTY;
                                    else if (tline[k + p.size] != EMPTY)
                                        tline[k + p.size] = ' ';
                                }
                                for (int l = k + p.size + 1; l < size; l++)
                                    tline[l] = ' ';
                            }
                    }
                    
                    bool pp = false;
                    
                    for (int j = 0; j < size; j++)
                    {
#ifdef DEBUG_REASON
                        if (!pp && line[j] == UNKNOWN && (tline[j] == FULL || tline[j] == EMPTY))
                        {
                            printf("now: ");
                            for (int k = 0; k < size; k++)
                                printf("%c", line[k]);
                            printf("\nnew: ");
                            for (int k = 0; k < size; k++)
                                printf("%c", tline[k]);
                            printf("\nchanges: ");
                            pp = true;
                        }
#endif
                        if (tline[j] == FULL)
                        {
                            if (line[j] == EMPTY)
                            {
                                //printf("x6\n");
                                return false;
                            }
                            if (line[j] == UNKNOWN)
                            {
                                line[j] = FULL;
                                go = true;
#ifdef DEBUG_REASON
                                printf(" %d FULL", j);
#endif
                            }
                        }
                        else if (tline[j] == EMPTY)
                        {
                            if (line[j] == FULL)
                            {
                                //printf("x7\n");
                                return false;
                            }
                            if (line[j] == UNKNOWN)
                            {
                                line[j] = EMPTY;
                                go = true;
#ifdef DEBUG_REASON
                                printf(" %d EMPTY", j);
#endif
                            }
                        }
                    }
#ifdef DEBUG_REASON
                    if (pp)
                        printf("\n");
#endif

                    if (nr_pieces_overlap == 1)
                    {
                        Piece& p = ps.pieces[nr_piece_overlap];
                        
                        for (int k = p.min; k < p.max; k++)
                            if (p.pos[k] && !(k <= i && i < k+p.size))
                            {
                                p.reset(k);
                                go = true;
                            }
                    }
                }
        }
                                
#ifdef DEBUG_REASON
        if (go)
            dump("result ", line, size, ps);
#endif
    }
    
    return true;
}

bool reason(char *rowcol, int nr, Board &board, int pos, int off, int size, Pieces& pieces, int& modified)
{
#ifdef DEBUG_REASON
    printf("%s%d\n", rowcol, nr);
#endif
    
    char line[MAX_SIZE];
    for (int i = 0; i < size; i++)
        line[i] = board[pos + off*i];
        
    Pieces ps;
    ps.assign(pieces);
    
    if (!reason(line, size, ps))
        return false;
                
    for (int i = 0; i < size; i++)
        board.intergrate(pos + off*i, line[i], modified);

    bool changed = false;
    pieces.update(ps, changed);
    if (changed)
    {
        modified++;
    }
    
    return true;
}

bool guess_solve(Board &board, const Clues& clues)
{
    static Clues guess_clues;
    guess_clues.assign(clues);
    
    board.resetneeds();
    
    int modified;    
    do
    {
        modified = 0;

        for (int i = 0; i < n; i++)
            if (board.rowneeds[i].needed(1) && !reason("rij", i+1, board, i, n, m, guess_clues.row[i], modified))
                return false;
            else
                board.rowneeds[i].done(1);
        for (int j = 0; j < m; j++)
            if (board.colneeds[j].needed(1) && !reason("colom", j+1, board, j*n, 1, n, guess_clues.col[j], modified))
                return false;
            else
                board.colneeds[j].done(1);

        //printf("\nguess modified = %d\n", modified);
        //printsol(board);
    }
    while (modified > 0);
    
    return true /* ????? */;
}

void guess_something(char *rowcol, int nr, const Clues& clues, Board &board, int pos, int off, int size, Pieces& pieces, int& modified)
{
    printf("guess %s%d", rowcol, nr);
    bool reduced = false;
    
    for (int i = 0; i < pieces.nr && modified == 0; i++)
    {
        Piece& p = pieces.pieces[i];
        printf(" %d", p.max - p.min);
        if (p.max - p.min > 1)
        {    
            Board combined_guess_board;
            combined_guess_board.clone(board);
            bool found = false;
            
            for (int k = p.min; k < p.max; k++)
                if (p.pos[k])
                {
                    Board guess_board;
                    guess_board.copy(board);
    
                    if (k > 0)
                        guess_board.assign(pos+off*(k-1), EMPTY);
                    if (k + p.size < size)
                        guess_board.assign(pos+off*(k + p.size), EMPTY);
                    for (int l = 0; l < p.size; l++)
                        guess_board.assign(pos+off*(k + l), FULL);
    
                    if (guess_solve(guess_board, clues))
                    {
                        found = true;
                        combined_guess_board.combine(guess_board);
                        if (combined_guess_board.nr_unknown == board.nr_unknown)
                            break;
                    }
                    else
                    {
                        printf("%s%d impossible: %d at %d\n", rowcol, nr, i, k);
                        p.reset(k);
                        reduced = true;
                    }                
                }
            
            if (found && combined_guess_board.nr_unknown < board.nr_unknown)
                board.intergrate(combined_guess_board, modified);
        }
    }
    if (reduced)
        reason(rowcol, nr, board, pos, off, size, pieces, modified);

    printf("\n");
}


class PiecesCombinationsIterator
{
public:
    PiecesCombinationsIterator(const Pieces& pieces, int size)
      : _pieces(pieces), _size(size)
    {
        for (int i = 0; i < _pieces.nr; i++)
            positions[i] = _pieces.pieces[i].min;
        _more = true;
    }
    bool more() { return _more; }
    void next()
    {
        for (int i = 0; i < _pieces.nr; i++)
        {
            const Piece& p = _pieces.pieces[i];
            int end = p.max;
            if (i+1 < _pieces.nr)
            {
                int j = positions[i+1] - p.size;
                if (j < end)
                    end = j;
            }

            for (int j = positions[i]+1; j < end; j++)
                if (p.pos[j])
                {
                    positions[i] = j;
                    return;
                }
            positions[i] = p.min;
        }
        _more = false;
    }

    int positions[MAX_SIZE];
    
private:
    const Pieces& _pieces;
    int _size;
    bool _more;
};

void try_all_combinations(char *rowcol, int nr, Clues& clues, Board &board, int pos, int off, int size, Pieces& pieces, int& modified, long& rfound)
{
    printf("try_all_combinations %s%d", rowcol, nr);

    Pieces try_pieces;
    try_pieces.nr = pieces.nr;
    for (int i = 0; i < size; i++)
        try_pieces.pieces[i].clear(size);

    Board combined_try_board;
    combined_try_board.clone(board);

#if 0
    printf("\n");
    for (int i = 0; i < size; i++)
        printf("%c", board[pos + off*i]);
    printf("\n");
#endif
    
    int tried = 0;
    int found = 0;
    for (PiecesCombinationsIterator it(pieces, size); it.more(); it.next())
    {
        Board try_board;
        try_board.copy(board);
        
        int j = 0;
        for (int i = 0; i < pieces.nr; i++)
        {
            int begin = it.positions[i];
            int end = begin + pieces.pieces[i].size;
            
            for (; j < begin; j++)
                try_board.assign(pos + off*j, EMPTY);
            for (; j < end; j++)
                try_board.assign(pos + off*j, FULL);
        }
        for (; j < size; j++)
            try_board.assign(pos + off*j, EMPTY);

        tried++;
        if (guess_solve(try_board, clues))
        {
            combined_try_board.combine(try_board);
    
            for (int i = 0; i < pieces.nr; i++)
                try_pieces.pieces[i].set(it.positions[i]);
            
#if 0            
            for (int i = 0; i < size; i++)
                printf("%c", try_board[pos + off*i]);
            printf("\n");
#endif
                
            found++;
        }
    }

    printf(" tried %d found %d", tried, found);
    
    if (found > 0)
    {
        int mod = 0;
        board.intergrate(combined_try_board, mod);
        modified += mod;
    }
    printf(" modified %d", modified);
    
//#ifdef SHOW_SOLVING        
//        printf("%s %2d: ", rowcol, nr);
//    if (mod)
//    {    
//        for (int j = 0; j < size; j++)
//            printf("%c", board[pos + off * j]);
//    }
//        printf(" %d (%d)\n", mod, found);
//#endif
    rfound = found;

    bool changed = false;
    pieces.update(try_pieces, changed);
    printf(" changed %d", changed);
    if (changed)
    {
        printf("\n");
        for (int i = 0; i < pieces.nr; i++)
        {
            Piece& p = try_pieces.pieces[i];
            printf("-- %d: %d-%d", i, p.min, p.max);
            for (int k = p.min; k < p.max; k++)
                if (p.pos[k])
                    printf(" %d", k);
            printf("\n");
        }
        modified++;
    }
    printf("\n");
}


//////


struct Combination
{
    char rc;
    int i;
    int d;
    int side;
    long max;
    long nr;
};

int compare_max(const void* vl, const void* vr)
{
    Combination *l = (Combination*)vl;
    Combination *r = (Combination*)vr;
    
    if (l->max < r->max)
        return -1;
    if (l->max > r->max)
        return 1;
    if (l->d < r->d)
        return -1;
    if (l->d > r->d)
        return 1;
    if (l->side < r->side)
        return -1;
    if (l->side > r->side)
        return 1;
    if (l->rc > r->rc)
        return -1;
    if (l->rc < r->rc)
        return 1;
    if (l->i < r->i)
        return -1;
    if (l->i > r->i)
        return 1;
    return 0;
}

long calc_max_combinations(const Pieces& pieces)
{
    long result = 1;
    for (int i = 0; i < pieces.nr; i++)
    {
        const Piece& p = pieces.pieces[i];
        
        int nr = 0;
        for (int j = p.min; j < p.max; j++)
            if (p.pos[j])
                nr++;
        
        result *= nr;
        
        if (result > 1000000)
            return 1000000;
    }
    return result;
}

void try_all_on_off(char *rowcol, int nr, const Clues& clues, Board &board, int pos, int off, int size, Pieces& pieces, int& modified)
{
    printf("try_all_on_off");
    for (int l = 0; l < m; l++)
    {
        int i = pos + off*l;
        
        if (board[i] == UNKNOWN)
        {
            Board combined_guesses;
            combined_guesses.clone(board);
            
            bool found = false;
            
            Board guess_board;
            guess_board.copy(board);
            guess_board.assign(i, FULL);
            
            if (guess_solve(guess_board, clues))
            {
                combined_guesses.combine(guess_board);
                found = true;
            }
            
            guess_board.copy(board);
            guess_board.assign(i, EMPTY);
            
            if (guess_solve(guess_board, clues))
            {
                combined_guesses.combine(guess_board);
                found = true;
            }
            
            if (found)
            {
                board.intergrate(combined_guesses, modified);
            }
            char s = board[i];
            printf("%c", s == EMPTY ? 'E' : s == FULL ? 'F' : '?');
        }
        else
            printf("%c", board[i]);
    }
}

char vals[1000];

#define SEARCH_MODE_NORMAL  '-'
#define SEARCH_MODE_FIRST   '1'
#define SEARCH_MODE_COUNTER 'C'

Alarm try_alarm;

bool try_all_in_square(int i, int j, int i_min, int i_max, int j_max, const Clues& clues, Board &combined_try_board, Board &try_board, int nr_unknown, bool &found, char search_mode, int depth)
{
    if (j == j_max)
    {
        found = true;
        combined_try_board.combine(try_board);
        //printf(".");
        int n_unknown = combined_try_board.nr_unknown;
        //printf("\n%d ", n_unknown);
        //vals[depth] = '\0';
        //printf("%s %c", vals,  search_mode);
        printf("\n%c", search_mode);
        if (n_unknown > nr_unknown)
            printf(" ***** %d", combined_try_board.count_unknown());
        return n_unknown < nr_unknown;
    }
    
    if (try_alarm.alarm())
    {
        return false;
    }
        
    int next_i = i + 1;
    int next_j = j;
    if (next_i == i_max)
    {
        next_i = i_min;
        next_j++;
    }
    
    int inj = i+n*j;
    if (try_board[inj] != UNKNOWN)
    {
        vals[depth] = try_board[inj];
        return try_all_in_square(next_i, next_j, i_min, i_max, j_max, clues, combined_try_board, try_board, nr_unknown, found, search_mode, depth+1);
    }

    char first = EMPTY;
    char second = FULL;
    if (search_mode == SEARCH_MODE_COUNTER && combined_try_board[inj] == EMPTY)
    {
        first = FULL;
        second = EMPTY;
    }
    
    Board next_try_board;
    next_try_board.copy(try_board);
    next_try_board.assign(inj, first);

    if (guess_solve(next_try_board, clues))
    {
        vals[depth] = first;
        //printf("%c", 'a'+depth);
        if (!try_all_in_square(next_i, next_j, i_min, i_max, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode, depth+1))
            return false;
    }
    if (search_mode != SEARCH_MODE_NORMAL && found)
        return true;
    
    next_try_board.copy(try_board);
    next_try_board.assign(inj, second);

    if (guess_solve(next_try_board, clues))
    {
        vals[depth] = second;
        //printf("%c", 'a'+depth);
        if (!try_all_in_square(next_i, next_j, i_min, i_max, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode, depth+1))
            return false;
    }
    
    return true;        
}

int times_called;

bool try_all_in_square_slow(int i_min, int i_max, int j_min, int j_max, const Clues& clues, Board &combined_try_board, Board &try_board, int nr_unknown, bool &found, char search_mode)
{
    times_called++;
    // scan all
    int still_unknown = 0;
    int first_unknown_inj;
    
    for (int i = i_min; i < i_max; i++)
        for (int j = j_min; j < j_max; j++)
        {
            int inj = i+n*j;
            if (try_board[inj] == UNKNOWN)
            {
                Board next_try_board;
                next_try_board.copy(try_board);
                next_try_board.assign(inj, EMPTY);
            
                bool empty_possible = guess_solve(next_try_board, clues);

                next_try_board.copy(try_board);
                next_try_board.assign(inj, FULL);
            
                bool full_possible = guess_solve(next_try_board, clues);
                
                //printf(" %d,%d %c%c", i,j, empty_possible ? 'E' : '_', full_possible ? 'F' : '_');
                if (empty_possible)
                {
                    if (full_possible)
                    {
                        if (still_unknown == 0)
                        {
                            first_unknown_inj = inj;
                        }
                        still_unknown++;
                    }
                    else
                        try_board.assign(inj, EMPTY);
                }
                else
                {
                    if (full_possible)
                        try_board.assign(inj, FULL);
                    else
                        return true; // no solution possible
                }                    
            }
        }
    
    //printf(" still_unknown %d\n", still_unknown);
    if (still_unknown == 0)
    {
        // We found a solution
        
        found = true;
        combined_try_board.combine(try_board);
        //printf(".");
        int n_unknown = combined_try_board.nr_unknown;
        //printf("\n%d ", n_unknown);
        //vals[depth] = '\0';
        //printf("%s %c", vals,  search_mode);
        printf("\n%c", search_mode);
        if (n_unknown > nr_unknown)
            printf(" ***** %d", combined_try_board.count_unknown());
        return n_unknown < nr_unknown;
    }
    
    int inj = first_unknown_inj;
    
    char first = EMPTY;
    char second = FULL;
    if (search_mode == SEARCH_MODE_COUNTER && combined_try_board[inj] == EMPTY)
    {
        first = FULL;
        second = EMPTY;
    }
    
    Board next_try_board;
    next_try_board.copy(try_board);
    next_try_board.assign(inj, first);

    if (guess_solve(next_try_board, clues))
    {
        //vals[depth] = first;
        //printf("%c", 'a'+depth);
        if (!try_all_in_square_slow(i_min, i_max, j_min, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode))
            return false;
    }
    if (search_mode != SEARCH_MODE_NORMAL && found && (search_mode != SEARCH_MODE_COUNTER || nr_unknown > 2))
        return true;
    
    next_try_board.copy(try_board);
    next_try_board.assign(inj, second);

    if (guess_solve(next_try_board, clues))
    {
        //vals[depth] = second;
        //printf("%c", 'a'+depth);
        if (!try_all_in_square_slow(i_min, i_max, j_min, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode))
            return false;
    }
    
    return true;        
}

bool try_all_in_square_find_one(int i_min, int i_max, int j_min, int j_max, const Clues& clues, Board &combined_try_board, Board &try_board, int nr_unknown, bool &found, char search_mode)
{
    try_alarm.set_alarm(3);
                
    if (try_all_in_square(i_min, j_min, i_min, i_max, j_max, clues, combined_try_board, try_board, nr_unknown, found, search_mode, 0))
        return true;
        
    if (try_alarm.went_off())
    {
        Board copy_try_board;
        copy_try_board.copy(try_board);
        times_called = 0;
        bool result = try_all_in_square_slow(i_min, i_max, j_min, j_max, clues, combined_try_board, copy_try_board, nr_unknown, found, search_mode);
        printf(" times_called = %d", times_called);
        return result;
    }
    
    return false;
}

bool try_all_in_square_counter(int i_min, int i_max, int j_min, int j_max, const Clues& clues, Board &combined_try_board, const Board &board, int nr_unknown, bool &found)
{
    for (int i = i_min; i < i_max; i++)
        for (int j = j_min; j < j_max; j++)
        {
            int inj = i+n*j;
            
            if (board[inj] == UNKNOWN && combined_try_board[inj] != UNKNOWN)
            {
                Board try_board;
                try_board.copy(board);
                try_board.assign(inj, combined_try_board[inj] == FULL ? EMPTY : FULL);
        
                if (guess_solve(try_board, clues))
                {
                    bool try_found = false;
                    bool result = try_all_in_square_find_one(i_min, i_max, j_min, j_max, clues, combined_try_board, try_board, nr_unknown, try_found, SEARCH_MODE_COUNTER);
                    if (try_found)
                        found = true;
                    if (!result)
                        return false;
                }
            }
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            int inj = i+n*j;
            
            if (   combined_try_board[inj] != UNKNOWN && board[inj] == UNKNOWN
                && (i < i_min || i_max <= i || j < j_min || j_max <= j))
            {
                Board try_board;
                try_board.copy(board);
                try_board.assign(inj, combined_try_board[inj] == FULL ? EMPTY : FULL);
        
                if (guess_solve(try_board, clues))
                {
                    bool try_found = false;
                    bool result = try_all_in_square_find_one(i_min, i_max, j_min, j_max, clues, combined_try_board, try_board, nr_unknown, try_found, SEARCH_MODE_COUNTER);
                    if (try_found)
                        found = true;
                    if (!result)
                        return false;
                }
            }
        }

    return true;
}

bool equal_unknowns(int unknowns, int size, int imin, int imax, int jmin, int jmax, const Board &board)
{
    int cu = unknowns;
    int ck = size - unknowns;
    for (int i = imin; i < imax; i++)
        for (int j = jmin; j < jmax; j++)
            if (board[i+n*j] == UNKNOWN)
            {
                if (cu == 0)
                    return false;
                cu--;
            }
            else
            {
                if (ck == 0)
                    return false;
                ck--;
            }
    return true;
}

void try_all_in_square(int unknowns, int nsize, int msize, const Clues& clues, Board &board, int &modified)
{
    int size = nsize * msize;
    if (unknowns > size)
        return;
        
    for (int jmin = 0, jmax = msize; jmax <= m; jmin++, jmax++)
    {
        for (int imin = 0, imax = nsize; imax <= m; imin++, imax++)
        {
            if (equal_unknowns(unknowns, size, imin, imax, jmin, jmax, board))
            {
                bool minimal = true;
                
                if (imin > 0)
                {
                    minimal = false;
                    int i = imin-1;
                    for (int j = jmin; j < jmax; j++)
                        if (board[i+n*j] == UNKNOWN)
                        {
                            minimal = true;
                            break;
                        }
                }
                if (minimal && imax < nsize)
                {
                    minimal = false;
                    int i = imax;
                    for (int j = jmin; j < jmax; j++)
                        if (board[i+n*j] == UNKNOWN)
                        {
                            minimal = true;
                            break;
                        }
                }
                if (minimal && jmin > 0)
                {
                    minimal = false;
                    int n_j = n*(jmin-1);
                    for (int i = imin; i < imax; i++)
                        if (board[i+n_j] == UNKNOWN)
                        {
                            minimal = true;
                            break;
                        }
                }
                if (minimal && jmax < msize)
                {
                    minimal = false;
                    int n_j = n*jmax;
                    for (int i = imin; i < imax; i++)
                        if (board[i+n_j] == UNKNOWN)
                        {
                            minimal = true;
                            break;
                        }
                }
                 
                if (minimal)
                {
                    printf("%3d %3d %3d: try_all_in_square(%2d-%2d, %2d-%2d) %d ", unknowns, nsize, msize, imin+1, imax, jmin+1, jmax, board.nr_unknown);
                    Board combined_try_board;
                    combined_try_board.clone(board);
        
                    Board try_board;
                    try_board.copy(board);
                    
                    bool found = false;
                    if (   try_all_in_square_find_one(imin, imax, jmin, jmax, clues, combined_try_board, try_board, board.nr_unknown, found, SEARCH_MODE_FIRST)
                        && found 
                        && try_all_in_square_counter(imin, imax, jmin, jmax, clues, combined_try_board, board, board.nr_unknown, found))
                    {
                        board.intergrate(combined_try_board, modified);
                    }
                }
                printf("\n");
            }
        }
    }
}

class CellInfoList;
class CellInfo
{
public:
    CellInfo() : filled(false), possible(false), nr_possible(0), tl(0), tr(0), bl(0), br(0), reduce(false), next_row(0), next_col(0) {}
    int i;
    int j;
    bool filled; // small hack: Initialized in Cell::Iterator::_valid()
    bool possible;
    int nr_possible;
    int tl;
    int tr;
    int bl;
    int br;
    bool reduce;
    bool operator==(const CellInfo& rhs) const { return i == rhs.i && j == rhs.j; }
    bool operator<(const CellInfo& rhs) const { return j < rhs.j || (j == rhs.j && i < rhs.i); }
    CellInfoList* next_row;
    CellInfoList* next_col;
};

class CellInfoList
{
public:
    CellInfoList(CellInfo* cellInfo, CellInfoList* list) : to(cellInfo), next(list), first(1), second(0) {}
    long first;
    long second;
    CellInfo* to;
    CellInfoList* next;
    
    class Iterator
    {
    public:
        Iterator(CellInfoList* list) : _list(list) { if (_list != 0) { i = _list->to->i; j = _list->to->j; } }
        bool more() { return _list != 0; }
        void next() { _list = _list->next; if (_list != 0) { i = _list->to->i; j = _list->to->j; } }
        CellInfoList& link() { return *_list; }
        CellInfo& value() { return *_list->to; }
        int i;
        int j;
    private:
        CellInfoList* _list;
    };
};

void add(CellInfoList** refCellList, CellInfo* cellInfo)
{
    while (*refCellList != 0 && (*refCellList)->to < cellInfo)
        refCellList = &(*refCellList)->next;
    
    if (*refCellList != 0 && (*refCellList)->to == cellInfo)
        (*refCellList)->first++;
    else
        (*refCellList) = new CellInfoList(cellInfo, *refCellList);
}

int count(CellInfoList* list)
{
    int r = 0;
    for (; list != 0; list = list->next)
        r++;
        
    return r;
}

class Cell
{
public:
    Cell() : calculated(false), reducable(false), next_reducable(0), _possible(0) {}
    ~Cell() { delete [] _possible; }
    int i;
    int j;
    Numbers row_numbers;
    bool *row_filled;
    Numbers col_numbers;
    bool *col_filled;
    int size;
    char b;
    bool calculated;
    bool reducable;
    Cell* next_reducable;

    void init()
    {
        int row_nr_used = row_numbers.init_trans(1);
        int col_nr_used = col_numbers.init_trans(row_nr_used);
        //printf("%d - %d = %d, %d - %d = %d\n",
        //    row_numbers.max, row_numbers.min, row_nr_used,
        //    col_numbers.max, col_numbers.min, col_nr_used);
        size = row_nr_used*col_nr_used;
        if (size > 0)
        {
            _possible = new CellInfo[row_nr_used*col_nr_used];
            for (Numbers::Iterator it_i(row_numbers); it_i.more(); it_i.next())
                for (Numbers::Iterator it_j(col_numbers); it_j.more(); it_j.next())
                {
                    CellInfo& p = _possible[it_i.trans() + it_j.trans()];
                    p.i = it_i;
                    p.j = it_j;
                }
        }
    }    
    CellInfo& value(Numbers::Iterator& it_i, Numbers::Iterator& it_j) 
    { 
        return _possible[it_i.trans() + it_j.trans()];
    }
    
    class Iterator
    {
    public:
        Iterator(Cell& cell) : _cell(cell), i(cell.row_numbers), j(cell.col_numbers)
        {
            filled = _cell.col_filled[j];
            if (!_valid())
                next();
        }
        Numbers::Iterator i;
        Numbers::Iterator j;
        bool filled;
        bool more() { return j.more(); }
        void next()
        {
            for(;;)
            {
                //fprintf(stderr, "next i=%d, j=%d\n", (int)i, (int)j);
                i.next();
                if (!i.more())
                {
                    i.init();
                    j.next();
                    if (!j.more())
                        return; // done
                    
                    filled = _cell.col_filled[j];    
                }
                if (_valid())
                    return; // found next
            }
        }
        CellInfo& value() { return _cell.value(i,j); }
    private:
        bool _valid()
        {
            //fprintf(stderr, "valid i=%d, j=%d\n", (int)i, (int)j);
            if (   _cell.row_filled[i] == filled
                && (   _cell.b == UNKNOWN
                    || (filled ? _cell.b == FULL : _cell.b == EMPTY)))
            {
                _cell.value(i,j).filled = filled; // -- small hack: This is the only place where it is initialized
                return true;
            }
            else
                return false;
        }
        Cell& _cell;
    };
        
private:
    CellInfo *_possible;
    int _row_trans[MAX_SIZE];
    int _col_trans[MAX_SIZE];
};

bool match_j(CellInfo& info1, CellInfo& info2)
{
    return (info1.filled || info2.filled) ? info2.j == info1.j + 1 : info2.j == info1.j;
}

bool match_i(CellInfo& info1, CellInfo& info2)
{
    return (info1.filled || info2.filled) ? info2.i == info1.i + 1 : info2.i == info1.i;
}

class CellMatrix
{
public:
    CellMatrix(int n, int m) : _n(n), _m(m), _cells(new Cell[n*m])
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                cell(i,j).i = i;
                cell(i,j).j = j;
            }
    }
    ~CellMatrix() { delete [] _cells; }
    inline Cell& cell(int i, int j) { return _cells[i+n*j]; }
    bool calculated(int i, int j) { return 0 <= i && i < _n && 0 <= j && j < _m && cell(i,j).calculated; }

private:
    int _n;
    int _m;
    Cell *_cells;
};

void find_reducable(int i, int j, CellMatrix &cellmat, Cell* &all_reducable)
{
    if (cellmat.calculated(i+1,j) && !cellmat.cell(i+1,j).reducable)
    {
        bool reducable = false;
        for (Cell::Iterator it1(cellmat.cell(i,j-1)); it1.more() && !reducable; it1.next())
            for (CellInfoList::Iterator it2(it1.value().next_col); it2.more() && !reducable; it2.next())
                if (it2.link().second != 0 && it2.link().first == 0)
                {
                    printf("bottom %d,%d -%d:%d-> %d,%d\n", i, j-1, it2.link().first, it2.link().second, i,j);
                    reducable = true;
                }
        if (reducable)
        {
            Cell& cell = cellmat.cell(i+1,j);
            cell.reducable = true;
            cell.next_reducable = all_reducable;
            all_reducable = &cell;
        }
    }
    
    if (cellmat.calculated(i,j+1) && !cellmat.cell(i,j+1).reducable)
    {
        bool reducable = false;
        for (Cell::Iterator it1(cellmat.cell(i-1,j)); it1.more() && !reducable; it1.next())
            for (CellInfoList::Iterator it2(it1.value().next_row); it2.more() && !reducable; it2.next())
                if (it2.link().second != 0 && it2.link().first == 0)
                {
                    printf("right %d,%d -%d:%d-> %d,%d\n", i-1, j, it2.link().first, it2.link().second, i,j);
                    reducable = true;
                }
        if (reducable)
        {
            Cell& cell = cellmat.cell(i,j+1);
            cell.reducable = true;
            cell.next_reducable = all_reducable;
            all_reducable = &cell;
        }
    }
    
    if (cellmat.calculated(i-1,j) && !cellmat.cell(i-1,j).reducable)
    {
        bool reducable = false;
        for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more() && !reducable; it1.next())
            for (CellInfoList::Iterator it2(it1.value().next_col); it2.more() && !reducable; it2.next())
                if (it2.link().first != 0 && it2.link().second == 0)
                {
                    printf("top %d,%d -%d:%d-> %d,%d\n", i-1, j-1, it2.link().first, it2.link().second, i-1,j);
                    reducable = true;
                }
        if (reducable)
        {
            Cell& cell = cellmat.cell(i-1,j);
            cell.reducable = true;
            cell.next_reducable = all_reducable;
            all_reducable = &cell;
        }
    }
    
    if (cellmat.calculated(i,j-1) && !cellmat.cell(i,j-1).reducable)
    {
        bool reducable = false;
        for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more() && !reducable; it1.next())
            for (CellInfoList::Iterator it2(it1.value().next_row); it2.more() && !reducable; it2.next())
                if (it2.link().first != 0 && it2.link().second == 0)
                {
                    printf("left %d,%d -%d:%d-> %d,%d\n", i-1, j-1, it2.link().first, it2.link().second, i,j-1);
                    reducable = true;
                }
        if (reducable)
        {
            Cell& cell = cellmat.cell(i,j-1);
            cell.reducable = true;
            cell.next_reducable = all_reducable;
            all_reducable = &cell;
        }
    }
}

void solve_extra(Clues &clues, Board &board)
{
    FILE* fresults = fopen("mega_nono_results.txt", "wt");
    
    // Initialize
    CellMatrix cellmat(n, m);
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            //printf("cell %d, %d:\n", i, j);
            Cell& cell = cellmat.cell(i,j);
            cell.b = board[i+n*j];
            cell.row_filled = clues.row[i].filled;
            cell.col_filled = clues.col[j].filled;
            clues.row[i].getNumbers(j, cell.row_numbers);
            clues.col[j].getNumbers(i, cell.col_numbers);
            cell.init();
        }

    printf("Cell(0,0)\n"); fflush(stdout);
    for (Cell::Iterator it(cellmat.cell(0,0)); it.more(); it.next())
    {
        it.value().possible = true;
        it.value().nr_possible++;
    }
        
    for (int j = 1; j < m; j++)
    {
        printf("Cell(0,%d)\n", j); fflush(stdout);
        for (Cell::Iterator it1(cellmat.cell(0,j-1)); it1.more(); it1.next())
            for (Cell::Iterator it2(cellmat.cell(0,j)); it2.more(); it2.next())
                if (match_i(it1.value(), it2.value()))
                {
                    it2.value().possible = true;
                    it2.value().nr_possible++;
                    add(&it1.value().next_col, &it2.value());
                }
    }
    
    for (int i = 1; i < n; i++)
    {
        printf("row %d\n", i);
        
        printf("Cell(%d,0)\n", i); fflush(stdout);
                
        for (Cell::Iterator it1(cellmat.cell(i-1,0)); it1.more(); it1.next())
            for (Cell::Iterator it2(cellmat.cell(i,0)); it2.more(); it2.next())
                if (match_j(it1.value(), it2.value()))
                {
                    it2.value().possible = true;
                    it2.value().nr_possible++;
                    add(&it1.value().next_row, &it2.value());
                }
                    
        for (int j = 1; j < m; j++)
        {
            printf("Fill cell(%d,%d) ", i, j); fflush(stdout);
            /*
            for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more(); it1.next())
                if (it1.value().possible)
                    for (Cell::Iterator it2(cellmat.cell(i-1,j)); it2.more(); it2.next())
                        if (it2.value().possible && match_i(it1, it2))
                            for (Cell::Iterator it3(cellmat.cell(i,j-1)); it3.more(); it3.next())
                                if (it3.value().possible && match_j(it1, it3))
                                    for (Cell::Iterator it4(cellmat.cell(i,j)); it4.more(); it4.next())
                                        if (match_i(it3, it4) && match_j(it2, it4))
                                        {
                                            it4.value().possible = true;
                                            it1.value().br++;
                                            it2.value().bl++;
                                            it3.value().tr++;
                                            it4.value().tl++;
                                        }
            */
            long rows = 0;
            long cols = 0;
            long rols = 0;
            int nr_created = 0;
            for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more(); it1.next())
                if (it1.value().possible)
                {
                    int c1 = count(it1.value().next_row); 
                    int c2 = count(it1.value().next_col); 
                    rows += c1;
                    cols += c2;
                    rols += c1*c2;
                    for (CellInfoList::Iterator it2(it1.value().next_col); it2.more(); it2.next())
                        if (it2.link().first != 0 && it2.value().possible && match_i(it1.value(), it2.value()))
                            for (CellInfoList::Iterator it3(it1.value().next_row); it3.more(); it3.next())
                                if (it3.link().first != 0 && it3.value().possible && match_j(it1.value(), it3.value()))
                                    for (Cell::Iterator it4(cellmat.cell(i,j)); it4.more(); it4.next())
                                        if (match_i(it3.value(), it4.value()) && match_j(it2.value(), it4.value()))
                                        {
                                            //printf(" - %d:%d %d,%d %d,%d %d,%d %d,%d: add\n",
                                            //        i,j, it1.value().i, it1.value().j, it2.value().i, it2.value().j, it3.value().i, it3.value().j, it4.value().i, it4.value().j);
                                            nr_created++;
                                            it4.value().possible = true;
                                            it4.value().nr_possible++;
                                            //printf("add %d,%d#%d,%d %d,%d#%d,%d\n",
                                            //        i-1,j, it2.value().i, it2.value().j, 
                                            //        i,j, it4.value().i, it4.value().j);
                                            add(&it2.value().next_row, &it4.value());
                                            //printf("add %d,%d#%d,%d %d,%d#%d,%d\n",
                                            //        i,j-1, it3.value().i, it3.value().j, 
                                            //        i,j, it4.value().i, it4.value().j);
                                            add(&it3.value().next_col, &it4.value());
                                            it2.link().second++;
                                            it3.link().second++;
                                            it1.value().br++;
                                            it2.value().bl++;
                                            it3.value().tr++;
                                            it4.value().tl++;
                                        }
                }
            cellmat.cell(i,j).calculated = true;
            
            
            bool all = true;
            int count_empty = 0;
            int count_filled = 0;
            for (Cell::Iterator it(cellmat.cell(i,j)); it.more(); it.next())
                if (it.value().nr_possible > 0)
                {
                    if (it.value().filled)
                        count_filled++;
                    else
                        count_empty++;
                }
                else
                    all = false;
            printf("%5d %c %dx%d=%d created = %d", count_filled + count_empty, all ? 'T' : 'F', rows, cols, rols, nr_created);
            for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more(); it1.next())
                if (it1.value().br == 0)
                    printf(" br:%d:%d", (int)it1.i, (int)it1.j);
            for (Cell::Iterator it2(cellmat.cell(i-1,j)); it2.more(); it2.next())
                if (it2.value().bl == 0)
                    printf(" bl:%d:%d", (int)it2.i, (int)it2.j);
            for (Cell::Iterator it3(cellmat.cell(i,j-1)); it3.more(); it3.next())
                if (it3.value().tr == 0)
                    printf(" tr:%d:%d", (int)it3.i, (int)it3.j);
            for (Cell::Iterator it4(cellmat.cell(i,j)); it4.more(); it4.next())
                if (it4.value().tl == 0)
                    printf(" tl:%d:%d", (int)it4.i, (int)it4.j);
            printf("\n");
            if (cellmat.cell(i,j).b == UNKNOWN)
            {
                if (count_filled = 0)
                    printf("***** Cell(%d,%d) is empty!!!\n");
                if (count_empty = 0)
                    printf("***** Cell(%d,%d) is filled!!!\n");
            }
            
            // Reducing
            Cell* all_reducable = 0;
            
            find_reducable(i,j, cellmat, all_reducable);
            
            while (all_reducable != 0)
            {
                Cell* cell = all_reducable;
                cell->reducable = false;
                all_reducable = cell->next_reducable;
                cell->next_reducable = 0;
                
                int i = cell->i;
                int j = cell->j;
                
                printf("Reduce cell(%d,%d) ", i, j); fflush(stdout);
                bool top_calculated = cellmat.calculated(i-1,j);
                bool left_calculated = cellmat.calculated(i,j-1);
                bool bottom_calculated = cellmat.calculated(i+1,j);
                bool right_calculated = cellmat.calculated(i,j+1);
                 
                int nr_reduced = 0;
                int nr_left = 0;
                for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more(); it1.next())
                    if (it1.value().possible)
                        for (CellInfoList::Iterator it2(it1.value().next_col); it2.more(); it2.next())
                            if (!(it2.link().first == 0 && it2.link().second == 0) && it2.value().possible && match_i(it1.value(), it2.value()))
                                for (CellInfoList::Iterator it3(it1.value().next_row); it3.more(); it3.next())
                                    if (!(it3.link().first == 0 && it3.link().second == 0) && it3.value().possible && match_j(it1.value(), it3.value()))
                                        for (Cell::Iterator it4(cellmat.cell(i,j)); it4.more(); it4.next())
                                            if (match_i(it3.value(), it4.value()) && match_j(it2.value(), it4.value()))
                                            {
                                                CellInfoList::Iterator it5(it3.value().next_col);
                                                for (; it5.more(); it5.next())
                                                    if (it5.value() == it4.value())
                                                        break;
                                                CellInfoList::Iterator it6(it2.value().next_row);
                                                for (; it6.more(); it6.next())
                                                    if (it6.value() == it4.value())
                                                        break;
                                                
                                                if (   !it5.more() || !(it5.value() == it4.value())
                                                    || !it6.more() || !(it6.value() == it4.value()))
                                                {
                                                    printf("Error in reduce loops\n");
                                                    exit(1);
                                                }
                                                
                                                /*printf(" - %d:%d %d,%d %d,%d %d,%d %d,%d:",
                                                        i, j, it1.value().i, it1.value().j, it2.value().i, it2.value().j, it3.value().i, it3.value().j, it4.value().i, it4.value().j);
                                                if (top_calculated)
                                                    printf(" top %d,%d", it2.link().first, it2.link().second);
                                                else
                                                    printf(" (top %d,%d)", it2.link().first, it2.link().second);
                                                if (left_calculated)
                                                    printf(" left %d,%d", it3.link().first, it3.link().second);
                                                else
                                                    printf(" (left %d,%d)", it3.link().first, it3.link().second);
                                                if (bottom_calculated)
                                                    printf(" bottom %d,%d", it5.link().second, it5.link().first);
                                                else
                                                    printf(" (bottom %d,%d)", it5.link().second, it5.link().first);
                                                if (right_calculated)
                                                    printf(" right %d,%d", it6.link().second, it6.link().first);
                                                else
                                                    printf(" (right %d,%d)", it6.link().second, it6.link().first);
                                                */
                                                if (   it2.link().second == 0
                                                    || it3.link().second == 0
                                                    || it5.link().first == 0
                                                    || it6.link().first == 0)
                                                {
                                                    //printf(" already reduced\n");
                                                }
                                                else if (   (top_calculated && it2.link().first == 0 && it2.link().second > 0)
                                                         || (left_calculated && it3.link().first == 0 && it3.link().second > 0)
                                                         || (bottom_calculated && it5.link().second == 0 && it5.link().first > 0)
                                                         || (right_calculated && it6.link().second == 0 && it6.link().first > 0))
                                                {
                                                    //printf(" = reduce\n");
                                                    nr_reduced++;
                                                    if (it2.link().second <= 0 || it3.link().second <= 0 || it5.link().first <= 0 || it6.link().first <= 0)
                                                    {
                                                        printf("illvalue\n");
                                                        exit(1);
                                                    }
                                                    it4.value().nr_possible--;
                                                    it2.link().second--;
                                                    it3.link().second--;
                                                    it5.link().first--;
                                                    it6.link().first--;
                                                    it1.value().br--;
                                                    it2.value().bl--;
                                                    it3.value().tr--;
                                                    it4.value().tl--;
                                                }
                                                else
                                                {
                                                    //printf(" = keep\n");
                                                    nr_left++;
                                                }
                                            }
                bool all = true;
                int count_empty = 0;
                int count_filled = 0;
                for (Cell::Iterator it(cellmat.cell(i,j)); it.more(); it.next())
                    if (it.value().nr_possible > 0)
                    {
                        if (it.value().filled)
                            count_filled++;
                        else
                            count_empty++;
                    }
                    else
                        all = false;
                printf("%5d %c %dx%d=%d reduced = %d, nr_left = %d\n", count_filled + count_empty, all ? 'T' : 'F', rows, cols, rols, nr_reduced, nr_left);
                /*for (Cell::Iterator it1(cellmat.cell(i-1,j-1)); it1.more(); it1.next())
                    if (it1.value().br == 0)
                        printf(" br:%d:%d", (int)it1.i, (int)it1.j);
                for (Cell::Iterator it2(cellmat.cell(i-1,j)); it2.more(); it2.next())
                    if (it2.value().bl == 0)
                        printf(" bl:%d:%d", (int)it2.i, (int)it2.j);
                for (Cell::Iterator it3(cellmat.cell(i,j-1)); it3.more(); it3.next())
                    if (it3.value().tr == 0)
                        printf(" tr:%d:%d", (int)it3.i, (int)it3.j);
                for (Cell::Iterator it4(cellmat.cell(i,j)); it4.more(); it4.next())
                    if (it4.value().tl == 0)
                        printf(" tl:%d:%d", (int)it4.i, (int)it4.j);
                printf("\n");
                */
                if (cellmat.cell(i,j).b == UNKNOWN)
                {
                    if (count_filled = 0)
                        printf("***** Cell(%d,%d) is empty!!!\n");
                    if (count_empty = 0)
                        printf("***** Cell(%d,%d) is filled!!!\n");
                }
                if (nr_left == 0)
                {
                    exit(1);
                }
                find_reducable(i,j, cellmat, all_reducable);
            }
        }

        for (int i2 = 0; i2 < i; i2++)
        {
            for (int j = 0; j < m; j++)
            {
                bool all = true;
                int count_empty = 0;
                int count_filled = 0;
                for (Cell::Iterator it(cellmat.cell(i2,j)); it.more(); it.next())
                    if (it.value().nr_possible > 0)
                    {
                        if (it.value().filled)
                            count_filled++;
                        else
                            count_empty++;
                    }
                    else
                        all = false;
                char b = cellmat.cell(i2,j).b;
                fprintf(fresults, "%5d%5d%s", count_empty, count_filled, 
                    b == FULL ? "* " :
                    b == EMPTY ? "_ " :
                    count_filled == 0 ? "*!" :
                    count_empty == 0 ? "_!" : 
                    "? ");
            }
            fprintf(fresults, "\n");
        }
        fprintf(fresults, "\n");
    }
    
    fflush(stdout);
}

bool solve(Clues &clues, Board &board)
{
    fprintf(stderr, "solve\n");
    
    int l = 0;
    int modified;
    int max_nr_nodes = 0;
    do
    {
        modified = 0;

        for (int i = 0; i < n; i++)
            if (board.rowneeds[i].needed(1) && !reason("rij", i+1, board, i, n, m, clues.row[i], modified))
                return false;
            else
                board.rowneeds[i].done(1);
        for (int j = 0; j < m; j++)
            if (board.colneeds[j].needed(1) && !reason("colom", j+1, board, j*n, 1, n, clues.col[j], modified))
                return false;
            else
                board.colneeds[j].done(1);

        if (modified > 0)
            l = 0;

        if (modified == 0)
        {
            Combination combinations[2*MAX_SIZE];
            
            for (int i = 0; i < n; i++)
            {
                combinations[i].rc = 'r';
                combinations[i].i = i;
                if (i < n-i)
                {
                    combinations[i].d = i;
                    combinations[i].side = 1;
                }
                else
                {
                    combinations[i].d = n-i;
                    combinations[i].side = 3;
                }
                combinations[i].max = calc_max_combinations(clues.row[i]);
                combinations[i].nr = combinations[i].max;
            }
            for (int i = 0; i < m; i++)
            {
                combinations[n+i].rc = 'c';
                combinations[n+i].i = i;
                if (i < m-i)
                {
                    combinations[n+i].d = i;
                    combinations[n+i].side = 2;
                }
                else
                {
                    combinations[n+i].d = m-i;
                    combinations[n+i].side = 4;
                }
                combinations[n+i].max = calc_max_combinations(clues.col[i]);
                combinations[n+i].nr = combinations[n+i].max;
            }
            
            qsort(combinations, n+m, sizeof(Combination), compare_max);

#ifdef GUESS_SOMETHING
            for (int j = 0; j < n+m && modified == 0; j++)
            {
                int i = combinations[j].i;
                if (combinations[j].rc == 'r')
                {
                    guess_something("rij", i+1, clues, board, i, n, m, clues.row[i], modified);
                    //if (modified == 0)
                    //    try_all_on_off("rij", i+1, clues, board, i, n, m, clues.row[i], modified);
                }
                else
                {
                    guess_something("colom", i+1, clues, board, i*n, 1, n, clues.col[i], modified);
                    //if (modified == 0)
                    //    try_all_on_off("colom", i+1, clues, board, i*n, 1, n, clues.col[i], modified);
                }
                    
            }
#endif

            for (int j = 0; j < n+m && modified == 0; j++)
            {
                if (combinations[j].max > 1 && combinations[j].max < 1000)
                {
                    printf("%c%d: %ld\n", combinations[j].rc, combinations[j].i, combinations[j].max);
                    
                    int i = combinations[j].i;
                    if (combinations[j].rc == 'r')
                        try_all_combinations("rij", i+1, clues, board, i, n, m, clues.row[i], modified, combinations[j].nr);
                    else
                        try_all_combinations("colom", i+1, clues, board, i*n, 1, n, clues.col[i], modified, combinations[i].nr);
                }
            }

#ifdef TRY_ALL_IN_SQUARE
            for (int unknowns = 2; modified == 0 && unknowns <= 200; unknowns++)
            {
                for (int size = 4; size < n * m; size++)
                    if (size >= unknowns)
                    {
                        int size_2 = size / 2;
                        int nsize, msize = size_2;
                        for (nsize = 2; msize > 2 && nsize <= size_2; nsize++)
                        {
                            for (; msize >= 2 && nsize * msize > size; msize--)
                                ;
                            if (nsize * msize == size && nsize <= n && msize <= m)
                                try_all_in_square(unknowns, nsize, msize, clues, board, modified);
                        }
                    }
            }
#endif

            if (modified == 0)
            {
                /* insert your code here */
            }
                            
            if (modified > 0)
            {
                board.resetneeds();
            }
            
        }
        
        printf("\nmodified = %d\n", modified);
        printsol(board);
        //dumpboard(board);
    }
    while (modified > 0);
  
       solve_extra(clues, board);
       
       fflush(stdout);

    return true;
}

Clues clues;
Board board;

int main(int argc, char *argv[])
{
    if (argc < 2)
    {
        printf("%s <fn> [<fn>]\n", argv[0]);
        return 0;
    }
    
    if (!read_clues(argv[1], clues))
    {
        printf("\n\nread error\n");
        return 0;
    }
    //write_pieces(clues);

    board.clear();

    if (argc > 2)
        read_prev_board(argv[2], board);
    if (!solve(clues, board))
        printf("\nNo solution\n");
    printf("\n\ndone\n");
    return 0;
}