Sudoku (1) P89454


Statement
 

pdf   zip

html

Write a program that finds all the possible solutions of a sudoku.

Input

Input consists of 81 numbers between zero and nine, plus the bars and dashes that can be seen at the instances. The zeros indicate positions of unknown value. Except zeros, there will not be any repeated number in any row, nor any column, nor any of the nine squares 3 × 3.

Output

Your program must print all the possible solutions of the given sudoku, in lexicographical order, and each one with a line in white in the end. It must print "-1" if there is not any possible solution.

Observation

The test data of this exercise are done in a way that a backtracking that simply fulls the rows from top to bottom and from left to right is fast enough.

Public test cases

  • Input

    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

    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

  • Input

    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

    Output

    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

  • Input

    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
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++