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

#define MAX_SIZE 100

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

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

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

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

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

		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 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(Board &board)
{
	FILE *f = fopen("frans.prev_sol", "r");
	if (f == 0)
	{
		printf("cannot open file 'frans.prev_sol'\n");
		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("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);
}

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

		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]);
				
			found++;
		}
	}

	printf(" found %d", 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[100];

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

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("%c", search_mode);
		if (n_unknown > nr_unknown)
			printf(" ***** %d", combined_try_board.count_unknown());
		return n_unknown < nr_unknown;
	}
	
	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 = search_mode == SEARCH_MODE_COUNTER ? FULL : EMPTY;
	char second = search_mode == SEARCH_MODE_COUNTER ? EMPTY : FULL;
	
	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;		
}

bool try_all_in_square_counter(int i, int j, 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)
{
	if (j == j_max)
	{
		return true;
	}
	
	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 (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);

		bool try_found = false;
		bool result = try_all_in_square(i_min, j_min, i_min, i_max, j_max, clues, combined_try_board, try_board, nr_unknown, try_found, SEARCH_MODE_COUNTER, 0);
		if (try_found)
			found = true;
		if (!result)
			return false;
	}

	return try_all_in_square_counter(next_i, next_j, i_min, i_max, j_min, j_max, clues, combined_try_board, board, nr_unknown, found);
}

void try_all_in_square(int unknowns, int nsize, int msize, const Clues& clues, Board &board, int &modified)
{
	if (unknowns > nsize * msize)
		return;
		
	for (int j = 0; j < m - msize + 1; j++)
		for (int i = 0; i < n - nsize + 1; i++)
		{
			int cu = 0;
			for (int i1 = 0; i1 < nsize; i1++)
				for (int j1 = 0; j1 < msize; j1++)
					if (board[(i+i1)+n*(j+j1)] == UNKNOWN)
						cu++;
			if (unknowns == cu)
			{
				printf("%d: try_all_in_square(%2d-%2d, %2d-%2d) %d ", unknowns, i, i+nsize-1, j, j+nsize-1, 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(i, j, i, i+nsize, j+msize, clues, combined_try_board, try_board, board.nr_unknown, found, SEARCH_MODE_FIRST, 0)
					&& found 
					&& try_all_in_square_counter(i, j, i, i+nsize, j, j+msize, clues, combined_try_board, board, board.nr_unknown, found)
					&& try_all_in_square(i, j, i, i+nsize, j+msize, clues, combined_try_board, try_board, board.nr_unknown, found, SEARCH_MODE_NORMAL, 0))
				{
					if (found)
					{
						board.intergrate(combined_try_board, modified);
						if (modified > 0)
						{
							printf(" modified = %d\n", modified);
							return;
						}
					}
				}
				printf("\n");
			}
		}
}


bool solve(Clues &clues, Board &board)
{
	fprintf(stderr, "solve\n");
	
	int l = 0;
	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, 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);
			
			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);
				}
					
			}
			for (int j = 0; j < n+m && modified == 0; j++)
			{
				if (combinations[j].max > 1 && combinations[j].max < 10000)
				{
					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);
				}
			}
			
			for (int unknowns = 2; modified == 0 && unknowns <= 25; unknowns++)
			{
				if (modified == 0)
					try_all_in_square(unknowns, 2, 2, clues, board, modified);
				if (modified == 0)
					try_all_in_square(unknowns, 3, 3, clues, board, modified);
				if (modified == 0)
					try_all_in_square(unknowns, 4, 4, clues, board, modified);
				if (modified == 0)
					try_all_in_square(unknowns, 5, 5, clues, board, modified);
				if (modified == 0)
					try_all_in_square(unknowns, 6, 6, clues, board, modified);
				if (modified == 0)
					try_all_in_square(unknowns, 7, 7, clues, board, modified);
			}
				
			if (modified > 0)
			{
				board.resetneeds();
			}
			
		}
		
/*		for (; modified == 0 && l < MAX_SIZE; l++)
		{
			if (2*l <= n)
				guess_something("rij", l+1, clues, board, l, n, m, clues.row[l], hotcol, modified);
			if (2*l < n)
				guess_something("rij", (n-l-1)+1, clues, board, (n-l-1), n, m, clues.row[(n-l-1)], hotcol, modified);
			if (2*l <= m)
				guess_something("colom", l+1, clues, board, l*n, 1, n, clues.col[l], hotrow, modified);
			if (2*l < m)
				guess_something("colom", (m-l-1)+1, clues, board, (m-l-1)*n, 1, n, clues.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);
		//dumpboard(board);
    }
    while (modified > 0);
    
    return true;
}

Clues clues;
Board board;

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

	board.clear();

	read_prev_board(board);
	if (!solve(clues, board))
		printf("\nNo solution\n");
	printf("\n\ndone\n");
	return 0;
}