Kanonische Form für Sudoku
Wie im vorherigen Kapitel beschrieben, kann man Sudokus auf bestimmte Arten verändern, ohne ihre Logik zu verändern.
Das macht es sehr schwer, zwei Sudokus zu vergleichen, da man, wenn man sie Zelle für Zelle vergleicht, häufig herausfindet dass sie unterschiedlich sind, obwohl sie der selben Logik folgen.
Deswegen definiert man eine sogenannte kanonische Form, d.h. eine Form, die für alle isomorphe Sudokus die selbe ist.
Zum Beispiel kann man sie folgendermaßen definieren: man schreibt die Zellen des Sudokus zeilenweise hintereinander, und für jede leere Zelle schreibt man eine Null auf.
Aus diesem Sudoku:
Wird dann
000000010400000000020000000000050407008000300001090000300400200050100000000806000.
Die kanonische Form ist das Sudoku, das als Zahl gelesen die kleinste Zahl ergibt, und das noch zu dem ursprünglichen Sudoku isomorph ist.
In diesem Fall ist das:
000000001000000020000003000000040500006000300007810000010020004030000070950000000
Oder als Grafik:
Es gibt Programme, die zu einem gegebenen Sudoku die kanonische Form ausgeben, z.B. YasSS.
top