TigerJython

Schülerarbeit: Sudoku-Solver

Der Sudoku-Solver von Yannick Niedermayr kann einfache bis mittelschwere Sudoku lösen.

Der Programm-Code

#
# (c) 2014, Yannick Niedermayr
#
from gturtle import *
from math import ceil

puzzlestring,testziffer,p,zeile,spalte,\
spezialliste1,spezialliste2,testcounter = [],0,0,0,0,[],[],1

# Sudoku selbst zeichnen
def draw():                                                         
    makeTurtle()
    hideTurtle()
    # Umrandung
    penDown()
    setPenColor("black")
    setLineWidth(2)
    setPos(-225,-225)
    repeat 4:
        forward(450)
        right(90)
    # 9Block-Unterteilung
    heading(90)
    setPos(-225,-75)
    forward(450)
    setPos(-225,75)
    forward(450)
    heading(0)
    setPos(-75,-225)
    forward(450)
    setPos(75,-225)
    forward(450)
    # 81Feld-Unterteilung
    heading(90)
    setLineWidth(1)
    x,y=-225,-175
    repeat 9:
        setPos(x,y)
        forward(450)
        y += 50
    heading(0)
    x,y=-175,-225
    repeat 8:
        setPos(x,y)
        forward(450)
        x += 50

# Eingabe der Ausgangssituation 
def stringeingabe(puzzlestring):                                        
    draw()
    x,y,feldcounter = -208,193,0
    setPos(x,y)
    repeat:
        e = inputInt("Zahl zwischen 1 und 9; 0 bedeutet leer; "+
                     "-1 um die letzte Zahl zu bearbeiten")
        if e == -1 and feldcounter > 0:
            puzzlestring.pop()
            x -= 40
            if x < -208:
                y += 50
                x = 193
            setPos(x,y)
            setPenColor("white")
            setLineWidth(22)
            forward(20)
            back(20)
            setPenColor("black")
            x -= 10
            setPos(x,y)
            feldcounter -= 1
        if not e == -1:
            f = int(head(str(e)))
            if f == 0: 
                f = "-"
                label(str(f))
                f = 0
            if f > 0:
                label(str(f))
            puzzlestring.append(f)
            x += 50
            if x > 208:
                y -= 50
                x = -208    
            setPos(x,y)
            feldcounter += 1
            if feldcounter == 81:
                break
    return puzzlestring 

# Lösung grafisch darstellen
def drawsolution(puzzlestring):                                                 
    # zahlenlabels
    draw()
    x,y,zahl = -208,193,0
    setPos(x,y)
    repeat 81:
        f = int(puzzlestring[zahl])
        label(str(f))
        x += 50
        if x > 208:
            y -= 50
            x = -208    
        setPos(x,y)
        zahl += 1

# Analyse der speziellen peers in Block-Position 1
def analyseBlockpos1():                                                                
    global testziffer,zeile,spalte,spezialliste1
    global spezialliste2,liste,p,o
    # zwei untere zeilen:
    if puzzlestring[testziffer + 1] and puzzlestring[testziffer + 2] > 0:       
        for o in range(9):
            p = puzzlestring[(zeile * 9) + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile + 1) * 9 + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True        
        if puzzlestring[testziffer +9] and puzzlestring[testziffer +10] and \
           puzzlestring[testziffer +11] > 0:
            for o in range(9):
                p = puzzlestring[((zeile + 1) * 9) + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer +18] and puzzlestring[testziffer +19] and \
           puzzlestring[testziffer +20] > 0:
            for o in range(9):
                p = puzzlestring[(zeile * 9) + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # zwei rechte spalten:
    if puzzlestring[testziffer + 9] and puzzlestring[testziffer + 18] > 0:       
        for o in range(9):
            p = 9*o + spalte
            test = puzzlestring[9*o + spalte]
            if (test > 0) and (test not in spezialliste1):
                spezialliste1.append(test)
        for o in range(9):
            p = (spalte+1) + 9 * o
            test = puzzlestring[(spalte+1) + 9 * o]
            if (test > 0) and (test not in spezialliste2):
                spezialliste2.append(test)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer + 1] and puzzlestring[testziffer + 10] and \
           puzzlestring[testziffer + 19] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte+1)]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer + 2] and puzzlestring[testziffer + 11] and \
           puzzlestring[testziffer + 20] > 0:
            for o in range(9):
                p = puzzlestring[9*o + spalte]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True
     

