Més Sudokus P79494


Statement
 

pdf   zip

thehtml

Feu un programa que trobi totes les solucions possibles d’un Sudoku.

Entrada

L’entrada comença amb un nombre n, seguit de n Sudokus. Cada Sudoku consisteix en 81 nombres entre zero i nou, més els caràcters que es poden veure als exemples. Un zero marca un valor desconegut. Excepte per als zeros, no hi ha cap número repetit a cap fila, ni a cap columna, ni a cap dels nou quadres 3 × 3.

Sortida

Per a cada Sudoku, escriviu-ne totes les solucions possibles en ordre lexicogràfic, cadascuna seguida d’una línia buida. Escriviu “no solution” si no hi ha cap solució possible. Escriviu una línia amb 30 asteriscos després de la sortida per a cada Sudoku.

Observació

Els jocs de proves estan triats de manera que un programa de força bruta que simplement ompli les files de dalt a baix i d’esquerra a dreta sigui suficientment ràpid.

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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++