Sudoku Zeilen

[Blue Flare]

@Hyperion war mir schon klar das for i in range(0,1,1) nicht richtig ist....
habe es jz aber geschafft
hier der code:

Code: Alles auswählen

def ausgabe(p_liste):
    for i in range(0,9,1):
        for j in range(0,9,1):
            print(p_liste[i][j] ,end="\t")
        print("")


def pruefen_9mal_9(p_liste):
    #pruefen ob das sudoko neun mal neun felder hat
    anz = len(p_liste)
    for i in range(len(p_liste)):
        if len(p_liste[i]) == len(p_liste):
               anz -= 1
    if anz == 0:
        return True
    else:
        return False

def nach_rechts_pruefen(p_liste):
    leere_liste = []
    liste = [1,2,3,4,5,6,7,8,9]
    for i in range(0,9,1):
        leere_liste = p_liste[i]
        leere_liste = sorted(leere_liste)
        if leere_liste != liste:
            return False
    return True

def nach_unten_pruefen(p_liste):
    leere_liste = []
    liste = [1,2,3,4,5,6,7,8,9]
    for i in range(0,9,1):
        leere_liste = []
        for j in range(0,9,1):
            leere_liste += [p_liste[j][i]]
            leere_liste = sorted(leere_liste)
        if leere_liste != liste:
            return False
    return True

            
    




#******************************************************

liste = [[7,4,2,6,5,9,3,1,8], [5,1,9,4,8,3,6,2,7], [8,3,6,1,2,7,5,9,4],
         [4,6,1,5,7,8,9,3,2], [3,8,5,2,9,4,1,7,6], [9,2,7,3,1,6,4,8,5],
         [6,7,3,9,4,2,8,5,1], [2,5,4,8,3,1,7,6,9], [1,9,8,7,6,5,2,4,3]]


ausgabe(liste)

wahr = pruefen_9mal_9(liste)
print(wahr)


wahr = nach_rechts_pruefen(liste)
print(wahr)


wahr = nach_unten_pruefen(liste)
print(wahr)

falls iwem noch ein fehler auffallen sollte bitte posten
danke für die hilfe

[Hyperion]

Alleine hier ist schon mal vieles umständlich!

Code: Alles auswählen

def nach_rechts_pruefen(p_liste):
    leere_liste = []
    liste = [1,2,3,4,5,6,7,8,9]
    for i in range(0,9,1):
        leere_liste = p_liste[i]
        leere_liste = sorted(leere_liste)
        if leere_liste != liste:
            return False
    return True

* Man kann in Python direkt über Elemente einer Liste iterieren. Damit wird leere_liste überflüssig.
* die Namensgebung sollte keine Typen umfassen (_liste als suffix ist unnötig und u.U. sogar irreführend, wenn man etwas anders als eine Liste verwenden kann)
* "p_liste" soll für "pruef_liste" stehen? Wieso nennst Du die Struktur nicht einfach "sudoku"? Genau das repräsentiert die ja!
* "liste" könnte man auf Modulebene anlegen.
* liste = range(1, 10) sieht doch besser aus, oder?
* sorted_line wäre dafür ein schönerer Name, auf Modulebene würd ich es so schreiben:

Code: Alles auswählen

SORTED_LINE = range(1, 10)

Am Schluss bliebe dann nur noch das Folgende übrig (ungetestet):

Code: Alles auswählen

def check_east(sudoku):
    for line in sudoku:
        if not sorted(line) == SORTED_LINE:
            return False
    return True

Ich denke bei den anderen Funktionen könnte man auch noch viel "optimieren"

"wahr" als name ist auch nicht so toll - "result" wäre soch sinniger (oder eben "ergebnis", wenn man beim Deutschen bleiben will)

Ich finde ja immer noch meine Idee mit der Summe am besten... Sortieren kostet da bestimmt mehr!

[Xynon1]

@Hyperion
Ich finde Sortieren auch nicht schön, also hier nochmal mit summieren.

Die "sorted" Variante ist zwar sehr präzise, aber für ein Sodoku eigentlich nicht nötig und so wird dein Programm zwar Funktionieren, sieht aber nicht schön aus . Hyperion hatte dir vorhin schon einmal den Tipp "sum" gegeben, welches ich auch oben benutzt habe. Die Lösung oben ist für Python ideal, für dich im Moment augenscheinlich noch nicht. Deswegen nochmal hier ohne "numpy" und mit ein wenig mehr Erklärung.