# Analyse der speziellen peers in Block-Position 2                
def analyseBlockpos2():                                                                    
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # zwei untere zeilen:
    if puzzlestring[testziffer - 1] and puzzlestring[testziffer + 1] > 0:           
        for o in range(9):
            p = puzzlestring[(zeile * 9) + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile + 1) * 9 + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer +8] and puzzlestring[testziffer + 9] and \
           puzzlestring[testziffer + 10] > 0:
            for o in range(9):
                p = puzzlestring[(zeile * 9) + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True
        if puzzlestring[testziffer +17] and puzzlestring[testziffer +18] and \
           puzzlestring[testziffer +18] > 0:
            for o in range(9):
                p = puzzlestring[(zeile + 1) * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True

    # linke und rechte spalten:                
    if puzzlestring[testziffer + 9] and puzzlestring[testziffer + 18] > 0:          
        for o in range(9):
            p = puzzlestring[9*o + (spalte-2)]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[9*o + spalte]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True  
        if puzzlestring[testziffer - 1] and puzzlestring[testziffer + 8] and \
           puzzlestring[testziffer + 17] > 0:
            for o in range(9):
                p = puzzlestring[9*o + spalte]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer +17] and puzzlestring[testziffer +18] and \
           puzzlestring[testziffer +19] > 0:
            for o in range(9):
                p = puzzlestring[9*o + spalte-2]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True
    
#  Analyse der speziellen peers in Block-Position 3
def analyseBlockpos3():                                                                    
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # zwei untere zeilen:
    if puzzlestring[testziffer - 2] and puzzlestring[testziffer - 1] > 0:           
        for o in range(9):
            p = puzzlestring[(zeile * 9) + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile + 1) * 9 + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer + 7] and puzzlestring[testziffer + 8] and \
           puzzlestring[testziffer + 9] > 0:
            for o in range(9):
                p = puzzlestring[(zeile + 1) * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer +16] and puzzlestring[testziffer + 17] and \
           puzzlestring[testziffer + 18] > 0:
            for o in range(9):
                p = puzzlestring[(zeile * 9) + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # zwei linke spalten:
    if puzzlestring[testziffer + 9] and puzzlestring[testziffer + 18] > 0:       
        for o in range(9):
            p = puzzlestring[9*o + (spalte-3)]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[9*o + (spalte-2)]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -2] and puzzlestring[testziffer +7] and \
           puzzlestring[testziffer +16] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte-2)]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -1] and puzzlestring[testziffer +8] and \
           puzzlestring[testziffer +17] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte-3)]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

#  Analyse der speziellen peers in Block-Position 4                   
def analyseBlockpos4():                                                                 
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # obere und untere zeile:
    if puzzlestring[testziffer + 1] and puzzlestring[testziffer + 2] > 0:        
        for o in range(9):
            p = puzzlestring[(zeile-2) * 9 + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile * 9) + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -9] and puzzlestring[testziffer -8] and \
           puzzlestring[testziffer -7] > 0:
            for o in range(9):
                p = puzzlestring[zeile * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer +9] and puzzlestring[testziffer + 10] and \
           puzzlestring[testziffer + 11] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-2) * 9 + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # zwei rechte spalten
    if puzzlestring[testziffer - 9] and puzzlestring[testziffer + 9] > 0:      
        for o in range(9):
            p = 9*o + spalte
            test = puzzlestring[9*o + spalte]
            if (test > 0) and (test not in spezialliste1):
                spezialliste1.append(test)
        for o in range(9):
            p = (spalte+1) + 9 * o
            test = puzzlestring[(spalte+1) + 9 * o]
            if (test > 0) and (test not in spezialliste2):
                spezialliste2.append(test)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -7] and puzzlestring[testziffer +2] and \
           puzzlestring[testziffer +11] > 0:
            for o in range(9):
                p = puzzlestring[9*o + spalte]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -8] and puzzlestring[testziffer +1] and \
           puzzlestring[testziffer +10] > 0:
            for o in range(9):
                p = puzzlestring[(spalte+1) + 9 * o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

#  Analyse der speziellen peers in Block-Position 5                 
def analyseBlockpos5():                                                                
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # obere und untere zeile:
    if puzzlestring[testziffer - 1] and puzzlestring[testziffer + 1] > 0:       
        for o in range(9):
            p = puzzlestring[(zeile-2) * 9 + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[zeile * 9 + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer - 10] and puzzlestring[testziffer -9] and \
           puzzlestring[testziffer -8] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-2) * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer +8] and puzzlestring[testziffer +9] and \
           puzzlestring[testziffer +10] > 0:
            for o in range(9):
                p = puzzlestring[(zeile * 9) + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # linke und rechte spalten:
    if puzzlestring[testziffer - 9] and puzzlestring[testziffer + 9] > 0:       
        for o in range(9):
            p = puzzlestring[9*o + (spalte-2)]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[9*o + spalte]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -10] and puzzlestring[testziffer -1] and \
           puzzlestring[testziffer +8] > 0:
            for o in range(9):
                p = puzzlestring[9*o + spalte]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -8] and puzzlestring[testziffer +1] and \
           puzzlestring[testziffer +10] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte-2)]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

