Més Sudokus P79494


Statement
 

pdf   zip

html

Write a program to find all the possible solutions 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 3 × 3 squares.

Output

For every Sudoku, print all the possible solutions in lexicographical order, each one followed by an empty line. Print “no solution” if there is no solution. Print a line with 30 asterisks after the output for every Sudoku.

Observation

The data tests are chosen so that a backtracking program that simply fills the rows from top to bottom and from left to right will be fast enough.

Public test cases
  • Input

    3
    
    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 0 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
    
    1 2 3 | 4 5 6 | 7 8 9
    9 8 7 | 3 2 1 | 6 5 4
    4 5 6 | 7 8 9 | 1 2 3
    ------+-------+------
    3 9 2 | 8 4 5 | 0 0 0
    0 0 0 | 0 0 0 | 0 0 0
    0 0 0 | 0 0 0 | 0 0 0
    ------+-------+------
    0 0 0 | 0 0 0 | 0 0 0
    0 0 0 | 0 0 0 | 0 0 0
    0 0 0 | 0 0 0 | 0 0 0
    

    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
    
    1 2 3 | 4 5 6 | 7 8 9
    4 5 6 | 9 8 7 | 2 3 1
    7 8 9 | 2 3 1 | 4 6 5
    ------+-------+------
    2 9 4 | 1 7 8 | 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
    
    ******************************
    no solution
    ******************************
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++