# UTS Programming Competition 2016 Problem 7

### From ProgSoc Wiki

# 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!