noch ein Sudoku

Code-Stücke können hier veröffentlicht werden.
Antworten
Siegfried
User
Beiträge: 24
Registriert: Sonntag 30. April 2017, 14:04

Ich habe mir einen Helfer bzw Lehrer für Anfänger für Sudoku Rätsel überlegt. Er war gerade fast fertig,als ich die Suchfunktion des Forums bemüht habe und mit Erschrecken feststellen musste, daß vor gerade einmal drei Monaten schon ein anderer Forist einen Sudoku Löser präsentiert hatte. Damit nicht genug wurde in dem Thread auch noch auf eine Internet Seite (http://www.norvig.com/sudoku.html) verwiesen, die jedes Sudoku löst. Aber zu meinem Glück blieb das Projekt des Kollegen vor der Vollendung stecken und Peter Norvig löst das Rätsel durch vollständiges Probieren. Dieses Verfahren ist für Rechner sehr gut geeignet, ist aber für Menschen ungeeignet ("unmenschlich"), da es viel zu viele Möglichkeiten gibt. Meine Zielsetzung ist hingegen, jeden Lösungsschritt nachvollziehbar zu zeigen.

Als Eingabe hatte ich mir das Format von http://www.sudoku-knacker.de überlegt. Auf der Seite ist unterhalb von jedem Rätsel das Rätsel als einzeiliger String aus Punkten und Ziffern dargestellt. Dadurch ist es möglich durch Strg-C und Strg-V die Rätsel in das Programm ohne aufwendige manuelle Eingaben zu kopieren und dann die Lösungsschritte auf der Sudoku-Knacker Seite einzugeben und nachzuvollziehen. Zufälligerweise benutzt Norvig das gleiche Format.

Das Grundprinzip ist simpel: Es wird mit NumPy für jede Ziffer eine Maske (aus boolschen Werten) erzeugt und dann für alle Bereiche (Zeile,Spalte oder Block) geguckt, ob es nur einen True Wert gibt, d.h. das die Ziffern nur auf eine mögliche Stelle paßt. Jeder gefundene Wert wird gesetzt und dann der Lösungsschritt ausgegeben. In der Ausgabe sieht man zum einen das Rätsel mit dem Lösungsschritt sowie Angaben in welchem Bereich welche Ziffer gesetzt wurde. Die Zeilen 18 und 41-42 sind nicht zwingend nötig, sie dienen nur der Geschwindigkeitssteigerung, da sie Ziffern bzw Bereiche,die abgearbeitet sind zukünftig nicht mehr berücksichtigen..


[codebox=python file=Unbenannt.txt]from __future__ import print_function
from itertools import product
from numpy import array as nparray

def sudoku(raetsel, ausgabe = ""):
def eindeutig(gefunden): ## sucht und setzt eindeutige Werte
for ziffer in uebrig.copy():
maske = vorbereitung(ziffer)
for bereich, sl in bereiche.iteritems():
if maske[sl].tostring().count("\x01") == 1: ## genau ein True
(raetsel[sl])[maske[sl]] = ziffer ## hier Setzung
if ausgabe in "vV":
print(raetsel, zsb[bereich[0]] + bereich[1], " Nr", ziffer, "\n")
elif ausgabe in "kK":
print(zsb[bereich[0]] + bereich[1], " Nr", ziffer)
maske = vorbereitung(ziffer)
gefunden = True
if raetsel.tostring().count(ziffer) == 9: uebrig.discard(ziffer)
return gefunden

def slice_ermitteln(c, nr): ## Danke nochmals an __deets__ und
if c == "Z": return nr ## BlackJack für Eure Geduld
elif c == "S": return (slice(None), nr)
else :
i1, i2 = nr // 3 * 3, nr % 3 * 3
return (slice(i1, i1 + 3), slice(i2, i2 + 3))

def vorbereitung(ziffer): ## ermittelt die Maske einer Ziffer für raetsel
maske = raetsel == leer
for sl in bereiche.itervalues(): ## für alle 9 (Zeilen, Spalten, Blöcke) = 27 bereiche
if ziffer in raetsel[sl]: maske[sl] = False
return maske

ziffern = nparray(list("123456789"))
zsb = {"Z" : "Zeile : ", "S" : "Spalte: ", "B" :"Block : "}
uebrig = set(ziffern)
bereiche = dict((c + str(nr), slice_ermitteln(c, nr)) for c, nr in product(zsb, range(9)))
while True:
gefunden = False
while eindeutig(gefunden): pass
for bereich,sl in bereiche.items():
if raetsel[sl].tostring().find(leer) < 0: bereiche.pop(bereich)
if not (gefunden and uebrig): break
return raetsel

r=".2..3...........4........7....5..2.11.....3..4....8....8.2..5..7..6.........1...."
leer = " "
raetsel = nparray(list(r.replace(".", leer))).reshape((9, 9))
sudoku(raetsel, ausgabe = "V") ##ausgabe="V"ollständig, "K"omprimiert oder keine

[/code]
Dadurch werden einige einfache Sudokus schon vollständig gelöst, aber weitem nicht alle. Jetzt kommt das Verfahren Zwillinge (,Drillinge,...) zum Zuge. Dies bedeutet, daß in einem Bereich zwei (oder drei ...) Ziffern nur auf zwei (oder drei ...)gleiche Felder gesetzt werden können. Im Beispiel bricht der Helfer in der o.a. Grundversion ab, ohne zu erkennen,daß in der letzten Spalte die Ziffern "2" und "3" nur an die Stellen 1 und 2 gesetzt werden können. Dieses heißt im Umkehrschluß, daß diese Stellen für alle anderen Ziffern nicht zur Verfügung stehen. Das Programm hat hierfür zwei Zusatzfunktionen (zwillinge, ausschluss) sowie noch eine Funktion (blockiere), die an die entsprechenden Stellen ein "A" (oder "B"...) setzt und alles rekursiv mit diesen Setzungen noch einmal aufruft.
Hierdurch schreitet der Lösungsprozeß deutlich voran und auch schon einige der "5 Sterne" Sudokus lassen sich lösen. Was aber noch nicht "erschlagen" ist, ist der der Fall das Ziffer a nur auf die Felder x und y, Ziffer b nur auf die Felder y und z sowie Ziffer c nur auf die Felder y und z eines Bereiches passen, d.h. drei (,vier,...) Ziffern teilen sich drei (,vier,...) Felder. Hierfür ist die Funktion mengen_abgleich da.
Die Ausgabe sieht nunmehr folgendermaßen aus:

[codebox=python file=Unbenannt.txt]

[[' ' '2' ' ' ' ' '3' ' ' ' ' '1' '5']
[' ' ' ' ' ' ' ' ' ' ' ' ' ' '4' 'A']
[' ' ' ' ' ' ' ' ' ' ' ' ' ' '7' 'A']
[' ' ' ' ' ' '5' '4' '3' '2' '9' '1']
['1' '5' '2' 'B' 'B' 'B' '3' '8' '4']
['4' ' ' ' ' '1' '2' '8' '7' '5' '6']
['6' '8' '1' '2' '9' '4' '5' '3' '7']
['7' ' ' ' ' '6' '8' '5' '1' '2' '9']
['2' '9' '5' '3' '1' '7' '4' '6' '8']] Zeile : 8 Nr 9 ['S832', 'B4976'[/code]]

Dabei ist in den eckigen Klammen die Liste mit den Sperren angegeben; im Beispiel erster Eintrag "S832" bedeutet "A" (erster Eintrag), Spalte 8, Ziffern "2" und "3". Der zweite Eintrag bedeutet "B" (zweiter Eintrag) ist in B4 für die Ziffern "4", "9", "7" und "6" reserviert.


Hier nun der vollständiger Helfer
[codebox=python file=Unbenannt.txt]
from __future__ import print_function
from itertools import combinations, groupby, product
from numpy import array as nparray
from re import compile as recompile

def sudoku(raetsel, sperren = [], ausgabe = "", uebrig = None, max_rekursionen = 2, bereiche=None):
def ausschluss(zk,ziffer):
zeichenkette = zk.tostring()
if suchwort.search(zeichenkette):
for ind, sperre in enumerate(sperren):
if ebene[ind] in zeichenkette and ziffer in sperre[2:]:
return True
return ziffer in zeichenkette

def blockiere (raets, mask, sperre):
pruef = raetsel.tostring()
speicher = raets[mask] ## Alte Werte merken
raets[mask] = ebene[len(sperren)] ## Stellen blockieren
sudoku(raetsel, sperren + [sperre], ausgabe, uebrig, max_rekursionen,bereiche)
raets[mask] = speicher ## Alte Werte zurück
return pruef <> raetsel.tostring() ## Hat sich etwas verändert?

def eindeutig(gefunden): ## sucht und setzt eindeutige Werte
for ziffer in uebrig.copy():
maske = vorbereitung(ziffer)
for bereich, sl in bereiche.iteritems():
if maske[sl].tostring().count("\x01") == 1: ## genau ein True
if not ausschluss(raetsel[sl], ziffer):
(raetsel[sl])[maske[sl]] = ziffer ## hier Setzung
if ausgabe in "vV":
print(raetsel, zsb[bereich[0]] + bereich[1], " Nr", ziffer, sperren, "\n")
elif ausgabe in "kK":
print(zsb[bereich[0]] + bereich[1], " Nr", ziffer, sperren)
maske = vorbereitung(ziffer)
gefunden = True
if raetsel.tostring().count(ziffer) == 9: uebrig.discard(ziffer)
return gefunden

def mengen_abgleich(): ## sperrt Mengen
for bereich, werte in groupby(sorted(mehrfach.items()), key = lambda x:x[0][:2]):
if bereich in bereiche:
werte = list(werte)
for i in range(3, len(werte)):
for kombination in combinations(werte, i):
menge1 = set("".join([kombi[2:] for kombi,nation in kombination]))
menge2 = set("".join([nation for kombi,nation in kombination]))
if len(menge1) == len(menge2):
sl=bereiche[bereich]
mask = nparray([c in menge1 for c in ziffern])
print(mask)
if bereich[0] == "B": mask = mask.reshape(3,3)
if blockiere(raetsel[sl], mask, bereich + "".join(menge2)):
return True
return False

def slice_ermitteln(c, nr): ## Danke nochmals an __deets__ und
if c == "Z": return nr ## BlackJack für Eure Geduld
elif c == "S": return (slice(None), nr)
else :
i1, i2 = nr // 3 * 3, nr % 3 * 3
return (slice(i1, i1 + 3), slice(i2, i2 + 3))

def vorbereitung(ziffer): ## ermittelt die Maske einer Ziffer für raetsel
maske = raetsel == leer
for sl in bereiche.itervalues(): ## für alle 9 (Zeilen, Spalten, Blöcke) = 27 bereiche
if ziffer in raetsel[sl]: maske[sl] = False
for ind, sperre in enumerate(sperren): ## - > nur bei Rekursion
nr = int(sperre[1])
i1,i2 = nr // 3 * 3, nr % 3 * 3
if ziffer in sperre[2:]:
sl = bereiche[sperre[:2]]
maske[sl] = False
zw=raetsel[sl].tostring()
if sperre[0] == "Z":
if zw.find(ebene[ind]) > 5: maske[i1:i1 + 3, 6: ] = False
elif zw.rfind(ebene[ind]) < 3: maske[i1:i1 + 3, :3] = False
elif zw.find(ebene[ind]) > 2 and zw.rfind(ebene[ind]) < 6:
maske[i1:i1 + 3, 3:6] = False
elif sperre[0] == "S":
if zw.find(ebene[ind]) > 5: maske[6: , i2:i2 + 3] = False
elif zw.rfind(ebene[ind]) < 3: maske[ :3, i2:i2 + 3] = False
elif zw.find(ebene[ind]) > 2 and zw.rfind(ebene[ind]) < 6:
maske[3:6, i2:i2 + 3] = False
return maske

def zwillinge(): ## sperrt "zwillinge", "Drillinge" ...
for ziffer in uebrig:
maske = vorbereitung(ziffer)
for bereich, sl in bereiche.iteritems():
if not ausschluss(raetsel[sl], ziffer):
if raetsel[sl].tostring().count(leer) > maske[sl].tostring().count("\x01"):
schluessel = bereich + ziffern[maske[sl].flatten()].tostring()
mehrfach[schluessel] = mehrfach.get(schluessel,"") + ziffer
if len(mehrfach[schluessel]) == len(schluessel) - 2:
print (maske[sl].flatten())
if blockiere(raetsel[sl], maske[sl], bereich + mehrfach[schluessel]):
return True
return False

suchwort1, suchwort2 = recompile("[A-Z]"), recompile("[ A-Z]")
ebene = [chr(i) for i in range(65, 95)]
ziffern = nparray(list("123456789"))
zsb = {"Z" : "Zeile : ", "S" : "Spalte: ", "B" :"Block : "}
if uebrig == None: uebrig = set(ziffern)
if bereiche == None:
bereiche = dict((c + str(nr), slice_ermitteln(c, nr)) for c, nr in product(zsb, range(9)))
while True:
gefunden = False
while eindeutig(gefunden): pass
for bereich,sl in bereiche.items():
if not suchwort2.search(raetsel[sl].tostring()): bereiche.pop(bereich)
if len(sperren) < max_rekursionen:
mehrfach = dict()
gefunden = zwillinge()
if (not gefunden) and uebrig and len(sperren) < max_rekursionen:
gefunden = mengen_abgleich()
if not (gefunden and uebrig): break
return raetsel

r=".2..3...........4........7....5..2.11.....3..4....8....8.2..5..7..6.........1...."
leer = " "
raetsel = nparray(list(r.replace(".", leer))).reshape((9, 9))
sudoku(raetsel, ausgabe = "V") ##ausgabe="V"ollständig, "K"omprimiert oder keine

[/code]
Nunmehr sind ca 90% der sehr schweren Rätsel lösbar. Da kein Programm besser ist als sein Programmierer und ich für die entsprechenden Sudokus auch keine Lösung außer Probieren kenne, bleiben die restlichen 10% nicht vollständig gelöst. Für den an Sudokus interessierten Laien sollte das Programm dennoch hilfreich sein, da er die Strategien "Zwillinge" und "Mengenausschluß" nachvollziehbar gezeigt bekommt.
Ich freue mich auf Anregungen und Kritiken von Euch
Zuletzt geändert von Anonymous am Mittwoch 31. Mai 2017, 20:49, insgesamt 1-mal geändert.
BlackJack

@Siegfried: Erst einmal zum ersten Quelltext:

Die Schreibweise ist teilweise schlecht zu lesen, weil so ziemlich jeder Leser gewohnt ist, dass nach einem Doppelpunkt für einen Block ein Zeilenumbruch folgt und auch einzeilige Blöcke in einer Zeile für sich und eingerückt stehen.

`leer` scheint eine Konstante zu sein. Für `ausgabe` würde ich auch Konstanten definieren.

Die verschachtelten Funktionen lassen sich nicht einzeln testen. Eine davon ist nicht einmal ein Closure. Wenn man sie heraus zieht, dann braucht `eindeutig()` ziemlich viele Argumente, da könnte man also überlegen was man zu einer Klasse zusammenfassen könnte.

`ziffern`/`uebrig` ist unnötig kompliziert.

Umwandeln von Arrays in Strings um dann Bytewerte zu zählen ist etwas unerwartet. Vergleichen und `sum()` ist da irgendwie intuitiver als auf einer Binärdatendarstellung eines Arrays zu operieren.

``string.find(character) < 0`` schreibt man besser als ``character in string``. Aber auch an der Stelle im Quelltext würde ich das Array nicht in einen String umwandeln, sondern direkt mit dem Array arbeiten.

`dict.pop()` ohne den Rückgabewert zu verwenden, wäre eher ein Fall für ``del``.

Das würde dann als Zwischenergebnis bei mir so aussehen:

Code: Alles auswählen

# coding: utf8
from __future__ import print_function
from itertools import product
from numpy import array as nparray

LEER = ' '
FULL_OUTPUT = 'V'
COMPRESSED_OUTPUT = 'K'
NO_OUPUT = None

ROW, COLUMN, BLOCK = 'ZSB'


def slice_ermitteln(c, nr):
    if c == ROW:
        return nr
    elif c == COLUMN:
        return (slice(None), nr)
    elif c == BLOCK:
        i1, i2 = nr // 3 * 3, nr % 3 * 3
        return (slice(i1, i1 + 3), slice(i2, i2 + 3))
    else:
        raise ValueError('unknown `c` value: {0!r}'.format(c))


def vorbereitung(raetsel, bereiche, ziffer):
    '''Ermittelt die Maske einer Ziffer für raetsel.'''
    maske = raetsel == LEER
    # für alle 9 (Zeilen, Spalten, Blöcke) = 27 bereiche
    for sl in bereiche.itervalues():
        if ziffer in raetsel[sl]:
            maske[sl] = False
    return maske


def eindeutig(raetsel, uebrig, bereiche, zsb, ausgabe, gefunden):
    '''Sucht und setzt eindeutige Werte.'''
    for ziffer in uebrig.copy():
        maske = vorbereitung(raetsel, bereiche, ziffer)
        for bereich, sl in bereiche.iteritems():
            if maske[sl].sum() == 1:  # genau ein True
                raetsel[sl][maske[sl]] = ziffer  # hier Setzung

                if ausgabe == FULL_OUTPUT:
                    print(
                        raetsel,
                        zsb[bereich[0]] + bereich[1],
                        ' Nr',
                        ziffer,
                        '\n',
                    )
                elif ausgabe == COMPRESSED_OUTPUT:
                    print(zsb[bereich[0]] + bereich[1], ' Nr', ziffer)
                
                maske = vorbereitung(raetsel, bereiche, ziffer)
                gefunden = True
                if (raetsel == ziffer).sum() == 9:
                    uebrig.discard(ziffer)

    return gefunden


def solve_sudoku(raetsel, ausgabe=NO_OUPUT):
    zsb = {ROW: 'Zeile : ', COLUMN: 'Spalte: ', BLOCK: 'Block : '}
    uebrig = set('123456789')
    bereiche = dict(
        (c + str(nr), slice_ermitteln(c, nr))
        for c, nr in product(zsb, xrange(9))
    )
    while True:
        gefunden = False
        while eindeutig(raetsel, uebrig, bereiche, zsb, ausgabe, gefunden):
            pass
        for bereich, sl in bereiche.items():
            if (raetsel[sl] != LEER).all():
                del bereiche[bereich]
        if not (gefunden and uebrig):
            break

    return raetsel


def main():
    source = (
        '.2..3....'
        '.......4.'
        '.......7.'
        '...5..2.1'
        '1.....3..'
        '4....8...'
        '.8.2..5..'
        '7..6.....'
        '....1....'
    )
    raetsel = nparray(list(source.replace('.', LEER))).reshape((9, 9))
    solve_sudoku(raetsel, ausgabe=FULL_OUTPUT)


if __name__ == '__main__':
    main()
Siegfried
User
Beiträge: 24
Registriert: Sonntag 30. April 2017, 14:04

@BlackJack: Vorab erst einmal vielen Dank für die Mühe, die Du gegeben hast. Leider bin ich in dieser Woche sehr eingespannt und komme erst am Wochenende dazu, mir Deine Anregungen richtig an zu gucken.
Antworten