#  Analyse der speziellen peers in Block-Position 6
def analyseBlockpos6():                                                                
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # obere und untere zeile:
    if puzzlestring[testziffer - 2] and puzzlestring[testziffer - 1] > 0:       
        for o in range(9):
            p = puzzlestring[(zeile-2) * 9 + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile * 9) + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer - 11] and puzzlestring[testziffer - 10] \
                                         and puzzlestring[testziffer -9] > 0:
            for o in range(9):
                p = puzzlestring[zeile * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer +7] and puzzlestring[testziffer +8] \
                                       and puzzlestring[testziffer + 9] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-2) * 9 + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # zwei linke spalten:
    if puzzlestring[testziffer - 9] and puzzlestring[testziffer + 9] > 0:       
        for o in range(9):
            p = puzzlestring[(spalte-3) + o * 9]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(spalte-2) + o * 9]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer - 11] and puzzlestring[testziffer - 2] \
                                         and puzzlestring[testziffer +7] > 0:
            for o in range(9):
                p = puzzlestring[(spalte-2) + o * 9]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -10] and puzzlestring[testziffer -1] and \
           puzzlestring[testziffer +8] > 0:
            for o in range(9):
                p = puzzlestring[(spalte-3) + o * 9]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

#  Analyse der speziellen peers in Block-Position 7
def analyseBlockpos7():                                                                
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # zwei obere zeilen  
    if puzzlestring[testziffer + 1] and puzzlestring[testziffer + 2] > 0:       
        for o in range(9):
            p = puzzlestring[(zeile-3) * 9 + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile-2) * 9 + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -18] and puzzlestring[testziffer -17] and \
           puzzlestring[testziffer -16] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-2) * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -9] and puzzlestring[testziffer -8] and \
           puzzlestring[testziffer -7] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-3) * 9 + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # zwei rechte spalten
    if puzzlestring[testziffer - 18] and puzzlestring[testziffer - 9] > 0:     
        for o in range(9):
            p = 9*o + spalte
            test = puzzlestring[9*o + spalte]
            if (test > 0) and (test not in spezialliste1):
                spezialliste1.append(test)
        for o in range(9):
            p = (spalte+1) + 9 * o
            test = puzzlestring[(spalte+1) + 9 * o]
            if (test > 0) and (test not in spezialliste2):
                spezialliste2.append(test)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -17] and puzzlestring[testziffer -8] and \
           puzzlestring[testziffer +1] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte+1)]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -16] and puzzlestring[testziffer -7] and \
           puzzlestring[testziffer +2] > 0:
            for o in range(9):
                p = puzzlestring[spalte + 9 * o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

#  Analyse der speziellen peers in Block-Position 8
def analyseBlockpos8():                                                                
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # zwei obere zeilen:
    if puzzlestring[testziffer - 1] and puzzlestring[testziffer + 1] > 0:       
        for o in range(9):
            p = (zeile-3) * 9 + o
            test = puzzlestring[(zeile-3) * 9 + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = (zeile-2) * 9 + o
            test = puzzlestring[(zeile-2) * 9 + o]
            if (test > 0) and (test not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer - 19] and puzzlestring[testziffer -18] and \
           puzzlestring[testziffer -17] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-2) * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer - 10] and puzzlestring[testziffer -9] and \
           puzzlestring[testziffer -8] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-3) * 9 + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # linke und rechte spalten
    if puzzlestring[testziffer - 18] and puzzlestring[testziffer - 9] > 0:       
        for o in range(9):
            p = puzzlestring[9*o + (spalte-2)]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[9*o + spalte]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -19] and puzzlestring[testziffer -10] and \
           puzzlestring[testziffer -1] > 0:
            for o in range(9):
                p = puzzlestring[9*o + spalte]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -17] and puzzlestring[testziffer -8] and \
           puzzlestring[testziffer +1] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte-2)]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