In einem Sodoku darf man ja nur die Zahlen 1-9 in den Reihen und Spalten haben. Das macht pro Linie exakt den Wert 45. Wenn dieser in einer Linie stimmt, kann keine Zahl doppelt sein. Was wiederum bedeutet, wenn überall, also in jeder Zeile und Spalte sich der Wert 45 ergibt, alle Zahlen richtig stehen. Dann braucht man auch nicht mehr die in einem 3x3 Kasten prüfen.

Code: Alles auswählen

array = [[7,4,2,6,5,9,3,1,8], [5,1,9,4,8,3,6,2,7], [8,3,6,1,2,7,5,9,4],
         [4,6,1,5,7,8,9,3,2], [3,8,5,2,9,4,1,7,6], [9,2,7,3,1,6,4,8,5],
         [6,7,3,9,4,2,8,5,1], [2,5,4,8,3,1,7,6,9], [1,9,8,7,6,5,2,4,3]]

# Zeilen prüfen, in dem man einfach die Summe nimmt und auf 45 prüft
# weicht eine Zeile davon ab, wird False zurück gegeben.
def check_rows(array):
    for row in array:
        if sum(row) != 45:
            return False
    return True

# Die Spalten prüfen ist schon schwerer, aber im Prinzip das selbe. 
# Hier geht man einfach die Zahlen von 1 bis 9 und die Zeilen durch und
# greift dann auf den Index der Spalte zu, summiert diese wieder und vergleicht.
# Hast du im Prinzip schon (beim sortieren) gemacht.
def check_columns(array):
    for index in xrange(len(array)):
        if sum(column[index] for column in array) != 45:
	    return False
    return True

# Zu guter Letzt, prüfen ob beides Wahr ist, dann ist das Soduko auch richtig.
def check(array):
    return check_rows(array) and check_columns(array)

Ich hoffe das ist besser verständlich.

[Blue Flare]

ahh alles klar dass meintest du mit sum() (die funktion kenne ich nur was ich damit sollte wusste ich nicht...)
danke

[Xynon1]

check_rows könnte man nochmal so abkürzen:

Code: Alles auswählen

def check_rows(array):
    return all(sum(row) == 45 for row in array)

[Hyperion]

@Xynon1: Jetzt muss man nur noch eine Funktion get_cols() schreiben, um sich das redundante checken zu sparen

[Xynon1]

Ja, hatte ich auch schon daran gedacht.
Aber dann kannst du auch gleich wieder numpy nehmen, wie ich oben gepostet hatte.

[Hyperion]

Naja, geht ja auch ohne recht einfach:

Code: Alles auswählen

def iget_cols(sudoku):
    for index in xrange(len(sudoku)):
        yield map(itemgetter(index), sudoku)

[/me]

Code: Alles auswählen

[...]
    wahr = False
[...]

Der Name des Bezeichners ist extrem unglücklich.

Das verursacht ja Kopfschmerzen beim Lesen.

[Xynon1]

@Hyperion
Ich habe auch nicht behauptet das es schwer wäre , nur macht man so genau das gleiche wie in der "numpy" Version. Ist aber auf jedenfall besser, als zweimal zu prüfen.

In der numpy Version könnte man noch eine "lambda"-Funktion und ein "all" aus der Gleichung nehmen, in dem man so prüft:

Code: Alles auswählen

all(map(lambda x, y: x==y==45, array.sum(0), array.sum(1)))

[Hyperion]

Ich habe mir mal erlaubt, Xynon1s Script mit meinem get_cols()-Ansatz zu kombinieren: Link

Damit wären die Hausaufgaben wohl gelöst

Herr Lehrer, bitte um Benotung

@all: Wäre mal interessant, ob hier überhaupt Lehrkräfte angemeldet sind, die im Unterricht Python behandeln? Oder eben zur Not auch nur mitlesen?

[DaMutz]

die Lösung mit der Summe ist zwar schnell und findet einzelne Fehler. Es könnten aber 4 Zahlen falsch sein und dann findet man mit diesem Ansatz den Fehler nicht mehr:

