Sudoku überprüfen

[Beginner123]

Hallo, ich bin gerade dabei zu überprüfen, ob ein gegebenes Sudokukonstrukt korrekt ist.
Einfachheitshalber habe ich erstmal nur zwei Listen in eine gepackt.
Als Erstes schaue ich, ob irgendeine Zahl in der Liste doppelt vorkommt, das funktioniert auch, mein Problem ist jetzt der zweite Schritt,
wie prüfe ich nun, ob sich mehrere gleiche Elemente an gleichen Positionen befinden?

Mein Versuch sieht bisher so aus:

Code: Alles auswählen

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

def check_sudoku(sx):
    for i in sx:
        for j in i:
            if i.count(j) > 1:
                return False
    return True
            
check_sudoku(sx)

Hier ist nur mein erster Schritt, mein Versuch die Positionen zu vergleichen ist in tausenden Rekursionen ausgeatet und deshalb nur verwirrend und nicht hiflreich

[Sirius3]

Bei Sudoku muß man die Zahlen einer Spalte, einer Reihe oder eines Quadranten testen. Wenn ein Problem zu kompliziert ist, versuche es in Teilstücke aufzuteilen, in Deinem Fall, drei Funktion, eine die die Zahlen in Spalte n, eine für die Reihe m und eine für den Quadranten q zurückliefert. Am einfachsten ist die Funktion für die Reihen, dann für Spalten und bei der Funktion, die die Zahlen für einen Quadranten zurückliefert, mußt Du Dir überlegen, wie denn Deine Liste angeordnet ist, am besten, indem Du Dir die Indexe auf einem Stück Kästchenpapier aufschreibst.

Hast Du erst das Problem gelöst, die Zahlen für die verschiedenen Richtungen auszulesen ist das Vergleichen auf Doppelte immer das selbe und kann in einer weiteren Funktion erledigt werden.
Das letzte, was Du Dir schreibst ist dann die Funktion check_sudoku, die dann mit Schleifen alle Zeilen, Reihen und Quadranten durchgeht. Aber darum kümmerst Du Dich erst, wenn die anderen Funktionen ausführlich getestet sind, dass sie wirklich ihre Teilaufgabe richtig erledigen.

Als Anfänger möchte man oft gleich das "richtige" Problem lösen. Aber die sind meist zu komplex, um das eigentliche Problem zu verstehen, muß man es aufteilen und damit vereinfachen.

[noisefloor]

Hallo,

das Testen auf keine doppelten Einträge in der Liste geht einfacher über ein Set:

Code: Alles auswählen

>>> a = [1, 2, 3, 4]
>>> b = [1, 2, 1, 4]
>>> def check_for_all_unique_numbers(my_list):
...     if len(my_list) == len(set(my_list)):
...         print('nichts doppelt')
...     else:
...         print('Es gibt doppelte Werte.')
...
>>> check_for_all_unique_numbers(a)
nichts doppelt
>>> check_for_all_unique_numbers(b)
Es gibt doppelte Werte.
>>>

Zum Üben würde sich das auch "nur" für ein Sudoko von 1-4 beziehen, also insgesamt 16 Kästchen. Wenn's läuft ist das erweitern auf 81 Kästchen ja nur noch Fleißarbeit.

Gruß, noisefloor

[ThomasL]

Ich dachte mir, da könnte man doch was mit Views von Slices eines Numpy-Arrays machen....

Code: Alles auswählen

import numpy as np

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

board = np.asarray(matrix, dtype=np.int)

quadrants = []
for row in range(3):
    for col in range(3):
        quadrants.append(board[row*3:(row+1)*3, col*3:(col+1)*3])

rows = []
columns = []
for i in range(9):
    rows.append(board[i,:])
    columns.append(board[:,i])

def pruefe(elemente, location):
    for pos, element in enumerate(elemente):
        if len(set(element.flatten().tolist())) != 9:
            print(f'Error in {location} {pos}')

