''' example input.dat text file ...
- - - - - - - 4 -
- - - 8 1 - 6 - -
3 - 9 - - - - 5 -
1 - 4 7 - - - - -
- - - - - 6 - - -
- 6 - 2 5 - 7 3 -
- 4 5 - 8 - - - 6
- 7 - 6 - - - - 2
- - - - - - - - -
'''
from datetime import datetime
import itertools
import numpy as np

def interlace(given, candidate):
    output = np.zeros((9,), dtype = 'int32')
    candidate_index = 0
    for given_index in range(9):
        if given[given_index] > 0:
            output[given_index] = given[given_index]
        else:
            output[given_index] = candidate[candidate_index]
            candidate_index += 1
    return output

def is_admissible(Z, ordering, index):
    row_index = ordering[index]
    # check for conflicts with provided values
    for j in range(9):
        if (X[row_index,j] < 1) and (Z[row_index,j] in given_cols[j]):
            return False
    # check for column conflicts before this row
    for i in range(index):
        for j in range(9):
            if (Z[ordering[i],j] == Z[row_index,j]):
                return False
    # check for conflicts within block
    observed = { 0: set(), 3: set(), 6: set() }
    for i in range(block[row_index], block[row_index] + 3):
        for j in range(9):
            if (Z[i,j] > 0):
                if (Z[i,j] in observed[block[j]]):
                    return False
                else:
                    observed[block[j]].add(Z[i,j])
    return True

block = { 0: 0, 1: 0, 2: 0, 3: 3, 4: 3, 5: 3, 6: 6, 7: 6, 8: 6 }
given_cols = [ set(), set(), set(), set(), set(), set(), set(), set(), set() ]

X = np.zeros((9,9), dtype = 'int32')
with open('input.dat', 'r') as input_file:
    for row_index in range(9):
        value = input_file.readline().strip('\r\n').split(' ')
        for col_index in range(9):
            if value[col_index] != '-':
                X[row_index, col_index] = int(value[col_index])

indicators = np.where(X > 0, 0, 1)
row_counts = np.sum(indicators, axis = 1)
col_counts = np.sum(indicators, axis = 0)
# todo: consider 3x3 "block" combinations

factorial = { 0: 1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720, 7: 5040, 8: 40320, 9: 362880 }
row_combinations = 1
col_combinations = 1
for i in range(X.shape[0]):
    row_combinations *= factorial[row_counts[i]]
    col_combinations *= factorial[col_counts[i]]

TRANSPOSE = False
if (col_combinations < row_combinations):
    X = np.transpose(X)
    TRANSPOSE = True

given_cols = [ set(), set(), set(), set(), set(), set(), set(), set(), set() ]
for row_index in range(X.shape[0]):
    for col_index in range(X.shape[1]):
        if (X[row_index,col_index] > 0):
            given_cols[col_index].add(X[row_index,col_index])

permutation_lists = []
possible = {}
for i in range(9):
    input_list = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
    for j in range(9):
        if (X[i,j] > 0):
            input_list.remove(X[i,j])
    candidate_list = list(itertools.permutations(input_list))
    np.random.shuffle(candidate_list)
    permutation_lists.append(candidate_list)
    possible[i] = len(permutation_lists[i])

ordering = []
for k,v in sorted(possible.items(), key = lambda x: x[1]):
    ordering.append(k)

print(str(datetime.now()))
Y = np.zeros((9,9), dtype = 'int32')
for candidate0 in permutation_lists[ordering[0]]:
    Y[ordering[0]] = interlace(X[ordering[0]], candidate0)
    admissible0 = is_admissible(Y, ordering, 0)
    if admissible0:
        for candidate1 in permutation_lists[ordering[1]]:
            Y[ordering[1]] = interlace(X[ordering[1]], candidate1)
            admissible1 = is_admissible(Y, ordering, 1)
            if not admissible1:
                Y[ordering[1]] = X[ordering[1]]
            else:
                for candidate2 in permutation_lists[ordering[2]]:
                    Y[ordering[2]] = interlace(X[ordering[2]], candidate2)
                    admissible2 = is_admissible(Y, ordering, 2)
                    if not admissible2:
                        Y[ordering[2]] = X[ordering[2]]
                    else:
                        for candidate3 in permutation_lists[ordering[3]]:
                            Y[ordering[3]] = interlace(X[ordering[3]], candidate3)
                            admissible3 = is_admissible(Y, ordering, 3)
                            if not admissible3:
                                Y[ordering[3]] = X[ordering[3]]
                            else:
                                for candidate4 in permutation_lists[ordering[4]]:
                                    Y[ordering[4]] = interlace(X[ordering[4]], candidate4)
                                    admissible4 = is_admissible(Y, ordering, 4)
                                    if not admissible4:
                                        Y[ordering[4]] = X[ordering[4]]
                                    else:
                                        for candidate5 in permutation_lists[ordering[5]]:
                                            Y[ordering[5]] = interlace(X[ordering[5]], candidate5)
                                            admissible5 = is_admissible(Y, ordering, 5)
                                            if not admissible5:
                                                Y[ordering[5]] = X[ordering[5]]
                                            else:
                                                for candidate6 in permutation_lists[ordering[6]]:
                                                    Y[ordering[6]] = interlace(X[ordering[6]], candidate6)
                                                    admissible6 = is_admissible(Y, ordering, 6)
                                                    if not admissible6:
                                                        Y[ordering[6]] = X[ordering[6]]
                                                    else:
                                                        for candidate7 in permutation_lists[ordering[7]]:
                                                            Y[ordering[7]] = interlace(X[ordering[7]], candidate7)
                                                            admissible7 = is_admissible(Y, ordering, 7)
                                                            if not admissible7:
                                                                Y[ordering[7]] = X[ordering[7]]
                                                            else:
                                                                for candidate8 in permutation_lists[ordering[8]]:
                                                                    Y[ordering[8]] = interlace(X[ordering[8]], candidate8)
                                                                    admissible8 = is_admissible(Y, ordering, 8)
                                                                    if not admissible8:
                                                                        Y[ordering[8]] = X[ordering[8]]
                                                                    else:
                                                                        print(str(datetime.now()))
                                                                        if TRANSPOSE:
                                                                            print(np.transpose(Y))
                                                                        else:
                                                                            print(Y)