# UTS Programming Competition 2016 Problem 7

This is a part of the UTS Programming Competition 2016 Problem Set.

# Problem 7: Sudoku

Run time limit: 2 seconds

## Problem Description

A 9x9 sudoku puzzle has 9 rows, 9 columns, and 9 blocks (3x3 subgrids), each of 9 cells, where each cell can contain a digit in the range [1, 9]. Each row, column and block should have a cell with each digit once only. Write a program to solve any Sudoku puzzle.

Note that Sudoku puzzles can often have multiple solutions for a given input. These test cases will all have enough cells completed such that there will be only one possible solution to the puzzle.

## Data Specification

### Input

Input consists of a single test case containing the initial puzzle state.

Known cells are given as digits 1-9, and unknown cells are given as 0. Each digit on a line is separated by a single SPACE.

There are nine lines in total.

### Output

Output consists of the solution to the given puzzle, ie. with all the zeroes filled in with digits 1-9, digits separated by a single SPACE, nine lines in total.

### Sample Input

```4 0 0 3 5 7 9 6 0
0 0 5 2 0 6 3 0 4
0 0 9 0 0 0 0 2 5
5 2 0 9 0 8 1 4 7
0 0 6 0 7 0 2 0 0
1 9 7 5 0 2 0 3 8
6 5 0 0 0 0 8 0 0
9 0 8 6 0 5 4 0 0
0 7 1 8 3 4 0 0 6
```

### Sample Output

```4 8 2 3 5 7 9 6 1
7 1 5 2 9 6 3 8 4
3 6 9 4 8 1 7 2 5
5 2 3 9 6 8 1 4 7
8 4 6 1 7 3 2 5 9
1 9 7 5 4 2 6 3 8
6 5 4 7 2 9 8 1 3
9 3 8 6 1 5 4 7 2
2 7 1 8 3 4 5 9 6
```

## Solutions

Put your solutions here!