#Listing 4: Funktion «loesen()»
def loesen(sudoku):

    MAXLINIEN = len(sudoku)
    MAXSPALTEN = MAXLINIEN

    # Beginne bei [0,0]
    pos = Position(MAXLINIEN,MAXSPALTEN)

    stapelAktuelle = []
    stapelMoegliche = []

    while not pos.ende():
        moegliche = test(sudoku,stapelAktuelle,pos.getZeile(),pos.getSpalte())

        while moegliche == []:
            if pos.ende():
                # Am Ende angekommen
                drucken(sudoku,stapelAktuelle)
                return True
            pos.naechste()
            moegliche = test(sudoku,stapelAktuelle,pos.getZeile(),pos.getSpalte())

        if moegliche == [-1]:
            # Backtracking
            zustand = stapelAktuelle.pop()
            while zustand[0] != stapelMoegliche[-1][0] or zustand[1] != stapelMoegliche[-1][1]:
                zustand = stapelAktuelle.pop()
            # Jetzt haben die letzten Zustaende von beiden dieselbe Position
            stapelAktuelle.append(stapelMoegliche.pop())
            # Setzen der richtigen Position
            pos.setZeile(stapelAktuelle[-1][0])
            pos.setSpalte(stapelAktuelle[-1][1])

        else:
            # Hier gibt es mehrere moegliche
            # Nimmt die Erste und legt sie auf stapelAktuelle 
		# und den Rest auf stapelMoegliche
            for moeglich in moegliche[1:]:
                stapelMoegliche.append([pos.getZeile(),pos.getSpalte(),moeglich])

            stapelAktuelle.append([pos.getZeile(),pos.getSpalte(),moegliche[0]])

        pos.naechste()

def existiert(sudoku, num, linie, spalte):
    gefunden = False
    for l in range(0,LINIEN):
        if sudoku[l][spalte] == num:
            gefunden = True

    for c in range(0,SPALTEN):
        if sudoku[linie][c] == num:
            gefunden = True
    return gefunden