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

#define MAX_SIZE 100

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

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

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;
		}
	}
	void assign(const Pieces& ps)
	{
		nr = ps.nr;
		for (int i = 0; i < nr; i++)
			pieces[i].assign(ps.pieces[i]);
	}
	void update(const Pieces& ps, bool changed)
	{
		for (int i = 0; i < nr; i++)
			pieces[i].update(ps.pieces[i], changed);
	}
};

int n;
int m;
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)
{
	FILE* f = fopen(fn, "r");
	
	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;
		}

		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++)
					;
				
				row[i].add(v);
			}
		}
		
		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;
		}

		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++)
					;
				
				col[i].add(v);
			}
		}
		
		col[i].init(n);
	}
	
	fclose(f);
	
	return true;
}

void write_pieces()
{
	for (int i = 0; i < n; i++)
	{
		printf("row %d:", i+1);
		
		Pieces& ps = row[i];
		
		for (int j = 0; j < ps.nr; j++)
		{
			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);
		
		Pieces& ps = col[i];
		
		for (int j = 0; j < ps.nr; j++)
		{
			Piece& p = ps.pieces[j];
			printf(" %d (%d %d)", p.size, p.min, p.max);
		}
		printf("\n");
	}
}

void printsol(char *board)
{
	rename("frans.sol", "frans.sol2");
	FILE *g = fopen("frans.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);
}

#define HOT 3

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

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))
						{
							return false;
						}
					}
				}
		}
		
		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))
				{
					return false;
				}
				go = true;
			}
		}

		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))
				{
					return false;
				}
				go = true;
			}
		}
		
		for (int i = 0; i < ps.nr; i++)
		{
			Piece& p = ps.pieces[i];

			for (int k = p.max - 1; k < p.min + p.size; k++)
			{
				if (line[k] == EMPTY)
				{
					return false;
				}
				if (line[k] != FULL)
				{
					line[k] = FULL;
					go = true;
				}
			}
		}
		
		for (int i = 0; i < size; i++)
			if (!notempty[i])
			{
				if (line[i] == FULL)
				{
					return false;
				}
				if (line[i] != EMPTY)
				{
					line[i] = EMPTY;
					go = true;
				}
			}

		if (!go)
		{			
			for (int i = 0; i < size; i++)
				if (line[i] == FULL)
				{
					char tline[MAX_SIZE];
					
					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)
							{
								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] = ' ';
							}
					}
					
					for (int j = 0; j < size; j++)
					{
						if (tline[j] == FULL)
						{
							if (line[j] == EMPTY)
							{
								return false;
							}
							if (line[j] == UNKNOWN)
							{
								line[j] = FULL;
								go = true;
							}
						}
						else if (tline[j] == EMPTY)
						{
							if (line[j] == FULL)
							{
								return false;
							}
							if (line[j] == UNKNOWN)
							{
								line[j] = EMPTY;
								go = true;
							}
						}
					}
				}
		}
	}
	
	return true;
}

bool reason(char *rowcol, int nr, char *board, int pos, int off, int size, Pieces& pieces, int *hot, int& modified, bool do_update)
{
	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++)
	{
		if (line[i] != UNKNOWN && board[pos + off*i] == UNKNOWN)
		{
			modified++;
			board[pos + off*i] = line[i];
			hot[i] |= HOT;
		}
	}
	if (do_update)
	{
		bool changed = false;
		pieces.update(ps, changed);
		if (changed)
		{
			modified++;
		}
	}
	
	return true;
}

bool guess_solve(char *board)
{
	int hotrow[MAX_SIZE];
	int hotcol[MAX_SIZE];
	for (int i = 0; i < n; i++)
		hotrow[i] = HOT;
	for (int j = 0; j < m; j++)
		hotcol[j] = HOT;

	int modified;	
    do
    {
        modified = 0;

        for (int i = 0; i < n; i++)
            if ((hotrow[i] & 1) == 1 && !reason("rij", i+1, board, i, n, m, row[i], hotcol, modified, false))
            	return false;
            else
            	hotrow[i] &= ~1;
        for (int j = 0; j < m; j++)
            if ((hotcol[j] & 1) == 1 && !reason("colom", j+1, board, j*n, 1, n, col[j], hotrow, modified, false))
				return false;
			else
				hotcol[j] &= ~1;
    }
    while (modified > 0);
    
    return true;
}

void guess_something(char *rowcol, int nr, char *board, int pos, int off, int size, Pieces& pieces, int *hot, int& modified)
{
	printf("guess %s%d\n", rowcol, nr);
	
	for (int i = 0; i < pieces.nr; i++)
	{
		Piece& p = pieces.pieces[i];
		
		for (int k = p.min; k < p.max; k++)
			if (p.pos[k])
			{
				char guess_board[MAX_SIZE*MAX_SIZE];
				for (int l = 0; l < MAX_SIZE*MAX_SIZE; l++)
					guess_board[l] = board[l];
			
				if (k > 0)
					guess_board[pos+off*(k-1)] = EMPTY;
				if (k + p.size < size)
					guess_board[pos+off*(k + p.size)] = EMPTY;
				for (int l = 0; l < p.size; l++)
					guess_board[pos+off*(k + l)] = FULL;

				if (!guess_solve(guess_board))
				{
					printf("%s%d impossible: %d at %d\n", rowcol, nr, i, k);
					p.reset(k);
					modified++;
				}
			}
	}
}

bool solve()
{
	printf("solve\n");
	
	char board[MAX_SIZE*MAX_SIZE];
	for (int i = 0; i < MAX_SIZE*MAX_SIZE; i++)
		board[i] = UNKNOWN;

	int hotrow[MAX_SIZE];
	int hotcol[MAX_SIZE];
	for (int i = 0; i < n; i++)
		hotrow[i] = HOT;
	for (int j = 0; j < m; j++)
		hotcol[j] = HOT;

	int l = 0;
	int modified;	
    do
    {
        modified = 0;

        for (int i = 0; i < n; i++)
            if ((hotrow[i] & 1) == 1 && !reason("rij", i+1, board, i, n, m, row[i], hotcol, modified, true))
            	return false;
            else
            	hotrow[i] &= ~1;
        for (int j = 0; j < m; j++)
            if ((hotcol[j] & 1) == 1 && !reason("colom", j+1, board, j*n, 1, n, col[j], hotrow, modified, true))
				return false;
			else
				hotcol[j] &= ~1;

		if (modified > 0)
			l = 0;
		
		for (; modified == 0 && l < MAX_SIZE; l++)
		{
			if (2*l <= n)
				guess_something("rij", l+1, board, l, n, m, row[l], hotcol, modified);
			if (2*l < n)
				guess_something("rij", (n-l-1)+1, board, (n-l-1), n, m, row[(n-l-1)], hotcol, modified);
			if (2*l <= m)
				guess_something("colom", l+1, board, l*n, 1, n, col[l], hotrow, modified);
			if (2*l < m)
				guess_something("colom", (m-l-1)+1, board, (m-l-1)*n, 1, n, col[(m-l-1)], hotrow, modified);
			
			if (modified > 0)
			{
				for (int i = 0; i < n; i++)
					hotrow[i] = HOT;
				for (int j = 0; j < m; j++)
					hotcol[j] = HOT;
			}			
		}
		printf("\nmodified = %d\n", modified);
		printsol(board);
    }
    while (modified > 0);
    
    return true;
}


int main(int argc, char *argv[])
{
	if (!read_clues("frans.nono"))
	{
		printf("\n\nread error\n");
		return 0;
	}
	if (!solve())
		printf("\nNo solution\n");
	printf("\n\ndone\n");
	return 0;
}