/***********************************************************************\
*                            sudoku_solver.d                            *
*                                                                       *
*                             Sudoku Solver                             *
>***********************************************************************<
* Copyright (C) 2005 Stewart Gordon.                                    *
*                                                                       *
* This software is provided 'as-is', without any express or implied     *
* warranty.  In no event will the author be held liable for any damages *
* arising from the use of this software.                                *
*                                                                       *
* Permission is granted to anyone to use this software for any purpose, *
* to alter it and redistribute it freely in source or binary form and   *
* to create and distribute derivative works, subject to the following   *
* restrictions:                                                         *
*                                                                       *
* - The origin of this software must not be misrepresented; you must    *
*   not claim that you wrote the original software.                     *
* - Altered versions must be plainly marked as such, and must not be    *
*   misrepresented as being the original software.                      *
* - Derivative works must retain the original author's credit in the    *
*   documentation.                                                      *
* - This notice may not be removed or altered from any source           *
*   distribution.                                                       *
\***********************************************************************/
import std.stdio;
import std.cstream;
import std.string;


void main() {
	char[][9] inputPuzzle;
	foreach (int index, inout char[] line; inputPuzzle) {
		din.flush();
		line = din.readLine();
	}

	SudokuPuzzle puzzle = new SudokuPuzzle(inputPuzzle);
	writefln();
	puzzle.show();

	try {
		while (puzzle.fillOnlyValues()
			  | puzzle.fillOnlyInSubgrids()
			  | puzzle.sliceAndSlot()) {
			puzzle.show();
		}
		debug {
			puzzle.show();
		}
	} catch (Exception ex) {
		puzzle.show();
		throw ex;
	}
}


struct Square {
	int value = -1;
	bit[9] cannotBe;

	uint firstAvailable() {
		foreach (int i, bit b; cannotBe) {
			if (!b) return i;
		}
	}

	uint nextAvailable(uint last) {
		for (int i = last + 1; i < 9; i++) {
			if (!cannotBe[i]) return i;
		}
	}
}


struct Subgrid {
	enum Type { ROW, COL, BLOCK }

	SudokuPuzzle thePuzzle;
	Type type;
	uint id;
	bit isSolved = false;
	Square*[9] squares;

	char[] toString() {
		switch (type) {
			case Type.ROW:
				return format("row %d", id + 1);
			case Type.COL:
				return format("column %d", id + 1);
			case Type.BLOCK:
				return format("block (%d, %d)", id%3 + 1, id/3 + 1);
		}
	}

	void coords(int element, out uint row, out uint col) {
		switch (type) {
			case Type.ROW:
				row = id;
				col = element;
				return;
			case Type.COL:
				row = element;
				col = id;
				return;
			case Type.BLOCK:
				row = (id/3) * 3 + element/3;
				col = (id%3) * 3 + element%3;
		}
	}

	bit fill() {
		if (isSolved) return false;

		isSolved = true;

		bit somethingFilled;
seekValue:
		for (uint value = 0; value < 9; value++) {
			int found = -1;
			foreach (uint iSquare, Square* sq; squares) {
				if (sq.value == value) {
					continue seekValue;
				} else if (!sq.cannotBe[value]) {
					if (found == -1) {
						found = iSquare;
						isSolved = false;
					} else {
						continue seekValue;
					}
				}
			}

			if (found == -1) {
				throw new Exception(format("No room for %d in %s",
				  value+1, toString));
			} else {
				uint row, col;
				coords(found, row, col);
				thePuzzle.place(row, col, value);
				somethingFilled = true;
			}
		}
		return somethingFilled;
	}

