#include <iostream>
#include <iomanip>
#include <string>
#include <cassert>

using namespace std;


struct Sudoku {
	int bd[81];
	bool poss[81][9];

	int& operator[](int i) {return bd[i];}
	const int& operator[](int i) const {return bd[i];}

	int nposs(int i) const {
		int t = 0;
		for (int j = 0; j < 9; j++) {
			t += poss[i][j];
		}
		return t;
	}
};

istream& operator>>(istream &in, Sudoku &su) {
	for (int i = 0; i < 81; i++) {
		char c;
		in >> c;
		if (c == '.') {
			su[i] = -1;
		} else {
			assert('1' <= c && c <= '9');
			su[i] = c - '1';
		}

		for (int j = 0; j < 9; j++) {
			su.poss[i][j] = true;
		}
	}
	return in;
}

ostream& operator<<(ostream &os, const Sudoku &su) {
	for (int y = 0; y < 9; y++) {
		if (y != 0) {
			os << endl;
			if (y % 3 == 0) os << endl;
		}

		for (int x = 0; x < 9; x++) {
			if (x != 0) {
				os << ' ';
				if (x % 3 == 0) os << ' ';
			}
			int v = su[9 * y + x];
			if (v == -1) os << '.';
			else os << v + 1;
			string s;
			for (int i = 0; i < 9; i++) {
				if (su.poss[9 * y + x][i]) s += '1' + i;
			}
			// os << '(' << setw(9) << s << ')';
		}
	}

	return os;
}

void cleanPossBase(Sudoku &su, bool print=true) {
	for (int y = 0; y < 9; y++)
	for (int x = 0; x < 9; x++) {
		if (su[9 * y + x] != -1) {
			for (int i = 0; i < 9; i++) {
				su.poss[9 * y + x][i] = false;
			}
			continue;
		}

		for (int i = 0; i < 9; i++) {
			if (i != x && su[9 * y + i] != -1 && su.poss[9 * y + x][su[9 * y + i]]) {
				if (print) cerr << "Removed poss " << su[9 * y + i]+1 << " at " << i << " because same number in row" << endl;
				su.poss[9 * y + x][su[9 * y + i]] = false;
			}
			if (i != y && su[9 * i + x] != -1 && su.poss[9 * y + x][su[9 * i + x]]) {
				if (print) cerr << "Removed poss " << su[9 * i + x]+1 << " at " << i << " because same number in column" << endl;
				su.poss[9 * y + x][su[9 * i + x]] = false;
			}
			int bx = x / 3 * 3 + i % 3;
			int by = y / 3 * 3 + i / 3;
			if ((bx != x || by != y) && su[9 * by + bx] != -1 && su.poss[9 * y + x][su[9 * by + bx]]) {
				if (print) cerr << "Removed poss " << su[9 * by + bx]+1 << " at " << i << " because same number in block" << endl;
				su.poss[9 * y + x][su[9 * by + bx]] = false;
			}
		}
	}
}

void cleanPossIndirectRC(Sudoku &su) {
	for (int n = 0; n < 9; n++) {
		for (int bi = 0; bi < 9; bi++) {
			bool haveR[3] = {false, false, false};
			bool haveC[3] = {false, false, false};
			int bx = bi % 3 * 3, by = bi / 3 * 3;

			for (int y = by; y < by + 3; y++) {
				for (int x = bx; x < bx + 3; x++) {
					if (su.poss[9 * y + x][n]) {
						haveR[y - by] = true;
						haveC[x - bx] = true;
					}
				}
			}

			if (haveR[0] + haveR[1] + haveR[2] == 1) {
				int y = by + 0 * haveR[0] + 1 * haveR[1] + 2 * haveR[2];
				for (int x = 0; x < 9; x++) {
					if (su.poss[9 * y + x][n]) {
						cerr << "Removed poss " << n+1 << " at " << 9*y+x << " because row-local numbers in block " << bi << endl;
						su.poss[9 * y + x][n] = false;
					}
				}
			}

			if (haveC[0] + haveC[1] + haveC[2] == 1) {
				int x = bx + 0 * haveC[0] + 1 * haveC[1] + 2 * haveC[2];
				for (int y = 0; y < 9; y++) {
					if (by <= y && y < by + 3) continue;
					if (su.poss[9 * y + x][n]) {
						cerr << "Removed poss " << n+1 << " at " << 9*y+x << " because row-local numbers in block " << bi << endl;
						su.poss[9 * y + x][n] = false;
					}
				}
			}
		}
	}
}

bool applySingles(Sudoku &su) {
	for (int i = 0; i < 81; i++) {
		if (su.nposs(i) == 1) {
			for (int j = 0; j < 9; j++) {
				if (su.poss[i][j]) {
					cerr << "Set " << i << " to " << j+1 << " since nposs=1" << endl;
					su[i] = j;
					return true;
				}
			}
		}
	}

	return false;
}

bool applyOnlysB(Sudoku &su) {
	for (int n = 0; n < 9; n++) {
		for (int bi = 0; bi < 9; bi++) {
			int bx = bi % 3 * 3, by = bi / 3 * 3;

			int idx = -1;
			for (int y = by; y < by + 3; y++) {
				for (int x = bx; x < bx + 3; x++) {
					if (su.poss[9 * y + x][n]) {
						if (idx == -1) idx = 9 * y + x;
						else goto nope_next;
					}
				}
			}

			if (idx != -1) {
				cerr << "Set " << idx << " to " << n+1 << " since only there in block" << endl;
				su[idx] = n;
				return true;
			}

		nope_next: ;
		}
	}

	return false;
}

bool performStep(Sudoku &su) {
	cleanPossBase(su);
	cleanPossIndirectRC(su);

	if (applySingles(su)) return true;
	if (applyOnlysB(su)) return true;

	return false;
}

void solve(Sudoku &su) {
	cleanPossBase(su, false);
	while (performStep(su)) {
		cout << su << endl << endl;
	}
}

int main() {
	cout << "This solver is incorrect. On suvh.txt, it gives a 5 on x=0 y=3, while that should be an 8." << endl;
	return 1;

	Sudoku su;
	cin >> su;

	solve(su);

	cout << su << endl;
}