## Aufruf >>>test()
## vorher in test()n die zu lösende Aufgabe eintragen

## Hausübung:
## 1.) die Funktion show() soll die Lösung schön formatiert anzeigen:
##   - in Zeilen und Spalten
##   - mit Trennlinien nach jeweils 3 Zellen
##   - in einem GUI-Fenster mit Labels
## 2.) schreibe eine Funktion check(solution), die einen Lösungsstring
## entgegennimmt und auf Richtigkeit überprüft (Zahlen 1-9 in jeder Zeile,
## jeder Spalte und jedem Teilquadrat)
## 3.) das Programm soll nicht nur die erste (einzige?) Lösung ermitteln,
## sondern alle: angezeigt oder als Rückgabe (Sicherheitsschranke für die Anzahl!)

##
## 03/2006 Wolfgang.Urban@schule.at
##################################################################################

# Lösungsstring anzeigen
# er enthält 81 Zellenwerte von 1..9 für eine Zeile nach der anderen

def show(solution):
    print solution
    

# alle Zellen bestimmen, etwas mit dieser Zelle gemeinsam haben
def friends_of_cell(cell):
    row,col = cell/9,cell%9
    frnds = []
    ## Zellen in selber Zeile
    for x in range(9):
        f = row*9+x
        if not f in frnds: frnds.append(f)
    ## in selber Spalte
    for y in range(9):
        f = y*9+col
        if not f in frnds: frnds.append(f)
    ## in selbem Teilquadrat
    y,x = row-(row%3),col-(col%3) ## linke obere Ecke
    for xx in range(3):
        for yy in range(3):
            f = (y+yy)*9+(x+xx)
            if not f in frnds: frnds.append(f)
    frnds.remove(cell)  ## soll sich nicht selbst enthalten
    return frnds

# alle 'befreundeten' Zellen ermitteln 
def allfriendslist():
    friends = []
    for c in range(81):
        friends.append(friends_of_cell(c))
    return friends

friends = allfriendslist()

# welche Zelle soll als nächstes probeweise belegt werden
def selectunsolved(possibles,strategy=min):
    s = []
    for i in range(len(possibles)):
        if len(possibles[i])>1:
           s.append((len(possibles[i]),i))
    select = strategy(s)
    return select[1]


# LÖSE DAS RÄTSEL
## possibles = alle noch möglichen Belegungen,
## marks = auszuführende Belegungen
def solve(possibles,marks):
    # alle geplanten Belegungen eintragen
    for cell,value in marks:
        # Wert (zumindest probeweiseprobeweise) einsetzen
        possibles[cell] = value

        ## Wert aus allen übrigen Zellen der Bereiche entfernen
        ## und auf Widerspruch achten
        for f in friends[cell]:
            p = possibles[f]
            if value in p:
                p = possibles[f] = p.replace(value,'')  ## entfernen
                if not p: return None                   ## SACKGASSE
                if len(p)==1:                           ## Wert eindeutig,
                    marks.append((f,p[0]))              ## also setzen

    if max(map(len,possibles))==1:          ## alles ist eindeutig belegt
        return ''.join(possibles)           ## Lösung zurückgeben

    # falls Sudoku noch nicht fertig gelöst
    cell = selectunsolved(possibles)            ## nächster Kandidat
    
    for v in possibles[cell]:                   ## für jede Möglichkeit
        ans = solve(possibles[:],[(cell,v)])    ## setzen und ausprobieren
        if ans != None:                         ## falls Antwort existiert
            return ans                          ## zurückgeben

def test():
    problem1 = "6  3 2    4     1          7 26            543         8 15        4 2        7  "
    problem2 = "15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423"
    problem3 = "6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1...."

    problem = problem2
    show(problem)

    # alle Möglichkeiten
    possibles = ["123456789"]*81
    # Angabe eintragen
    marks = []
    for i in range(len(problem)):
        if problem[i] not in ' .':
            marks.append((i,problem[i]))
            
    # eine Lösung suchen
    result = solve(possibles,marks)
    if result: show(result)
    else: print "no solution possible"