#include <stdio.h>


#define MAX_N 20
#define MAX_M 20     

int field[MAX_N][MAX_M];
int n,m;

int count;
int count_0;
int count_1;
int count_more;

void fill(int depth, int min_nr_filled, int min_k)
{
	//printf(" - %d %d\n", depth, min_nr_filled);
	if (depth == n)
	{
		bool zero_row = false;
		
		for (int j = 0; j < m; j++)
		{
			bool all_zero = true;
			for (int i = 0; i < n; i++)
				if (field[i][j] == 1)
				{
					all_zero = false;
					break;
				}
			if (all_zero)
				return;
				
			for (int j2 = j+1; j2 < m; j2++)
			{
				bool all_equal = true;
				for (int i = 0; i < n; i++)
					if (field[i][j] != field[i][j2])
					{
						all_equal = false;
						break;
					}
				if (all_equal)
					return;
			}
		}
		
		count++;

		// count number of solutions:
		int nr_sols = 0;
		int sol = 0;
		for (int k = 1; k < (1 << m); k++)
		{
			bool correct = true;
			for (int i = 0; i < n; i++)
			{
				int nr_ones = 0;
				for (int j = 0; j < m; j++)
					if ((k & (1 << j)) && field[i][j] == 1)
						nr_ones++;
				if (nr_ones != 1)
				{
					correct = false;
					break;
				}
			}
			
			if (correct)
			{
				sol = k;
				nr_sols++;
			}
		}
		if (nr_sols == 0)
			count_0++;
		else if (nr_sols == 1)
		{	
			count_1++;
			printf("--\n");
			for (int j = 0; j < m; j++)
			{
				for (int i = 0; i < n; i++)
					printf("%d", field[i][j]);
				printf("%s\n", sol & (1 << j) ? " *" : "");
			}
		}
		else
			count_more++;
		
		return;
	}
	
	// fill column 'depth'
	for (int k = 3; k < (1 << m); k++)
	{
		int nr_filled = 0;
		for (int j = 0; j < m; j++)
			if (k & (1 << j))
			{
				field[depth][j] = 1;
				nr_filled++;
			}
			else
				field[depth][j] = 0;
				
		if (nr_filled >= min_nr_filled && nr_filled < m
		    && (nr_filled > min_nr_filled || k > min_k))
		{
			bool implied_row = false;
			
			for (int i = 0; i < depth; i++)
			{
				implied_row = true;
				for (int j = 0; j < m; j++)
					if (field[i][j] == 1 && field[depth][j] == 0)
					{
						implied_row = false;
						break;
					}
				if (implied_row)
					break;
			}
			
			if (!implied_row)
			{
				bool prev_is_filled = true;
				bool correct = true;
				for (int j = 0; j < m; j++)
				{
					bool is_filled = false;
					for (int i = 0; i <= depth; i++)
						if (field[i][j] == 1)
						{
							is_filled = true;
							break;
						}
					
					if (is_filled && !prev_is_filled)
					{
						correct = false;
						break;
					}
					prev_is_filled = is_filled;
				}

				if (correct)				
					fill(depth+1, nr_filled, k);
			}
		}
	}
}
	
int main(int argc, char *argv[])
{
	for (int nm = 9; nm <= 36; nm++)
		for (n = 3; n <= 12; n++)
			for (m = 3; m <= 12 && n*m <= 36; m++)
				if (n*m == nm)
					if (m <= (1 << n))
					{
						count = 0;
						count_0 = 0;
						count_1 = 0;
						count_more = 0;
						fill(0, 2, 0);
						printf("n = %d, m = %d: %d  %d, %d, %d\n", n, m, count, count_0, count_1, count_more);
					}

	return 0;
}