// Simple Sudoku solver
// Copyright 2005 Steinar H. Gunderson. GPLv2.

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

#define WIDTH  9
#define HEIGHT 9
#define XGRAN  3
#define YGRAN  3
#define NUM    (XGRAN*YGRAN)

bool board[WIDTH * HEIGHT][NUM];
int passes = 0;

char *current_pass;
int num_current_pass;

void print_board()
{
	printf("+");
	for (unsigned x = 0; x < WIDTH; ++x) {
		for (unsigned xx = 0; xx < XGRAN; ++xx) {
			printf("-");
		}
		printf("+");
	}
	printf("\n");

	for (unsigned y = 0; y < HEIGHT; ++y) {
		for (unsigned yy = 0; yy < YGRAN; ++yy) {
			printf("|");
			for (unsigned x = 0; x < WIDTH; ++x) {
				for (unsigned xx = 0; xx < XGRAN; ++xx) {
					if (board[y * WIDTH + x][yy * YGRAN + xx]) {
						printf("%x", yy * YGRAN + xx + 1);
					} else {
						printf(" ");
					}
				}
				printf("|");
			}
			printf("\n");
		}
		printf("+");
		for (unsigned x = 0; x < WIDTH; ++x) {
			for (unsigned xx = 0; xx < XGRAN; ++xx) {
				printf("-");
			}
			printf("+");
		}
		printf("\n");
	}
	
	printf("\n");
}

bool print_sol()
{
	bool complete = true;
	
	for (unsigned y = 0; y < HEIGHT; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			unsigned n = 0, k = 0;
			for (unsigned i = 0; i < NUM; ++i) {
				if (board[y * WIDTH + x][i]) {
					++n;
					k = i;
				}
			}

			if (n == 1) {
				printf("%x", k + 1);
			} else {
				printf("-");
				complete = false;
			}
		}
		printf("\n");
	}

	return complete;
}

// are the opportunities in cell 2 a subset of cell 1? (doesn't have to
// be a true subset, equality is fine)
bool cell_is_subset(unsigned x1, unsigned y1, unsigned x2, unsigned y2)
{
	for (unsigned i = 0; i < NUM; ++i) {
		if (!board[y1 * WIDTH + x1][i] && board[y2 * WIDTH + x2][i])
			return false;
	}
	return true;
}

void start_pass(char *name)
{
	current_pass = name;
	num_current_pass = 0;
}

void impossible(unsigned x, unsigned y, unsigned i)
{
	if (board[y * WIDTH + x][i]) {
		++num_current_pass;
	}
	board[y * WIDTH + x][i] = false;
}

bool end_pass()
{
	if (num_current_pass > 0) {
		printf("'%s' eliminated %u\n", current_pass, num_current_pass);
		//print_board();
		return true;
	}

	return false;
}

void block_propagation()
{
	// block propagation
	for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
		for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
			for (unsigned y = 0; y < YGRAN; ++y) {
				for (unsigned x = 0; x < XGRAN; ++x) {
					unsigned yy = yb*YGRAN + y;
					unsigned xx = xb*XGRAN + x;
					
					for (unsigned i = 0; i < NUM; ++i) {
						if (!board[yy * WIDTH + xx][i])
							continue;
						
						// if somebody can't be anything but I, we can't
						for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
							for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
								unsigned yy2 = yb*YGRAN + y2;
								unsigned xx2 = xb*XGRAN + x2;

								if (yy2 == yy && xx2 == xx)
									continue;
								
								for (unsigned j = 0; j < NUM; ++j) {
									if (i == j && !board[yy2 * WIDTH + xx2][j])
										goto flexible;
									if (i != j && board[yy2 * WIDTH + xx2][j])
										goto flexible;
								}
								impossible(xx, yy, i);
								goto next;
flexible:						
								1;
							}
						}
next:
						1;
					}
				}	
			}
		} 
	}
}

void block_propagation2()
{
	for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
		for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
			for (unsigned y = 0; y < YGRAN; ++y) {
				for (unsigned x = 0; x < XGRAN; ++x) {
					unsigned yy = yb*YGRAN + y;
					unsigned xx = xb*XGRAN + x;
					
					for (unsigned i = 0; i < NUM; ++i) {
						if (!board[yy * WIDTH + xx][i])
							continue;
						
						// if nobody else can be I, we can't be anything else
						for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
							for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
								unsigned yy2 = yb*YGRAN + y2;
								unsigned xx2 = xb*XGRAN + x2;

								if (yy2 == yy && xx2 == xx)
									continue;
								
								if (board[yy2 * WIDTH + xx2][i])
									goto no_elim;
							}
						}

						for (unsigned j = 0; j < NUM; ++j) {
							if (i == j || !board[yy * WIDTH + xx][j])
								continue;
							impossible(xx, yy, j);
						} 
no_elim:						
						1;
					}
				}	
			}
		} 
	}
}

