Cross-Hatching Sudoku Solver

In this problem, you are required to apply the simplest technique in Sudoku: cross-hatching.

For each digit from $1$ to $9$, the cross-hatching method works as follows: if a digit is already placed in a row, column, or $3\times3$ block, then that digit cannot appear in any other cell of that row, column, or block. In every $3\times3$ block that does not yet contain a given digit, if there is exactly one cell where that digit can be legally placed (i.e. the cell’s row and column do not already contain that digit), you must fill that cell with the digit. This process is repeated for each digit until no further deductions can be made.

The input is a partially filled Sudoku grid. You must first check that the initial placements are valid (i.e. no duplicate digits occur in any row, column, or $3\times3$ block). Also, if during cross-hatching you find a $3\times3$ block that does not already contain a digit but has no available cell for that digit, you should output ERROR.

Note that complete solving of the Sudoku is not required – only the iterative application of the cross-hatching technique until no further progress is possible.

inputFormat

The input consists of 9 lines. Each line contains 9 tokens separated by spaces. Each token is either a digit from 1 to 9 (representing a filled cell) or a '.' (representing an empty cell).

outputFormat

If the initial grid is invalid or if during the application of cross-hatching a digit cannot be placed in a $3\times3$ block (i.e. there is no candidate cell), output ERROR. Otherwise, output the resulting grid in the same format: 9 lines with 9 tokens (digits or '.') separated by a single space. Note that the grid may still be partially filled if no further deductions are possible using this method.

sample

. . . . . . . . .
. . . 4 . . . . .
. . . 4 . . . . .
. . . . . . . . .
. 4 . . . . . . .
. . 4 . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

4 . . . . . . . .
. . . 4 . . . . .
. . . 4 . . . . .
. . . . . . . . .
. 4 . . . . . . .
. . 4 . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .