Sudoku Zeilen

[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/