Hide

Problem D
Simply Sudoku

Sudoku puzzles come in all different shapes and difficulty levels. Traditionally a Sudoku puzzle is a $9\times 9$ grid. Initially, some of the cells are filled in with numbers and some are empty. The goal is to fill in each cell with a number in the range $1$$9$ subject to the following restrictions:

  • Each digit $1$$9$ must appear once in each row

  • Each digit $1$$9$ must appear once in each column

  • Each digit $1$$9$ must appear once in each $3\times 3$ sub-grid

The difficulty of a Sudoku puzzle can vary widely. The easiest puzzles can be solved with the following two simple techniques:

Single Value Rule:

search for squares which only have one possible value that can be put there.

Unique Location Rule:

within any row, column or sub-grid search for a value that can only be placed in one of the nine locations.

Consider the partially solved Sudoku puzzle shown in Figure 1. The Single Value Rule applies to grid square A$7$ where $8$ is the only value that can be placed there. The Unique Location Rule can be used to put a $5$ in square B$3$ as it is the only location in row $3$ where a $5$ can be placed.

\includegraphics[width=0.5\textwidth ]{sudoku-fig.pdf}
Figure 1: Sample Input $1$

The easiest Sudoku puzzles can be solved with only these two rules; harder puzzles use techniques like swordfish, x-wings and BUGs.

For this problem you will be given a Sudoku puzzle and must determine if it is an easy puzzle, i.e., whether it can be solved by just using the Single Value and Unique Location rules.

Input

Input consists of a single Sudoku puzzle given over nine lines. Each line contains $9$ values in the range $0$ to $9$, where a $0$ indicates a blank in the puzzle.

Output

Output the word Easy followed by the solved Sudoku puzzle if it is an easy puzzle. The puzzle should be printed on nine lines with a single space separating values on a line. If the puzzle is not easy output Not easy followed by as much of the Sudoku puzzle as can be solved using the two rules described above. Use the same format for the partial solution as for the complete solution using a ‘.’ instead of a digit for a unfilled square.

Sample Input 1 Sample Output 1
2 6 0 5 1 0 3 0 0
3 0 0 0 6 0 0 0 2
0 1 5 0 7 3 9 0 4
0 0 9 0 0 0 5 0 0
0 0 2 6 0 1 4 0 0
0 0 6 0 0 0 7 0 0
6 0 1 9 4 0 2 3 0
9 0 0 0 2 0 0 0 5
0 0 8 0 3 5 0 4 9
Easy
2 6 4 5 1 9 3 7 8
3 9 7 8 6 4 1 5 2
8 1 5 2 7 3 9 6 4
1 3 9 4 8 7 5 2 6
5 7 2 6 9 1 4 8 3
4 8 6 3 5 2 7 9 1
6 5 1 9 4 8 2 3 7
9 4 3 7 2 6 8 1 5
7 2 8 1 3 5 6 4 9
Sample Input 2 Sample Output 2
0 0 0 0 0 0 7 0 1
0 0 0 0 0 1 2 3 5
0 0 1 8 0 0 0 0 6
0 0 0 0 2 5 0 9 3
9 0 0 0 0 0 0 0 2
3 1 0 6 7 0 0 0 0
2 0 0 0 0 3 8 0 0
1 3 8 9 0 0 0 0 0
4 0 6 0 0 0 0 0 0
Not easy
. . 3 . . . 7 8 1
. . . . . 1 2 3 5
. . 1 8 3 . 9 4 6
. . . . 2 5 . 9 3
9 . . 3 . . . 7 2
3 1 2 6 7 9 4 5 8
2 . . . . 3 8 . .
1 3 8 9 . . 5 . .
4 . 6 . . . 3 . .

Please log in to submit a solution to this problem

Log in