New Magic Square

Time limit2sMemory limit128 MB

Summary
Fill a 5x5 grid with numbers 1 to 25 so each row strictly increases, respecting up to one prefilled cell per row, and output the lexicographically smallest valid grid or -1.
Level

Medium7 of 10

Topics
Backtracking, Greedy, Combinatorics, Matrix
Solved
No attempts yet

Problem

You must fill a 5 x 5 grid with the integers from 1 through 25, using each integer exactly once. In every row, the numbers must strictly increase from left to right.

Some cells may already contain numbers. In each row, at most one cell is already filled. Fill every remaining empty cell.

If the grid cannot be completed, print -1. If there are multiple valid completions, print the lexicographically smallest grid when read from top to bottom and, within each row, from left to right. In other words, minimize the value in row 1 column 1 first; if tied, minimize row 1 column 2, then row 1 column 3, and so on.

Input

Five lines are given. Each line contains five integers separated by spaces. An empty cell is given as 0. A nonzero value represents a cell that is already filled.

Output

Print the completed 5 x 5 grid in five lines. Each line must contain the five numbers in that row, separated by spaces.

If the grid cannot be completed, print -1.

Examples4

  1. Example 1

    Input
    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
    Expected output
    1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

  2. Example 2

    Input
    0 0 20 0 0
0 0 0 0 0
0 0 0 5 0
0 0 0 0 0
0 0 0 0 0
    Expected output
    1 6 20 21 22
7 8 9 10 11
2 3 4 5 12
13 14 15 16 17
18 19 23 24 25

  3. Example 3

    Input
    0 0 0 0 0
0 0 0 0 24
0 0 0 0 0
0 0 0 0 0
21 0 0 0 0
    Expected output
    -1

  4. Example 4

    Input
    0 0 15 0 0
2 0 0 0 0
0 0 0 7 0
0 0 16 0 0
0 0 0 0 21
    Expected output
    1 3 15 17 18
2 8 9 10 22
4 5 6 7 23
11 12 16 24 25
13 14 19 20 21