#koordinater er skrevet på formen (linje, kolonne)
def smudprint(board):
    j = 1
    for line in board:
        i = 0
        for x in line:
            print(x, end=' ')
            i+= 1
            if i in (3,6):
                print(' | ', end='')
        print()
        if j in (3,6):
            print('-'*24)
        j += 1


def read_board(boardname): #leser inn brettet fra fil
    board = [] #lager et tomt brett
    with open(boardname, 'r') as file:
        for i in range(9):  #skal lese inn 9 linjer
            line = file.readline().strip() #leser inn en linje
            line = [int(x) for x in line] #gjør alle elementene i linjen til ints
            board.append(line)
    return board

def sjekk_linje(board, kor): #tar inn et brett og et koordinat, sjekker lovlige tall i det koordinatet
    # et set er en serie med tall hvor hvert tall bare kan forekomme én gang
    # f.eks. : set(1,2,3) - set(1,3) = {2}

    lovlige_tall = set([1,2,3,4,5,6,7,8,9]) - set(board[kor[0]])
    return list(lovlige_tall)

def sjekk_kolonne(board, kor):
    column = [] #lager tom kolonne
    for line in board:
        column.append(line[kor[1]])

    lovlige_tall = set([1,2,3,4,5,6,7,8,9]) - set(column)
    return list(lovlige_tall)

def sjekk_rute(board, kor):
    rute = []
    rutenr_linje = kor[0]//3 #hvis du er i linje nr. 2 er du i rute nr.0, linje nr. 3 => rute nr. 1 osv (husk nullindeksering)
    rutnr_kolonne = kor[1]//3
    for i in range(3): #hvis du er i rute 2 (linjeretning) vil du hente tall fom linje 6 til linje 8
        for k in range(3): #hvis du er i rute 1 (kolonneretning) vil du hente tall fom. kolonne 3 til kolonne 5
            rute.append(board[rutenr_linje*3 + i][rutnr_kolonne*3 + k])

    lovlige_tall = set([1,2,3,4,5,6,7,8,9]) - set(rute)
    return list(lovlige_tall)

def finn_neste_koordintat(kor):
    if kor[1] == 8:
        neste_rad = kor[0] + 1
        neste_kolonne = 0
    else:
        neste_rad = kor[0]
        neste_kolonne = kor[1] + 1

    return (neste_rad,neste_kolonne)

def ferdig(board,kor):
    if kor == (8,8): #hvis du nettopp har puttet et tall inn i siste rute er du ferdig!
        return True
    return False

def brute_force(board, kor, scope=0):
    scope_board = [[] for line in board] # bygger et brett inni funksjonen pga. hvordan python håndterer lister
    for k in range(len(board)):
        for i in range(len(board[k])):
            scope_board[k].append(board[k][i])

    printboard = [[] for line in board] #lager bare et brett for å printe ting så det blir kult :)
    for k in range(len(board)):
        for i in range(len(board[k])):
            if scope_board[k][i] == 0:
                printboard[k].append('')
            else:
                printboard[k].append(board[k][i])
    print(printboard)

    #Finner hvilke tall som er lovlige
    lovlig1 = sjekk_linje(scope_board, kor)
    lovlig2 = sjekk_kolonne(scope_board, kor)
    lovlig3 = sjekk_rute(scope_board, kor)

    if scope_board[kor[0]][kor[1]] == 0: #sjekker om ruten er tom
        lovlig_tall = [] #lager en liste med lovlige tall i ruten med koordinat kor
        for x in [1,2,3,4,5,6,7,8,9]:
            if x in lovlig1 and (x in lovlig2) and (x in lovlig3): #et tall må være i alle lovlig-listene
                lovlig_tall.append(x)

        for tall in lovlig_tall: #skal iterere gjennom de lovlige tallene
            scope_board[kor[0]][kor[1]] = tall #setter inn et av tallene i den tomme rute

            if ferdig(scope_board,kor): #sjekker om brettet ble ferdig
                return scope_board

            neste_kor = finn_neste_koordintat(kor) #finner koordinatet til neste rute

            #sender brettet hvor vi har satt inn ett nytt tall til funksjonen, sånn at den prøver seg på neste rute
            neste_brett = brute_force(scope_board,neste_kor, scope = scope+1)

            if neste_brett: #se på kommentaren i "return false" linjen
                return neste_brett

        scope_board[kor[0]][kor[1]] = 0#hvis koden kommer hit betyr det at det ikke var noen av tallene i listen "lovlig_tall" som funket
        return False  #Da må vi "tømme" ruten (sette den lik 0) og få
                        # et av de tidligere "nivåene" prøve neste tall i sin "lovlige tall" liste
    else:
        if ferdig(scope_board,kor):
            return scope_board
        neste_kor = finn_neste_koordintat(kor)
        neste_brett = brute_force(scope_board, neste_kor, scope = scope +1)
        if neste_brett:
            return neste_brett


board = read_board('brett.txt')
losning = brute_force(board,(0,0))
smudprint(losning)