void block_elimination()
{
	for (unsigned y = 0; y < WIDTH; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			// find cells in the same block matching this one exactly
			unsigned nmatch = 0, ncnt = 0;
			
			for (unsigned i = 0; i < NUM; ++i) {
				if (board[y * WIDTH + x][i])
					++ncnt;
			}

			if (ncnt == 1)
				continue;  // taken by other logic

			unsigned yb = y/YGRAN;
			unsigned xb = x/XGRAN;
			
			for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
				for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
					if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2)) {
						++nmatch;
					}
				}
			}

			if (nmatch != ncnt)
				continue;
			
			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
				
				for (unsigned y2 = 0; y2 < YGRAN; ++y2) {
					for (unsigned x2 = 0; x2 < XGRAN; ++x2) {
						if (!board[(yb*YGRAN + y2) * WIDTH + (xb*XGRAN + x2)][i])
							continue;
						if (cell_is_subset(x, y, xb*XGRAN + x2, yb*YGRAN + y2)) 
							continue;
					
						impossible(xb*XGRAN + x2, yb*YGRAN + y2, i);
					}
				}
			}
		} 
	}
}

void horizontal_propagation()
{
	for (unsigned y = 0; y < HEIGHT; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			unsigned tyb = y/YGRAN;
			unsigned txb = x/XGRAN;

			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
				
				for (unsigned xb = 0; xb < WIDTH/XGRAN; ++xb) {
					if (xb == txb)
						continue;

					// check if anything not on this line can be I
					for (unsigned yy = 0; yy < YGRAN; ++yy) {
						unsigned y2 = tyb * YGRAN + yy;
						if (y2 == y)
							continue;

						for (unsigned xx = 0; xx < XGRAN; ++xx) {
							unsigned x2 = xb * XGRAN + xx;
							if (board[y2 * WIDTH + x2][i])
								goto no_go;
						}
					}

					impossible(x, y, i);
no_go:
					1;
				}
			}
		}
	}
}

void horizontal_propagation2()
{
	for (unsigned y = 0; y < WIDTH; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
						
				// if nobody else can be I, we can't be anything else
				for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
					if (x2 == x)
						continue;
								
					if (board[y * WIDTH + x2][i])
						goto no_elim_h;
				}

				for (unsigned j = 0; j < NUM; ++j) {
					if (i == j || !board[y * WIDTH + x][j])
						continue;
					impossible(x, y, j);
				} 
no_elim_h:						
				1;
			}
		} 
	}
}

void horizontal_elimination()
{
	for (unsigned y = 0; y < WIDTH; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			// find cells on the same row matching this one exactly
			unsigned nmatch = 0, ncnt = 0;
			
			for (unsigned i = 0; i < NUM; ++i) {
				if (board[y * WIDTH + x][i])
					++ncnt;
			}

			if (ncnt == 1)
				continue;  // taken by other logic

			for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
				if (cell_is_subset(x, y, x2, y)) {
					++nmatch;
				}
			}

			if (nmatch != ncnt)
				continue;
			
			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
				
				for (unsigned x2 = 0; x2 < WIDTH; ++x2) {
					if (!board[y * WIDTH + x2][i])
						continue;
					if (cell_is_subset(x, y, x2, y))
						continue;
					
					impossible(x2, y, i);
				}
			}
		} 
	}
}

void vertical_propagation()
{
	for (unsigned y = 0; y < HEIGHT; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			unsigned tyb = y/YGRAN;
			unsigned txb = x/XGRAN;

			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
				
				for (unsigned yb = 0; yb < HEIGHT/YGRAN; ++yb) {
					if (yb == tyb)
						continue;

					// check if anything not on this column can be I
					for (unsigned xx = 0; xx < XGRAN; ++xx) {
						unsigned x2 = txb * XGRAN + xx;
						if (x2 == x)
							continue;

						for (unsigned yy = 0; yy < YGRAN; ++yy) {
							unsigned y2 = yb * YGRAN + yy;
							if (board[y2 * WIDTH + x2][i])
								goto no_go_v;
						}
					}

					impossible(x, y, i);
no_go_v:
					1;
				}
			}
		}
	}
}

void vertical_propagation2()
{
	for (unsigned y = 0; y < WIDTH; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
						
				// if nobody else can be I, we can't be anything else
				for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
					if (y2 == y)
						continue;
								
					if (board[y2 * WIDTH + x][i])
						goto no_elim_v;
				}

				for (unsigned j = 0; j < NUM; ++j) {
					if (i == j || !board[y * WIDTH + x][j])
						continue;
					impossible(x, y, j);
				} 
no_elim_v:
				1;
			}
		} 
	}
}