#  Analyse der speziellen peers in Block-Position 9
def analyseBlockpos9():                                                     
    global testziffer,zeile,spalte,spezialliste1,spezialliste2,liste,p,o
    # zwei obere zeilen:
    if puzzlestring[testziffer - 2] and puzzlestring[testziffer - 1] > 0:       
        for o in range(9):
            p = puzzlestring[(zeile-3) * 9 + o]
            if (p > 0) and (p not in spezialliste1):
                spezialliste1.append(p)
        for o in range(9):
            p = puzzlestring[(zeile-2) * 9 + o]
            if (p > 0) and (p not in spezialliste2):
                spezialliste2.append(p)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer - 20] and puzzlestring[testziffer - 19] \
                                         and puzzlestring[testziffer -18] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-3) * 9 + o]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer - 11] and puzzlestring[testziffer - 10] \
                                         and puzzlestring[testziffer -9] > 0:
            for o in range(9):
                p = puzzlestring[(zeile-2) * 9 + o]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True

    # zwei linke spalten:
    if puzzlestring[testziffer - 18] and puzzlestring[testziffer - 9] > 0:       
        for o in range(9):
            p = 9*o + (spalte-3)
            test = puzzlestring[9*o + (spalte-3)]
            if (test > 0) and (test not in spezialliste1):
                spezialliste1.append(test)
        for o in range(9):
            test = puzzlestring[9*o + (spalte-2)]
            p = 9*o + (spalte-2)
            if (test > 0) and (test not in spezialliste2):
                spezialliste2.append(test)
        if speziallistecompare(liste):
            return True
        if puzzlestring[testziffer -20] and puzzlestring[testziffer -11] and \
           puzzlestring[testziffer -2] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte-2)]
                if (p > 0) and (p not in spezialliste1):
                    spezialliste1.append(p)
            if speziallistecomparenospezialliste2():
                return True
        if puzzlestring[testziffer -19] and puzzlestring[testziffer -10] and \
           puzzlestring[testziffer -1] > 0:
            for o in range(9):
                p = puzzlestring[9*o + (spalte-3)]
                if (p > 0) and (p not in spezialliste2):
                    spezialliste2.append(p)
            if speziallistecomparenospezialliste1():
                return True


# listen vergleichen
def speziallistecompare(liste):                                     
    global spezialliste1,spezialliste2,testziffer
    h = 0
    if len(spezialliste1) - len(spezialliste2)> 0:
        repeat len(spezialliste1):
            if spezialliste1[h] in liste :
                if spezialliste1[h] in spezialliste2:
                    puzzlestring[testziffer] = int(spezialliste1[h])
                    testziffer,spezialliste1,spezialliste2 = 0,[],[]
                    return puzzlestring, testziffer, True 
                    
            h += 1
    if len(spezialliste2) - len(spezialliste1)> 0:
        repeat len(spezialliste2):
            if spezialliste2[h] in liste :
                if spezialliste2[h] in spezialliste1:
                    puzzlestring[testziffer] = int(spezialliste2[h])
                    testziffer,spezialliste1,spezialliste2 = 0,[],[]
                    return puzzlestring, testziffer, True 
    if len(spezialliste2) - len(spezialliste1)== 0:
        repeat len(spezialliste1):
            if spezialliste2[h] in liste :
                if spezialliste2[h] in spezialliste1:
                    puzzlestring[testziffer] = int(spezialliste2[h])
                    testziffer,spezialliste1,spezialliste2 = 0,[],[]
                    return puzzlestring, testziffer, True 
            h += 1
    spezialliste1,spezialliste2 = [],[]
    return False

# Listen(ohne Spezialliste2) vergleichen    
def speziallistecomparenospezialliste2():                             
    global spezialliste1,liste,testziffer
    h,moeglichkeiten = 0,0
    repeat len(spezialliste1):
        if spezialliste1[h] in liste :
            moeglichkeiten += 1
            zahl = int(spezialliste1[h])
        h += 1
    if moeglichkeiten == 1:
        puzzlestring[testziffer] = zahl
        testziffer,spezialliste1 = 0,[]
        return puzzlestring, testziffer, spezialliste1, True
    spezialliste1 = []
    return False

