# N*N-es mátrix
# N=9

# Sudoku "tábla" kiírása
def kiir(matrix):
    for i in range(N):
        for j in range(N):
            print(matrix[i][j],end=' ')
        print()

# Annak vizsgálata, hogy az adott szám beilleszthető-e az adott
# sor-oszlop helyre
def Rendben(sudoku, sor, oszlop, szam):
    # Ellenőrizzük, hogy az adott sorban szerepel-e már a beírni kívánt szám
    # Ez esetben hamis értéket adunk vissza - return false
    for o in range(N):
        if sudoku[sor][o] == szam:
            return False

    # Ellenőrizzük, hogy az adott oszlopban szerepel-e már a beírni kívánt
    # szám. Ez esetben is hamis értéket adunk vissza - return false
    for s in range(N):
        if sudoku[s][oszlop] == szam:
            return False

    # Megnézzük, hogy az érintett 3x3-as résztáblában szerepel-e már
    # a beírni kívánt szám. Ez esetben is hamis értéket adunk vissza
    # - return false
    rt_sor = sor - sor % 3           # Résztábla kezdősorának meghatározása
    rt_oszlop = oszlop - oszlop % 3  # Résztábla kezdőoszlopának meghatározása

    for i in range(rt_sor,rt_sor+3):
        for j in range(rt_oszlop,rt_oszlop+3):
            if sudoku[i][j] == szam:
                return False

    return True   # Ha minden rendben volt, igaz értéket adunk vissza

# A részlegesen már kitöltött sudoku-tábla teljes kitöltése
def Sudoku_feltoltes(sudoku, sor, oszlop):

    # Ha a sornak és oszlopoknak is a végére értünk leállítjuk a rekurziót - return true
    if sor == N - 1 and oszlop == N:
        return True

    # Ha egy sor elemeivel (oszlopok) végeztünk, menjünk a következő sorra,
    # oszlopot pedig megint az elejére állítjuk */
    if oszlop == N:
        sor+=1
        oszlop = 0

    # Ellenőrizzük, hogy már kitöltött pozíción vagyunk-e,
    # ha igen, menjünk egy oszloppal jobbra és rekurzió...
    if sudoku[sor][oszlop] > 0:
        return Sudoku_feltoltes(sudoku, sor, oszlop + 1)

    for szam in range(1,N+1):
        # Elhelyezhető-e az adott szám az adott sor-oszlop pozíción
        if Rendben(sudoku, sor, oszlop, szam):
            sudoku[sor][oszlop] = szam
            # Térjünk rá a következő oszlop vizsgálatára - rekurzió
            if Sudoku_feltoltes(sudoku, sor, oszlop + 1):
                return True
        # Ha nem találtunk megoldást, állítsuk ismét üresre az adott
        # helyet a táblában
        sudoku[sor][oszlop] = 0
    return False

# ************************** F Ő M O D U L ***********************

# Kezdeti állapot megadása
N=9
sudoku = [
            [ 5, 0, 0, 0, 4, 0, 7, 0, 3 ],
	        [ 0, 4, 0, 6, 2, 8, 0, 0, 0 ],
	        [ 0, 0, 2, 0, 0, 0, 0, 0, 0 ],
	        [ 0, 0, 0, 5, 0, 0, 4, 9, 7 ],
	        [ 0, 0, 0, 0, 7, 0, 0, 0, 0 ],
	        [ 7, 1, 4, 0, 0, 3, 0, 0, 0 ],
	        [ 0, 0, 0, 0, 0, 0, 6, 0, 0 ],
	        [ 0, 0, 0, 9, 6, 2, 0, 5, 0 ],
	        [ 8, 0, 1, 0, 3, 0, 0, 0, 9 ]
        ]

if Sudoku_feltoltes(sudoku, 0, 0):
    kiir(sudoku)
else:
    print('Nem találtam megoldást... ')