void vertical_elimination()
{
	for (unsigned y = 0; y < WIDTH; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			// find cells on the same row matching this one exactly
			unsigned nmatch = 0, ncnt = 0;
			
			for (unsigned i = 0; i < NUM; ++i) {
				if (board[y * WIDTH + x][i])
					++ncnt;
			}

			if (ncnt == 1)
				continue;  // taken by other logic

			for (unsigned y2 = 0; y2 < WIDTH; ++y2) {
				if (cell_is_subset(x, y, x, y2)) {
					++nmatch;
				}
			}

			if (nmatch != ncnt)
				continue;
			
			for (unsigned i = 0; i < NUM; ++i) {
				if (!board[y * WIDTH + x][i])
					continue;
				
				for (unsigned y2 = 0; y2 < HEIGHT; ++y2) {
					if (!board[y2 * WIDTH + x][i])
						continue;
					if (cell_is_subset(x, y, x, y2))
						continue;
					
					impossible(x, y2, i);
				}
			}
		} 
	}
}

bool dead_end()
{
	for (unsigned y = 0; y < HEIGHT; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			bool ok = false;
			for (unsigned i = 0; i < NUM; ++i) {
				if (board[y * WIDTH + x][i]) {
					ok = true;
					break;
				}
			}
			if (!ok)
				return true;
		}
	}

	return false;
}

bool solve()
{
	//print_board();
	bool done_anything = false;

	start_pass("Block propagation 1");
	block_propagation();
	done_anything |= end_pass();
	
	start_pass("Block propagation 2");
	block_propagation2();
	done_anything |= end_pass();

	start_pass("Block elimination");
	block_elimination();
	done_anything |= end_pass();

	start_pass("Horizontal propagation 1");
	horizontal_propagation();
	done_anything |= end_pass();
	
	start_pass("Horizontal propagation 2");
	horizontal_propagation2();
	done_anything |= end_pass();

	start_pass("Horizontal elimination");
	horizontal_elimination();
	done_anything |= end_pass();

	start_pass("Vertical propagation 1");
	vertical_propagation();
	done_anything |= end_pass();

	start_pass("Vertical propagation 2");
	vertical_propagation2();
	done_anything |= end_pass();

	start_pass("Vertical elimination");
	vertical_elimination();
	done_anything |= end_pass();

	++passes;

	if (dead_end())
		return false;

	if (done_anything)
		return solve();   // always on we march
	
	// oops, not done anything, and we're not in a self-
	// contradiction either. need to pick a guess?
	unsigned best_x = 0, best_y = 0, best_pos = NUM + 1;

	for (unsigned y = 0; y < HEIGHT; ++y) {
		for (unsigned x = 0; x < WIDTH; ++x) {
			unsigned pos = 0;
			for (unsigned i = 0; i < NUM; ++i) {
				if (board[y * WIDTH + x][i])
					++pos;
			}

			if (pos > 1 && pos < best_pos) {
				best_pos = pos;
				best_x = x;
				best_y = y;
			}
		}
	}

	if (best_pos == NUM + 1)
		return true;

	// uncomment to enable backtracking
#if 0
	bool board_copy[WIDTH * HEIGHT][NUM];
	memcpy(board_copy, board, (WIDTH*HEIGHT)*NUM*sizeof(bool));
	
	for (unsigned i = 0; i < NUM; ++i) {
		if (!board[best_y * WIDTH + best_x][i])
			continue;
		
		for (unsigned j = 0; j < NUM; ++j) {
			if (i == j)
				continue;
			
			board[best_y * WIDTH + best_x][j] = false;
		}
		if (solve())
			return true;
		
		memcpy(board, board_copy, (WIDTH*HEIGHT)*NUM*sizeof(bool));
	}
#endif

	return false;
}

int main()
{
	for (unsigned y = 0; y < HEIGHT; ++y) 
		for (unsigned x = 0; x < WIDTH; ++x) 
			for (unsigned i = 0; i < NUM; ++i) 
				board[y * WIDTH + x][i] = true;
			
	for (unsigned y = 0; y < HEIGHT; ++y) {
		char buf[256];
		if (fgets(buf, 256, stdin) == NULL) {
			fprintf(stderr, "premature eof\n");
			exit(1);
		}
		if (strlen(buf) != WIDTH + 1) {
			fprintf(stderr, "malformed line %u\n", y);
			exit(1);
		}
		for (unsigned x = 0; x < WIDTH; ++x) {
			char ch = buf[x];
			if (ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'G') {
				unsigned n;
				if (ch >= '0' && ch <= '9')
					n = (ch - '0');
				else
					n = 10 + (ch - 'A');
				
				for (unsigned i = 0; i < NUM; ++i) {
					if (i == n-1)
						continue;
					board[y * WIDTH + x][i] = false;
				}
			} else if (ch == '-') {
			} else {
				fprintf(stderr, "illegal char on line %u\n", y);
				exit(1);
			}
		}
	}
	
	bool ok = solve();
	print_sol();

	if (ok) {
		printf("\n%u passes\n", passes);
	} else {
		printf("\n%u passes (incomplete)\n", passes);
		print_board();
	}
}