Code: Alles auswählen

array = [[7,5,2,6,5,8,3,1,8], [5,1,9,4,8,3,6,2,7], [8,3,6,1,2,7,5,9,4],
         [4,5,1,5,7,9,9,3,2], [3,8,5,2,9,4,1,7,6], [9,2,7,3,1,6,4,8,5],
         [6,7,3,9,4,2,8,5,1], [2,5,4,8,3,1,7,6,9], [1,9,8,7,6,5,2,4,3]]

ich wäre ja für folgende Lösung:
- sortieren und mit einem Referenz Hash vergleichen

[Hyperion]

die Lösung mit der Summe ist zwar schnell und findet einzelne Fehler. Es könnten aber 4 Zahlen falsch sein und dann findet man mit diesem Ansatz den Fehler nicht mehr:

Stimmt!

- sortieren und mit einem Referenz Hash vergleichen

Na dann ist aber meine Lösung per set() und der Länge schneller!

Hier mal die umgestellte Version mit DaMutz Beispiel als invalides Sudoku.

[Xynon1]

@DaMutz
Mist, erwischt, wie lange hast du gebraucht das Beispiel zu finden?

[DaMutz]

@DaMutz
Mist, erwischt, wie lange hast du gebraucht das Beispiel zu finden?

vielleicht 1 Minute, du musst nur bei einer Zeile eine Zahl um 1 erhöhen, und eine andere Zahl um 1 verkleinern. In einer andere Zeile musst du das in der gleichen Spalte umgekehrt machen, also inkrementieren bei der dekrementierten Spalte (hoffentlich klar)...
Ausserdem hat der Algorithmus noch eine andere schwäche und zwar könnte ich auch Zahlen > 9 verwenden. Also folgendes Array:

Code: Alles auswählen

array = [[45,0,0,0,0,0,0,0,0], 
        [0,45,0,0,0,0,0,0,0],
        [0,0,45,0,0,0,0,0,0], 
        [0,0,0,45,0,0,0,0,0], 
        [0,0,0,0,45,0,0,0,0], 
        [0,0,0,0,0,45,0,0,0], 
        [0,0,0,0,0,0,45,0,0], 
        [0,0,0,0,0,0,0,45,0], 
        [0,0,0,0,0,0,0,0,45]]

oder mit negativen Zahlen, dann könnte man sogar das set() überlisten glaube ich im Moment zumindest, da aber ein Sudoku zu kreieren ist nicht so trivial (ich versuche es noch )

[EyDu]

Naja, die Konstruktion eines Gegenbeispiels ist doch ganz einfach. Angenommen ein beliebiges 2x2 Stück, welches vollständig innerhalb einer der 9 3x3 Blöcke liegt, hat die Form

Code: Alles auswählen

a b
c d

Dann kannst du dies in

Code: Alles auswählen

a+1 b-1
c-1 d+1

umwandeln. Offensichtlich bleiben alle Summen gleich.

Edit: Na da war ich aber viel zu langsam.

[DaMutz]

so das array mit negativen Zahlen:

Code: Alles auswählen

array = [[45, -1,  1, -2,  2, -3,  3, -4,  4], 
        [  4, 45, -1,  1, -2,  2, -3,  3, -4],
        [ -4,  4, 45, -1,  1, -2,  2, -3,  3], 
        [  3, -4,  4, 45, -1,  1, -2,  2, -3], 
        [ -3,  3, -4,  4, 45, -1,  1, -2,  2], 
        [  2, -3,  3, -4,  4, 45, -1,  1, -2], 
        [ -2,  2, -3,  3, -4,  4, 45, -1,  1], 
        [  1, -2,  2, -3,  3, -4,  4, 45, -1], 
        [ -1,  1, -2,  2, -3,  3, -4,  4, 45]]

dieser Fall kann natürlich durch abs() schnell detektiert werden...

[Hyperion]

Ok, man muss halt notfalls zusätzlich die Sudoku-Struktur gegen ein Alphabet checken.

[numerix]

Für alle, die jetzt noch nicht genug vom Sudoku-Prüfen haben, gibt es hier noch etwas zu beackern:
http://www.spoj.pl/SHORTEN/problems/SUDCHECK/