# Listen(ohne Spezialliste1) vergleichen
def speziallistecomparenospezialliste1():                             
    global spezialliste2,liste,testziffer
    h,moeglichkeiten = 0,0
    repeat len(spezialliste2):
        if spezialliste2[h] in liste :
            moeglichkeiten += 1
            zahl = int(spezialliste2[h])
        h += 1
    if moeglichkeiten == 1:
        puzzlestring[testziffer] = zahl
        testziffer,spezialliste2 = 0,[]
        return puzzlestring, testziffer, spezialliste2, True
    spezialliste2 = []
    return False

# check(): Überprüfen, ob die Zahl noch in "Liste" ist    
def check():                                                            
    global puzzlestring,testziffer,p,liste
    if puzzlestring[p] != 0:
        if puzzlestring[p] in liste:
            liste.remove(puzzlestring[p])
        if len(liste) == 1:
            puzzlestring[testziffer] = int(liste[0])
            testziffer = 0
            return puzzlestring, True  

# Algorithmus zum Überprüfen von Feldern
def peers():                                                            
    global testziffer,p,liste,zeile,spalte,spezialliste1,spezialliste2    
    repeat:
        if testziffer == 81:
            return False
        v = puzzlestring[testziffer]
        if v == 0:
            break
        testziffer += 1
        # zeile überprüfen
    zeile = int(ceil((testziffer + 1) / 9))
    zeilereset = zeile
    liste = [1,2,3,4,5,6,7,8,9]
    for o in range(9):
        p = (zeile-1)*9 + o
        if check():
            return puzzlestring

        # spalte überprüfen
    spalte = int(testziffer + 1 - ((zeile - 1 ) * 9))
    for o in range(9):
        p = 9*o + (spalte - 1)
        if check():
            return puzzlestring
    x = 0
            
        # bestimmen des blockes
    blockspalte = ceil(spalte / 3)
    blockzeile = ceil(zeile / 3)
    block = int(blockspalte + ((blockzeile - 1) * 3))

        # ermitteln der block-startposition(linke obere ecke)
    if block == 1:
        p = 0

    elif block == 2:
        p = 3

    elif block == 3:
        p = 6

    elif block == 4:
        p = 27

    elif block == 5:
        p = 30

    elif block == 6:
        p = 33

    elif block == 7:
        p = 54

    elif block == 8:
        p = 57

    elif block == 9:
        p = 60

        #überprüfen im block:
    blockz = 0
    blocks = 0 
    repeat 9:
        if blocks == 3:
            blockz += 1
            blocks = 0
            p += 6
        blocks += 1
        if check():
            return puzzlestring

        p += 1

        # bestimmung position im block

    poszeile = zeile / 3 - (blockzeile - 1)
    posspalte = spalte / 3 - (blockspalte - 1)
    if poszeile < 0.5:
        blockposzeile = 1
    if poszeile > 0.5:
        blockposzeile = 2
    if poszeile == 1:
        blockposzeile = 3
    if posspalte < 0.5:
        blockposspalte = 1
    if posspalte > 0.5:
        blockposspalte = 2
    if posspalte == 1:
        blockposspalte = 3

    blockpos = int(blockposspalte + ((blockposzeile - 1)* 3))
        # algorithmus für spezielle peers
    
    if blockpos < 4:
        if blockpos == 1:
            analyseBlockpos1()
        elif blockpos == 2:
            analyseBlockpos2()
        elif blockpos == 3:
            analyseBlockpos3()
    elif 3 < blockpos < 7:
        if blockpos == 4:
            analyseBlockpos4()
        elif blockpos == 5:
            analyseBlockpos5()
        elif blockpos == 6:
            analyseBlockpos6()
    elif 6 < blockpos < 10:
        if blockpos == 7:
            analyseBlockpos7()
        elif blockpos == 8:
            analyseBlockpos8()
        elif blockpos == 9:
            analyseBlockpos9()
           
    # wenn nicht eindeutige zahl
    testziffer += 1

# MAIN; Eingabe der Ausgangssituation
stringeingabe(puzzlestring)                                                 
repeat:                    
    print str(puzzlestring)
    # wenn alle Zahlen bekannt --> Lösungsausgabe
    if 0 not in puzzlestring:                                               
        drawsolution(puzzlestring)
        break
    # wenn nicht lösbar --> Fehlermeldung
    if peers() == False:                                                    
        msgDlg("Dieses Sudoku ist (für den Solver) nicht "+
               "lösbar bzw. schon gelöst.")
        break
    testcounter += 1