Even more Sudokus P78955


Statement
 

pdf   zip

thehtml

Write a program to find the unique solution of a Sudoku.

Input

Input begins with a number n, followed by n Sudokus. Every Sudoku consists of 81 numbers between zero and nine, plus the characters shown in the examples. A zero indicates an unknown value. Except for zeros, there are no repeated numbers in any row, nor in any column, nor in any of the nine squares 3 × 3. Every Sudoku has exactly one solution.

Output

For every Sudoku, print its unique solution, followed by an empty line.

Observation

A backtracking program that simply fills the rows from top to bottom and from left to right should not be fast enough to solve this exercise. Instead, at every step of the backtracking, fill the empty cell (or one of the empty cells) with less options left.

Public test cases
  • Input

    2
    
    0 8 0 | 0 5 9 | 0 0 0
    7 0 3 | 0 0 0 | 0 0 0
    6 4 9 | 7 0 0 | 0 0 0
    ------+-------+------
    0 6 4 | 0 0 3 | 0 0 5
    0 0 7 | 0 0 0 | 6 0 0
    8 0 0 | 6 0 0 | 0 4 0
    ------+-------+------
    0 0 0 | 0 0 7 | 3 2 8
    0 0 0 | 0 0 0 | 1 0 7
    0 0 0 | 8 9 0 | 0 0 0
    
    1 2 3 | 4 5 6 | 7 8 9
    4 5 6 | 0 7 0 | 0 0 0
    7 8 9 | 0 0 0 | 0 6 0
    ------+-------+------
    2 0 0 | 1 0 0 | 0 0 0
    5 0 0 | 0 2 0 | 8 0 0
    8 0 1 | 5 0 3 | 9 0 0
    ------+-------+------
    3 0 0 | 0 6 0 | 1 9 8
    6 0 0 | 0 0 0 | 0 2 7
    9 7 5 | 8 0 0 | 0 0 3
    

    Output

    1 8 2 | 3 5 9 | 4 7 6
    7 5 3 | 2 6 4 | 9 8 1
    6 4 9 | 7 1 8 | 2 5 3
    ------+-------+------
    2 6 4 | 9 7 3 | 8 1 5
    9 1 7 | 4 8 5 | 6 3 2
    8 3 5 | 6 2 1 | 7 4 9
    ------+-------+------
    5 9 6 | 1 4 7 | 3 2 8
    4 2 8 | 5 3 6 | 1 9 7
    3 7 1 | 8 9 2 | 5 6 4
    
    1 2 3 | 4 5 6 | 7 8 9
    4 5 6 | 9 7 8 | 2 3 1
    7 8 9 | 2 3 1 | 4 6 5
    ------+-------+------
    2 9 4 | 1 8 7 | 3 5 6
    5 3 7 | 6 2 9 | 8 1 4
    8 6 1 | 5 4 3 | 9 7 2
    ------+-------+------
    3 4 2 | 7 6 5 | 1 9 8
    6 1 8 | 3 9 4 | 5 2 7
    9 7 5 | 8 1 2 | 6 4 3
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++