pruefe(quadrants, 'Quadrant')
pruefe(rows, 'Reihe')
pruefe(columns, 'Spalte')

board[8,5] = 5

pruefe(quadrants, 'Quadrant')
pruefe(rows, 'Reihe')
pruefe(columns, 'Spalte')

# Error in Quadrant 7
# Error in Reihe 8
# Error in Spalte 5

[noisefloor]

Hallo,

bisschen kürzer Ansatz via numpy:

Code: Alles auswählen

>>> import numpy as np
>>> matrix = [[8, 2, 7, 1, 5, 4, 3, 9, 6],
...           [9, 6, 5, 3, 2, 7, 1, 4, 8],
...           [3, 4, 1, 6, 8, 9, 7, 5, 2],
...           [5, 9, 3, 4, 6, 8, 2, 7, 1],
...           [4, 7, 2, 5, 1, 3, 6, 8, 9],
...           [6, 1, 8, 9, 7, 2, 4, 3, 5],
...           [7, 8, 6, 2, 3, 5, 9, 1, 4],
...           [1, 5, 4, 7, 9, 6, 8, 2, 3],
...           [2, 3, 9, 8, 4, 1, 5, 6, 7]]
>>> board = np.asarray(matrix, dtype=np.int)
>>> def check_for_unique_numbers(data):
...     for row in data:
...         if len(set(row))!=9:
...             print('not all unique numbers')
...         else:
...             print('all unique numbers')
... 
>>> check_for_unique_numbers(board)
all unique numbers
[...]
all unique numbers
>>> check_for_unique_numbers(board.transpose())
all unique numbers
[...]
all unique numbers
>>> quadrants = [board[x:x+3, y:y+3].flatten().tolist() for x in range(0, 7, 3) for y in range(0, 7, 3)]
>>> check_for_unique_numbers(quadrants)
all unique numbers
[...]
all unique numbers
>>>

Gruß, noisefloor

[Beginner123]

Danke für eure Hilfe, da ich Klassen noch nicht hatte und nicht importieren darf, habe ich versucht das was ihr geschieben habt ohne Klassen umzusetzen und mit ein bisschen raten, bin ich auf das Ergebnis gekommen, meine Tests gingen alle gut durch (Wahrscheinlich nicht perfekt):

Code: Alles auswählen

def check_sudoku(sx):
    for i in sx:
        for j in i:
            if i.count(j) > 1:
                return False
    spalten = []
    for j in range(len(sx)):
        for i in sx:
            spalten += [i[j]]
        if sorted(list(set(spalten))) != sorted(spalten):
            return False
        spalten = []
    return True
    

[Sirius3]

@Beginner123: Variablen initialisiert man, wenn man sie braucht, und nicht, wenn man mit ihnen fertig ist. Wenn man ein Element an eine Liste anhängen will, benutzt man append. Die if-Abfrage ist dann auch recht kompliziert.

Code: Alles auswählen

def check_sudoku(sx):
    for row in sx:
        if len(set(row)) < len(row):
            return False
    for j in range(len(sx)):
        column = []
        for row in sx:
            column.append(row[j])
        if len(set(column)) < len(column):
            return False
    return True

oder etwas knapper:

Code: Alles auswählen

def check_sudoku(sx):
    return (all(len(set(row)) == len(row) for row in sx)
        and (all(len(set(col)) == len(col) for col in zip(*sx))

Soweit zu "nicht perfekt". Schlimmer ist aber, dass das Ergebnis falsch ist. Die Quadranten werden nicht geprüft.

[Beginner123]

@Sirius Stimmt die Quadranten habe ich vergessen, das ist mir jedoch noch zu schwer für die Prüfung werde ich das nicht brauchen. Wichtig für mich ist es jetzt über 2 verschachtelte Listen, die Positionen vergleichen zu können, danke für die Hilfe, das mit den Variablen macht Sinn, werde ich ab jetzt mit berücksichtigen.
Ich versuche mich zu bemühen, momentan fällt mir das programmieren noch recht schwer, deshalb die ganzen Fehler...