/*  Nonogram2ExactCover - converting nonograms to Exact Covers

    The command line options are:
        [-01 [-no_exact]] [-logic] <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 generate an Exact Cover representing
    the given Nonogram.

    This program is refered to at http://www.iwriteiam.nl/D0906.html#28
    
    The implementation makes use of dancing links, a technique suggested
    by D.E. Knuth. See: http://en.wikipedia.org/wiki/Dancing_Links
    
    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;

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

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

    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;
    }
    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;
    }
};

struct Pieces
{
    int nr;
    Piece pieces[MAX_SIZE];
    
    void add(int v)
    {
        pieces[nr++].size = v;
    }
    
    void init(int size)
    {
        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;
        }
    }
};

int n;
int m;
int nm;

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



struct Clues
{
    Pieces row[MAX_SIZE];
    Pieces col[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");
    if (f == 0)
    {
        printf("Cannot open file '%s'\n", fn);
        return false;
    }
    
    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);
        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);
        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);
        return false;
    }
    for (int i = 0; i < n; i++)
    {
        read_line(f, line, more);
        if (!more)
        {    fclose(f);
            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);
        return false;
    }
    for (int i = 0; i < m; i++)
    {
        read_line(f, line, more);
        if (!more)
        {    fclose(f);
            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 read_partial_solution(char *fn, char* partial_sol)
{
    FILE* f = fopen(fn, "rt");
    if (f == 0)
    {
        printf("Cannot open file '%s'\n", fn);
        return;
    }
    
    for (int row_nr = 0; row_nr < n; row_nr++)
    {
        char line[1000];
        fgets(line, 999, f);
        
        for (int col_nr = 0; col_nr < m; col_nr++)
            *partial_sol++ = line[col_nr];
    }
}        

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;
};


Clues clues;

char *partial_sol;

void gen_all_perm(bool mode_exact, bool mode_01)
{
    bool row_solved[MAX_SIZE];
    for (int row_nr = 0; row_nr < n; row_nr++)
        row_solved[row_nr] = true;
    bool col_solved[MAX_SIZE];
    for (int col_nr = 0; col_nr < m; col_nr++)
        col_solved[col_nr] = true;
    {
        char *s = partial_sol;
        for (int row_nr = 0; row_nr < n; row_nr++)
        {
            for (int col_nr = 0; col_nr < m; col_nr++)
                if (*s++ == '?')
                {
                    col_solved[col_nr] = false;
                    row_solved[row_nr] = false;
                }
        }
    }
    
    for (int row_nr = 0; row_nr < n; row_nr++)
    {
        fprintf(stderr, "row %d\n", row_nr);
        if (row_solved[row_nr])
            continue;
            
        Pieces& pieces = clues.row[row_nr];
        
        for (int i = 0; i < pieces.nr; i++)
        {
            Piece& p = pieces.pieces[i];
            
            for (int j = p.min; j < p.max; j++)
            {
                int col_nr = j - 1;
                bool matches = col_nr < 0 || partial_sol[m*row_nr + col_nr] != FULL;
                col_nr++;
                for (int k = 0; k < p.size && matches; k++, col_nr++)
                    if (partial_sol[m*row_nr + col_nr] == EMPTY)
                        matches = false;
                if (matches && col_nr < m && partial_sol[m*row_nr + col_nr] == FULL)
                    matches = false;

                if (!matches)                    
                    p.reset(j);
            }
        }
        
        for (PiecesCombinationsIterator it(pieces, m); it.more(); it.next())
        {
            int values[MAX_SIZE];
            
            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++)
                    values[j] = 0;
                for (; j < end; j++)
                    values[j] = 1;
            }
            for (; j < m; j++)
                values[j] = 0;
                
            bool matches = true;
            for (int col_nr = 0; col_nr < m; col_nr++)
            {
                if (partial_sol[m*row_nr + col_nr] == (values[col_nr] ? '_' : '*'))
                {
                    matches = false;
                    break;
                }
            }
            
            if (matches)
            {
                if (mode_exact)
                {
                    for (int i = 0; i < n; i++)
                        if (!row_solved[i])
                            printf("%c", (i == row_nr) ? '1' : '0');
                    for (int i = 0; i < m; i++)
                        if (!col_solved[i])
                            printf("0");
                }
                
                char *s = partial_sol;
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < m; j++)
                        if (*s++ == '?')
                            if (mode_01)
                                printf("%s", i != row_nr ? "00" : values[j] == 1 ? "10" : "01");
                            else
                                printf("%c", (i == row_nr && values[j] == 1) ? '1' : '0');
                                
                printf(" row %2d: ", row_nr+1);
                
                for (int i = 0; i < m; i++)
                    printf("%d", values[i]);
                    
                for (int j = 0; j < pieces.nr; j++)
                {
                    const Piece& p = pieces.pieces[j];
                    printf(" %d", p.size);
                }
                printf("\n");
            }
        }
    }

    for (int col_nr = 0; col_nr < m; col_nr++)
    {
        if (col_solved[col_nr])
            continue;
            
        fprintf(stderr, "col %d\n", col_nr);
        const Pieces& pieces = clues.col[col_nr];
            
        for (PiecesCombinationsIterator it(pieces, n); it.more(); it.next())
        {
            int values[MAX_SIZE];
            
            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++)
                    values[j] = 0;
                for (; j < end; j++)
                    values[j] = 1;
            }
            for (; j < n; j++)
                values[j] = 0;
            
            bool matches = true;
            for (int row_nr = 0; row_nr < n; row_nr++)
            {
                if (partial_sol[m*row_nr + col_nr] == (values[row_nr] ? '_' : '*'))
                {
                    matches = false;
                    break;
                }
            }
            
            if (matches)
            {
                if (mode_exact)
                {
                    for (int i = 0; i < n; i++)
                        if (!row_solved[i])
                            printf("0");
                    for (int i = 0; i < m; i++)
                        if (!col_solved[i])
                            printf("%c", (i == col_nr) ? '1' : '0');
                }
                                    
                char *s = partial_sol;
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < m; j++)
                        if (*s++ == '?')
                            if (mode_01)
                                printf("%s", j != col_nr ? "00" : values[i] == 1 ? "01" : "10");
                            else
                                printf("%c", (j == col_nr && values[i] == 0) ? '1' : '0');
                        
                printf(" col %2d: ", col_nr+1);
                
                for (int i = 0; i < n; i++)
                    printf("%d", values[i]);
                    
                for (int j = 0; j < pieces.nr; j++)
                {
                    const Piece& p = pieces.pieces[j];
                    printf(" %d", p.size);
                }
                printf("\n");
            }
        }
    }
}

class Logic
{
public:

    int from;
    int to;
    
    int nr_positions_used;
};


#define MAX_VALUES 20

bool comp_details = false;

class ConnectCode
{
public:
    ConnectCode() : _nr(0), _nr_bits(0) {}

    void setEmpty()
    {
        _val = 0;
    }

    void setValue(int v, bool inverse)
    {
        _inv = inverse;
        for (int i = 0; i < _nr; i++)
            if (_values[i] == v)
            {
                _val = i+1;    
                return;
            }
        if (_nr == MAX_VALUES)
        {
            printf("Error: increase MAX_VALUES\n");
            exit(1);
        }
        _values[_nr++] = v;
        _val = _nr;
        if (_nr == 2)
            _nr_bits = 2;
        if (_nr == 5)
            _nr_bits = 3;
        if (_nr == 9)
            _nr_bits = 4;
        if (_nr == 17)
            _nr_bits = 5;
        if (_nr == 31)
            _nr_bits = 6;
    }
    
    void setFull()
    {
        _val = -1;        
    }
    
    void print()
    {
        if (_nr_bits == 0)
            return;
            
        //printf("<");
        if (_val == -1)
        {
            for (int i = 0; i < _nr_bits; i++)
                printf("1");
        }
        else if (_val == 0)
        {
            for (int i = 0; i < _nr_bits; i++)
                printf("0");
        }
        else if (_inv)
        {
            int x = 1;
            for (int i = 0; i < _nr_bits; i++, x *= 2)
                printf("%c", (_val-1) & x ? '0' : '1');
        }
        else
        {
            int x = 1;
            for (int i = 0; i < _nr_bits; i++, x *= 2)
                printf("%c", (_val-1) & x ? '1' : '0');
        }
        //printf(">");
    }
    void printcomp()
    {
        if (comp_details)
        {
            if (_nr_bits == 0)
                ;
            else if (_val == -1)
                printf("*");
            else if (_val == 0)
                printf(" ");
            else
                printf("%c", (_inv ? 'a' : 'A') + _val - 1);
        }
    }
private:
    int _nr;
    int _nr_bits;
    int _values[MAX_VALUES];
    int _val;
    bool _inv;
};

class Board
{
public:
    void clear()
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                field[i][j] = '_';
                rows[i][j].setEmpty();
                cols[i][j].setEmpty();
            }    
    }
    void print(bool is_row)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                if (field[i][j] == '1')
                    printf("%s", is_row ? "100" : "011");
                else if (field[i][j] == '0')
                    printf("%s", is_row ? "101" : "010");
                else
                    printf("000");
                rows[i][j].print();
                cols[i][j].print();
            }
    }
            
    char field[MAX_SIZE][MAX_SIZE];
    ConnectCode rows[MAX_SIZE][MAX_SIZE-1];
    ConnectCode cols[MAX_SIZE][MAX_SIZE-1];
};

void gen_logic()
{
    Board board;
        
    for (int round = 0; round < 2; round++)
    {
        for (int row_nr = 0; row_nr < n; row_nr++)
        {
            fprintf(stderr, "%s row %d\n", round == 0 ? "Analyze" : "Generate", row_nr);
                
            Pieces& pieces = clues.row[row_nr];
            
            if (pieces.nr == 0)
            {
                board.clear();
                
                for (int col_nr = 0; col_nr < m; col_nr++)
                {
                    board.field[row_nr][col_nr] = '0';
                    if (col_nr < m-1)
                        board.rows[row_nr][col_nr].setFull();
                }
            
                if (round == 1)
                {
                    board.print(true);
                    printf(" row %2d: ", row_nr+1);
                    for (int col_nr = 0; col_nr < m; col_nr++)
                    {
                        printf("%c", board.field[row_nr][col_nr]);
                        if (col_nr < m-1)
                            board.rows[row_nr][col_nr].printcomp();
                    }
                    printf("\n");
                }
            }
            
            for (int i = 0; i < pieces.nr; i++)
            {
                Piece& piece = pieces.pieces[i];
                bool first = i == 0;
                bool last = i == pieces.nr-1;
                
                char name[MAX_SIZE];
                
                for (int p = piece.min; p < piece.max; p++)
                {
                    board.clear();
        
                    if (first)
                    {
                        for (int col_nr = 0; col_nr < p; col_nr++)
                        {
                            board.field[row_nr][col_nr] = '0';
                            board.rows[row_nr][col_nr].setFull();
                        }
                    }
                    else
                        board.rows[row_nr][p-1].setValue(i-1, true);
                    
                    for (int col_nr = p; col_nr < p + piece.size; col_nr++)
                    {
                        board.field[row_nr][col_nr] = '1';
                        board.rows[row_nr][col_nr].setFull();
                    }
                    
                    if (last)
                    {
                        for (int col_nr = p + piece.size; col_nr < m; col_nr++)
                        {
                            board.field[row_nr][col_nr] = '0';
                            board.rows[row_nr][col_nr].setFull();
                        }
                    }
                    else
                    {
                        int col_nr = p + piece.size;
                        board.field[row_nr][col_nr] = '0';
                        board.rows[row_nr][col_nr].setValue(i, false);
                    }
                    
                    if (round == 1)
                    {
                        board.print(true);
                        printf(" row %2d: ", row_nr+1);
                        for (int col_nr = 0; col_nr < m; col_nr++)
                        {
                            printf("%c", board.field[row_nr][col_nr]);
                            if (col_nr < m-1)
                                board.rows[row_nr][col_nr].printcomp();
                        }
                        printf("\n");
                    }
                }
                
                if (!last)
                {
                    int pmaxnext = pieces.pieces[i+1].max;
                    
                    for (int col_nr = piece.min + piece.size + 1; col_nr < pmaxnext-1; col_nr++)
                    {
                        board.clear();
                        
                        board.rows[row_nr][col_nr-1].setValue(i, true);
                        board.field[row_nr][col_nr] = '0';
                        board.rows[row_nr][col_nr].setValue(i, false);

                        if (round == 1)
                        {
                            board.print(true);
                            printf(" row %2d: ", row_nr+1);
                            for (int col_nr = 0; col_nr < m; col_nr++)
                            {
                                printf("%c", board.field[row_nr][col_nr]);
                                if (col_nr < m-1)
                                    board.rows[row_nr][col_nr].printcomp();
                            }
                            printf("\n");
                        }
                    }
                }                    
            }
        }

        for (int col_nr = 0; col_nr < n; col_nr++)
        {
            fprintf(stderr, "%s col %d\n", round == 0 ? "Analyze" : "Generate", col_nr);
                
            Pieces& pieces = clues.col[col_nr];
            
            if (pieces.nr == 0)
            {
                board.clear();
                
                for (int row_nr = 0; row_nr < n; row_nr++)
                {
                    board.field[row_nr][col_nr] = '0';
                    if (row_nr < n-1)
                        board.cols[row_nr][col_nr].setFull();
                }
            
                if (round == 1)
                {
                    board.print(false);
                    printf(" col %2d: ", col_nr+1);
                    for (int row_nr = 0; row_nr < m; row_nr++)
                    {
                        printf("%c", board.field[row_nr][col_nr]);
                        if (row_nr < n-1)
                            board.cols[row_nr][col_nr].printcomp();
                    }
                    printf("\n");
                }
            }
            
            for (int i = 0; i < pieces.nr; i++)
            {
                Piece& piece = pieces.pieces[i];
                bool first = i == 0;
                bool last = i == pieces.nr-1;
                
                char name[MAX_SIZE];
                
                for (int p = piece.min; p < piece.max; p++)
                {
                    board.clear();
        
                    if (first)
                    {
                        for (int row_nr = 0; row_nr < p; row_nr++)
                        {
                            board.field[row_nr][col_nr] = '0';
                            board.cols[row_nr][col_nr].setFull();
                        }
                    }
                    else
                        board.cols[p-1][col_nr].setValue(i-1, true);
                    
                    for (int row_nr = p; row_nr < p + piece.size; row_nr++)
                    {
                        board.field[row_nr][col_nr] = '1';
                        board.cols[row_nr][col_nr].setFull();
                    }
                    
                    if (last)
                    {
                        for (int row_nr = p + piece.size; row_nr < m; row_nr++)
                        {
                            board.field[row_nr][col_nr] = '0';
                            board.cols[row_nr][col_nr].setFull();
                        }
                    }
                    else
                    {
                        int row_nr = p + piece.size;
                        board.field[row_nr][col_nr] = '0';
                        board.cols[row_nr][col_nr].setValue(i, false);
                    }
                    
                    if (round == 1)
                    {
                        board.print(false);
                        printf(" col %2d: ", col_nr+1);
                        for (int row_nr = 0; row_nr < n; row_nr++)
                        {
                            printf("%c", board.field[row_nr][col_nr]);
                            if (row_nr < n-1)
                                board.cols[row_nr][col_nr].printcomp();
                        }
                        printf("\n");
                    }
                }
                
                if (!last)
                {
                    int pmaxnext = pieces.pieces[i+1].max;
                    
                    for (int row_nr = piece.min + piece.size + 1; row_nr < pmaxnext-1; row_nr++)
                    {
                        board.clear();
                        
                        board.cols[row_nr-1][col_nr].setValue(i, true);
                        board.field[row_nr][col_nr] = '0';
                        board.cols[row_nr][col_nr].setValue(i, false);

                        if (round == 1)
                        {
                            board.print(false);
                            printf(" col %2d: ", col_nr+1);
                            for (int row_nr = 0; row_nr < m; row_nr++)
                            {
                                printf("%c", board.field[row_nr][col_nr]);
                                if (row_nr < n-1)
                                    board.cols[row_nr][col_nr].printcomp();
                            }
                            printf("\n");
                        }
                    }
                }                    
            }
        }

    }    
}

int main(int argc, char *argv[])
{
    char* clues_fn = 0;
    char* partial_sol_fn = 0;
    bool mode_exact = true;
    bool mode_01 = false;
    bool mode_logic = false;
    
    for (int i = 1; i < argc; i++)
    {
        if (strcmp(argv[i], "-01") == 0)
            mode_01 = true;
        else if (strcmp(argv[i], "-no_exact") == 0)
            mode_exact = false;
        else if (strcmp(argv[i], "-logic") == 0)
            mode_logic = true;
        else if (strcmp(argv[i], "-comp_details") == 0)
            comp_details = true;
        else if (clues_fn == 0)
            clues_fn = argv[i];
        else if (partial_sol_fn == 0)
            partial_sol_fn = argv[i];
        else
            printf(" skipped argument '%s'\n", argv[i]);
    }
    
    if (clues_fn == 0)
    {
        printf("%s [-01 [-no_exact]] [-logic] <filename> [<filename2>]\n", argv[0]);
        return 0;
    }
    
    if (!read_clues(clues_fn, clues))
    {
        printf("\n\nread error\n");
        return 0;
    }
    
    partial_sol = (char*)malloc(sizeof(char)*(n*m+1));
    for (int i = 0; i < n*m; i++)
        partial_sol[i] = '?';
    partial_sol[n*m] = '\0';
    
    if (partial_sol_fn != 0)
    {
        read_partial_solution(partial_sol_fn, partial_sol);
        
        char *s = partial_sol;
        for (int row_nr = 0; row_nr < n; row_nr++)
        {
            for (int col_nr = 0; col_nr < m; col_nr++)
                printf("%c", *s++);
            printf("\n");
        }
    }
    
    if (mode_logic)
    {
        if (mode_01)
            printf("Option -01 ignored\n");
        if (!mode_exact)
            printf("Option -no_exact ignored\n");
        if (partial_sol_fn != 0)
            printf("Partial solution ignored\n");
        
        gen_logic();
    }
    else
        gen_all_perm(mode_exact, mode_01);
    
    
    return 0;
}