És la solució d'un Sudoku? P16893


Statement
 

pdf   zip

Recordeu que un Sudoku és un joc que consisteix a completar una graella 9×99 \times 9 amb números entre 1 i 9 de manera que el resultat final no tingui números repetits a la mateixa fila, columna o submatriu 3×33 \times 3. Per exemple, aquest és un Sudoku i la seva solució:

(9,9) (0,0)(0,9) (1,0)(1,9) (2,0)(2,9) (3,0)(3,9) (4,0)(4,9) (5,0)(5,9) (6,0)(6,9) (7,0)(7,9) (8,0)(8,9) (9,0)(9,9)

(0,0)(9,0) (0,1)(9,1) (0,2)(9,2) (0,3)(9,3) (0,4)(9,4) (0,5)(9,5) (0,6)(9,6) (0,7)(9,7) (0,8)(9,8) (0,9)(9,9)

(0.5,0.5)4 (2.5,0.5)5 (3.5,0.5)6

(1.5,1.5)2 (2.5,1.5)9 (3.5,1.5)1

(4.5,2.5)7 (5.5,2.5)5 (8.5,2.5)8

(2.5,3.5)6 (3.5,3.5)4 (4.5,3.5)2

(1.5,4.5)4 (2.5,4.5)8 (6.5,4.5)5 (7.5,4.5)6

(4.5,5.5)6 (5.5,5.5)1 (6.5,5.5)8

(0.5,6.5)1 (3.5,6.5)9 (4.5,6.5)3

(5.5,7.5)6 (6.5,7.5)4 (7.5,7.5)5

(5.5,8.5)2 (6.5,8.5)3 (8.5,8.5)7

(9,9) (0,0)(0,9) (1,0)(1,9) (2,0)(2,9) (3,0)(3,9) (4,0)(4,9) (5,0)(5,9) (6,0)(6,9) (7,0)(7,9) (8,0)(8,9) (9,0)(9,9)

(0,0)(9,0) (0,1)(9,1) (0,2)(9,2) (0,3)(9,3) (0,4)(9,4) (0,5)(9,5) (0,6)(9,6) (0,7)(9,7) (0,8)(9,8) (0,9)(9,9)

(0.5,0.5)4 (1.5,0.5)7 (2.5,0.5)5 (3.5,0.5)6 (4.5,0.5)8 (5.5,0.5)9 (6.5,0.5)1 (7.5,0.5)3 (8.5,0.5)2

(0,1) (0.5,0.5)9 (1.5,0.5)2 (2.5,0.5)9 (3.5,0.5)1 (4.5,0.5)4 (5.5,0.5)3 (6.5,0.5)6 (7.5,0.5)7 (8.5,0.5)5

(0,2) (0.5,0.5)6 (1.5,0.5)3 (2.5,0.5)1 (3.5,0.5)2 (4.5,0.5)7 (5.5,0.5)5 (6.5,0.5)9 (7.5,0.5)4 (8.5,0.5)8

(0,3) (0.5,0.5)5 (1.5,0.5)1 (2.5,0.5)6 (3.5,0.5)4 (4.5,0.5)2 (5.5,0.5)8 (6.5,0.5)7 (7.5,0.5)9 (8.5,0.5)3

(0,4) (0.5,0.5)2 (1.5,0.5)4 (2.5,0.5)8 (3.5,0.5)3 (4.5,0.5)9 (5.5,0.5)7 (6.5,0.5)5 (7.5,0.5)6 (8.5,0.5)1

(0,5) (0.5,0.5)7 (1.5,0.5)9 (2.5,0.5)3 (3.5,0.5)5 (4.5,0.5)6 (5.5,0.5)1 (6.5,0.5)8 (7.5,0.5)2 (8.5,0.5)4

(0,6) (0.5,0.5)1 (1.5,0.5)5 (2.5,0.5)7 (3.5,0.5)9 (4.5,0.5)3 (5.5,0.5)4 (6.5,0.5)2 (7.5,0.5)8 (8.5,0.5)6

(0,7) (0.5,0.5)3 (1.5,0.5)8 (2.5,0.5)2 (3.5,0.5)7 (4.5,0.5)1 (5.5,0.5)6 (6.5,0.5)4 (7.5,0.5)5 (8.5,0.5)9

(0,8) (0.5,0.5)9 (1.5,0.5)6 (2.5,0.5)4 (3.5,0.5)8 (4.5,0.5)5 (5.5,0.5)2 (6.5,0.5)3 (7.5,0.5)1 (8.5,0.5)7

En aquest problema no us demanem que resolgueu cap Sudoku, només que comproveu que cada matriu donada pot ser la solució d’un Sudoku.

Entrada

L’entrada consisteix en un nombre nn, seguit de nn casos. Cada cas té 9 files, cadascuna amb 9 números entre 1 i 9.

Sortida

Per a cada cas, escriviu “si” o “no” depenent de si la matriu donada compleix les regles de les solucions dels Sudokus.

Public test cases

  • Input

    2

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

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

    Output

    si
no
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Java Python