Code of the Mathezirkel-Fraktivität "Sudoku-Solver"

sudoku.py

def zeichneSudoku(grid):
    print()

    for i in range(9):
        for j in range(9):
            # Zeichen malen
            if grid[i][j] == 0:
                print(" ", end=" ")
            else:
                print(grid[i][j], end=" ")

            # STRICH VERTIKAL
            if (j + 1) % 3 == 0 and j != 8:
                print("|", end="")

        # STRICH HORIZONTAL
        if (i + 1) % 3 == 0 and i != 8:
            print()
            for asd in range(10):
                print("--", end="")

        print()

    print()


def loeseSudoku(grid):
    gefunden, zeile, spalte = findeLeereStelle(grid)

    if not gefunden:
        # sudoku gelöst, weil alles gefüllt.
        return True

    # leere Stelle, probiere aus.
    for probierZahl in range(1, 10):
        darfErDas = (
            not zahlInSpalte(grid, spalte, probierZahl)
            and not zahlInZeile(grid, zeile, probierZahl)
            and not zahlInBox(grid, (zeile // 3) * 3, (spalte // 3) * 3, probierZahl)
        )

        if darfErDas:
            grid[zeile][spalte] = probierZahl

            if loeseSudoku(grid):
                return True

            # nicht geklappt für diese probierZahl
            grid[zeile][spalte] = 0

    return False


def zahlInSpalte(grid, spalte, zahl):
    for i in range(9):
        if grid[i][spalte] == zahl:
            return True
    return False


def zahlInZeile(grid, zeile, zahl):
    for i in range(9):
        if grid[zeile][i] == zahl:
            return True
    return False


def zahlInBox(grid, zeile, spalte, zahl):
    for i in range(3):
        for j in range(3):
            if grid[zeile + i][spalte + j] == zahl:
                return True
    return False


# (Gefunden, Zeile, Spalte)
def findeLeereStelle(grid):
    for zeile in range(9):
        for spalte in range(9):
            if grid[zeile][spalte] == 0:
                return (True, zeile, spalte)
    return (False, 0, 0)


if __name__ == "__main__":
    print("Löse das Sudoku:")

    # sudoku = [
    #     [3, 0, 6, 5, 0, 8, 4, 0, 0],
    #     [5, 2, 0, 0, 0, 0, 0, 0, 0],
    #     [0, 8, 7, 0, 0, 0, 0, 3, 1],
    #     [0, 0, 3, 0, 1, 0, 0, 8, 0],
    #     [9, 0, 0, 8, 6, 3, 0, 0, 5],
    #     [0, 5, 0, 0, 9, 0, 6, 0, 0],
    #     [1, 3, 0, 0, 0, 0, 2, 5, 0],
    #     [0, 0, 0, 0, 0, 0, 0, 7, 4],
    #     [0, 0, 5, 2, 0, 6, 3, 0, 0],
    # ]

    sudoku = [  # Höllisch
        [0, 4, 0, 0, 0, 0, 9, 2, 0],
        [0, 0, 2, 9, 0, 8, 5, 0, 0],
        [0, 0, 0, 0, 0, 6, 0, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0, 7],
        [0, 0, 0, 0, 3, 0, 0, 0, 0],
        [0, 0, 4, 5, 0, 2, 8, 0, 0],
        [0, 7, 0, 3, 0, 9, 0, 0, 8],
        [0, 0, 0, 0, 4, 0, 3, 0, 0],
        [0, 0, 9, 0, 6, 0, 0, 0, 0],
    ]

    # ! START TESTS
    # sudoku = [
    #     [0, 0, 7, 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, 0, 0, 0, 0, 0, 0, 0, 0],
    #     [0, 2, 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],
    #     [0, 0, 0, 0, 0, 0, 0, 0, 0],
    #     [0, 0, 0, 0, 0, 0, 5, 0, 0],
    # ]

    # print(zahlInSpalte(sudoku, 2, 7))  # True
    # print(zahlInSpalte(sudoku, 1, 7))  # False
    # print(zahlInSpalte(sudoku, 5, 7))  # False

    # print(zahlInZeile(sudoku, 4, 2))  # True
    # print(zahlInZeile(sudoku, 1, 2))  # False
    # print(zahlInZeile(sudoku, 5, 2))  # False

    # print(zahlInBox(sudoku, 6, 6, 5))  # True
    # print(zahlInBox(sudoku, 3, 0, 2))  # True
    # print(zahlInBox(sudoku, 3, 3, 2))  # False

    print(findeLeereStelle(sudoku))

    # ! ENDE TESTS

    zeichneSudoku(sudoku)

    print("Löse...")

    if loeseSudoku(sudoku):
        print("Gelöst:")
        zeichneSudoku(sudoku)

    else:
        print("Keine Lösung")