	bit refinePerms() {
		if (isSolved) return false;

		Square*[] remSquares;
		bit[9][] stillCannotBe;
		uint[] perm;
		bit[9] inCurrentPerm;
		int permPos = 0;
		bit somethingDone = false;

		foreach (Square* sq; squares) {
			if (sq.value == -1) remSquares ~= sq;
		}

		if (remSquares.length == 0) {
			isSolved = true;
			return false;
		} else if (remSquares.length <= 2) {
			return false;
		}

		perm.length = stillCannotBe.length = remSquares.length;
		foreach (inout bit[9] scb; stillCannotBe) scb[] = true;

/+
remSquares
012345678
x...xxxxx	3
..x.x.xxx	4
x..xxxxxx	2
x..xxxxxx	2
...xx.xxx	4

permPos     v
perm:		9

inCurrentPerm: 3

30125
+/
		perm[0] = 0;
		while (true) {
			for (; perm[permPos] < 9 && (inCurrentPerm[perm[permPos]]
				|| remSquares[permPos].cannotBe[perm[permPos]]);
			  perm[permPos]++) {}

			if (perm[permPos] == 9) {
				if (permPos == 0) {
					break;
				} else {
					inCurrentPerm[perm[--permPos]] = false;
					perm[permPos]++;
				}
			} else {
				inCurrentPerm[perm[permPos]] = true;
				if (++permPos == remSquares.length) {
					// found permutation
					// ***
					debug writef("Permutation:");
					foreach (uint index, uint value; perm) {
						stillCannotBe[index][value] = false;
						debug writef(" %d", value + 1);
					}
					debug {
						writefln();
						getch();
					}

					inCurrentPerm[perm[--permPos]] = false;
					inCurrentPerm[perm[--permPos]] = false;
					perm[permPos]++;
				} else {
					perm[permPos] = 0;
				}
			}
		}

		// done - now update cannotBe
		foreach (uint index, Square* sq; remSquares) {
			if (sq.cannotBe != stillCannotBe[index]) somethingDone = true;
			sq.cannotBe[] = stillCannotBe[index];
		}
		return somethingDone;
	}

	bit sliceAndSlot(Subgrid other) {
		Square*[] inThis = squares.dup;
		Square*[] inBoth;
		Square*[] inOther = other.squares.dup;

		Square*[] filter(Square*[] old, bit[] options) {
			Square*[] result;

			foreach (Square* sq; old) {
				if (sq != null && sq.value == -1) {
					result ~= sq;
					for (uint value = 0; value < 9; value++) {
						if (!sq.cannotBe[value]) options[value] = true;
					}
				}
			}

			return result;
		}

		void eliminate(Square*[] sqs, uint value) {
			foreach (Square* sq; sqs) {
				sq.cannotBe[value] = true;
			}
		}

		bit somethingEliminated = false;

	intersect:
		// separate out intersection of subgrids
		for (int iInThis = 0; iInThis < inThis.length; iInThis++) {
			for (int iInOther = 0; iInOther < inOther.length; iInOther++) {
				if (inThis[iInThis] == inOther[iInOther]) {
					inBoth ~= inThis[iInThis];
					inThis[iInThis] = inOther[iInOther] = null;
					continue intersect;
				}
			}
		}

		// now filter options
		bit[9] canBeInThis, canBeInBoth, canBeInOther;

		inThis = filter(inThis, canBeInThis);
		if (inThis.length == 0) return false;
		inBoth = filter(inBoth, canBeInBoth);
		if (inBoth.length == 0) return false;
		inOther = filter(inOther, canBeInOther);
		if (inOther.length == 0) return false;

		for (int value = 0; value < 9; value++) {
			if (canBeInThis[value] && canBeInBoth[value]
				  && !canBeInOther[value]) {
				eliminate(inThis, value);
				somethingEliminated = true;
			} else if (!canBeInThis[value] && canBeInBoth[value]
				  && canBeInOther[value]) {
				eliminate(inOther, value);
				somethingEliminated = true;
			}
		}

		return somethingEliminated;
	}
}


class SudokuPuzzle {
	Square[9][9] grid;

	Subgrid[27] subgrids;

	this(char[][] g)
	in {
		assert (g.length == 9);
		foreach (char[] row; g) assert (row.length <= 9);
	}
	body {
		// populate grid
		foreach (uint iRow, char[] row; g) {
			foreach (uint iCol, char sq; row) {
				if (sq != ' ') {
					assert (sq >= '1' && sq <= '9');
					place(iRow, iCol, sq - '1');
				}
			}
		}

		// row subgrids
		foreach (uint iRow, inout Subgrid sg; subgrids[0..9]) {
			sg.type = Subgrid.Type.ROW;
			sg.id = iRow;
			sg.thePuzzle = this;
			foreach (uint iCol, inout Square* sq; sg.squares) {
				sq = &grid[iRow][iCol];
			}
		}
		// column subgrids
		foreach (uint iCol, inout Subgrid sg; subgrids[9..18]) {
			sg.type = Subgrid.Type.COL;
			sg.id = iCol;
			sg.thePuzzle = this;
			foreach (uint iRow, inout Square* sq; sg.squares) {
				sq = &grid[iRow][iCol];
			}
		}
		// block subgrids
		foreach (uint iBlock, inout Subgrid sg; subgrids[18..27]) {
			sg.type = Subgrid.Type.BLOCK;
			sg.id = iBlock;
			sg.thePuzzle = this;
			foreach (uint iCell, inout Square* sq; sg.squares) {
				sq = &grid
				  [(iBlock/3) * 3 + iCell/3][(iBlock%3) * 3 + iCell%3];
			}
		}
	}

	void show() {
		writefln();
		foreach (uint iRow, Square[9] row; grid) {
			foreach (uint iCol, Square sq; row) {
				if (sq.value == -1) {
					writef(".");
				} else {
					writef("%d", sq.value + 1);
				}
				if (iCol % 3 == 2) writef(" ");
			}
			writefln();
			if (iRow % 3 == 2) writefln();
		}
	}

	void place(uint inRow, uint inCol, uint value) {
		if (grid[inRow][inCol].value == value) {
			return;
		} else if (grid[inRow][inCol].value != -1) {
			throw new Exception(
			  format("Trying to place %d in (%d, %d), "
			  "which already contains value %d", value+1, inCol+1, inRow+1,
			  grid[inRow][inCol].value+1));
		} else if (grid[inRow][inCol].cannotBe[value]) {
			throw new Exception(
			  format("Trying to place eliminated value %d in (%d, %d)",
			  value+1, inCol+1, inRow+1));
		}

		grid[inRow][inCol].value = value;
		// strike out row
		foreach (inout Square sq; grid[inRow]) {
			sq.cannotBe[value] = true;
		}
		// strike out column
		foreach (inout Square[9] row; grid) {
			row[inCol].cannotBe[value] = true;
		}
		// strike out block
		uint blockTop = (inRow / 3) * 3;
		uint blockLeft = (inCol / 3) * 3;
		grid[blockTop][blockLeft].cannotBe[value] = true;
		grid[blockTop][blockLeft+1].cannotBe[value] = true;
		grid[blockTop][blockLeft+2].cannotBe[value] = true;
		grid[blockTop+1][blockLeft].cannotBe[value] = true;
		grid[blockTop+1][blockLeft+1].cannotBe[value] = true;
		grid[blockTop+1][blockLeft+2].cannotBe[value] = true;
		grid[blockTop+2][blockLeft].cannotBe[value] = true;
		grid[blockTop+2][blockLeft+1].cannotBe[value] = true;
		grid[blockTop+2][blockLeft+2].cannotBe[value] = true;

		// strike out other values of this square
		grid[inRow][inCol].cannotBe[] = true;
		grid[inRow][inCol].cannotBe[value] = false;
	}

	bit fillOnlyValues() {
		bit somethingFilled = false;
		foreach (uint iRow, Square[9] row; grid) {
trySquare:	foreach (uint iCol, Square sq; row) {
				if (sq.value == -1) {
					int found = -1;
					foreach (int i, bit b; sq.cannotBe) {
						if (!b) {
							if (found == -1) {
								found = i;
							} else {
								continue trySquare;
							}
						}
					}
					if (found == -1) {
						throw new Exception(format(
						  "Nothing fits in (%d, %d)", iCol+1, iRow+1));
					} else {
						place(iRow, iCol, found);
						somethingFilled = true;
					}
				}
			}
		}
		return somethingFilled;
	}

	bit fillOnlyInSubgrids() {
		bit somethingFilled = false;

		foreach (Subgrid sg; subgrids) {
			somethingFilled |= sg.fill();
			somethingFilled |= sg.refinePerms();
		}
		return somethingFilled;
	}

	bit sliceAndSlot() {
		Subgrid[] rows = subgrids[0..9];
		Subgrid[] cols = subgrids[9..18];
		Subgrid[] blocks = subgrids[18..27];
		bit somethingFilled = false;

		// slice and slot rows
		for (uint iBand = 0; iBand < 9; iBand += 3) {
			foreach (Subgrid row; rows[iBand..iBand+3]) {
				foreach (Subgrid block; blocks[iBand..iBand+3]) {
					somethingFilled |= row.sliceAndSlot(block);
				}
			}
		}

		// slice and slot columns
		for (uint iStack = 0; iStack < 9; iStack += 3) {
			foreach (Subgrid col; cols[iStack..iStack+3]) {
				for (uint iBlock = iStack/3; iBlock < 9; iBlock++) {
					somethingFilled |= col.sliceAndSlot(blocks[iBlock]);
				}
			}
		}

		return somethingFilled;
	}
}