Beispiel Nr.1 (Bonsai)

Betrachten wir ein erstes einfaches Beispiel (aus der besagten TV-Zeitschrift):

!   3.    5.    0.    6.    9.    1.    0.    7.    2. !
!   2.    1.    6.    0.    7.    0.    5.    9.    4. !
!   0.    0.    0.    2.    5.    4.    0.    0.    0. !
!   1.    0.    0.    0.    3.    0.    0.    0.    7. !
!   8.    4.    9.    0.    0.    0.    6.    5.    3. !
!   5.    0.    0.    0.    4.    0.    0.    0.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !

(Die '0' stehen für leere Felder. Die '!' repräsentieren eine Begrenzung. Das gesamte Format stammt aus dem opensource Programm 'scilab' (www.scilab.org). Ich habe das Programm scilab benutzt, um einige der Berechnungen vorzunehmen).

58% der Felder sind mit Ziffern vorbesetzt. Ist es nun leicht oder gibt es da verborgene Fallen?

Wie soll man vorgehen?

Da jede Entscheidung für ein bestimmtes Feld Xi.j Auswirkungen auf nachfolgende Entscheidungen hat, wäre eine Strategie die, von einem definierten Startpunkt auszugehen und alle Möglichkeiten vom Start weg systematisch duchzuprobieren. Solch ein definierter Ausgangspunkt könnte die erste Zeile sein (Z1), die man von links nach rechts spaltenweise abarbeitet (S1, ..., S9). Ist man damit fertig, nimmt man sich die nächste Zeile im gleichen Stil vor, also Z2 mit  (S1, ..., S9). usw. (In der Theorie des maschinellen Lernens nennt man solch eine Strategie 'breadth first', Breite zuerst, im Gegensatz zu 'depth first', Tiefe zuerst).

Versuchen wir unser Glück damit.

Zeile 1
In der ersten Zeile gibt es nur in Spalte S3 und S7 ein freies Feld.
Für Feld X1.3 gilt, dass die neue Ziffer weder in Z1, noch in S3 noch im Unterquadrat Q1.3 vorkommen darf. Ausserdem muss Sie in allen drei potentiellen Mengen noch möglich sein. Schauen wir uns das an:

Z1- =  {4,8}
S3- =  {1,2,3,4,7,8}
Q1.3- = Q1 = {4,7,8,9}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X1.3 aus Z1- geschnitten mit  S3- geschnitten mit Q1- =  {4,8}

Für das Feld X1.7 bekommt man:

Z1- =  {4,8}
S7- =  {1,2,3,4,8,9}
Q1.7- = Q3 = {1,3,6,8}


Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X1.7 aus Z1- geschnitten mit  S7- geschnitten mit Q3- =  {8}

Daraus kann man erkennen, dass man für das Feld X1.7 die '8' wählen muss, da es nur diese eine Möglichkeit gibt. Damit fällt die '8' für das andere Feld X1.3 aus, da in Zeile Z1 jede Ziffer nur einmal vorkommen darf. Also folgt für X1.3 als mögliche Ziffer nur die '4'.

Die Zeile Z1 ist damit voll 'deterministisch', d.h. es gibt keine Alternativen, daher: free(Z1) = 1.

Als Ergebnis erhalten wir für das ganze Feld damit:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    0.    7.    0.    5.    9.    4. !
!   0.    0.    0.    2.    5.    4.    0.    0.    0. !
!   1.    0.    0.    0.    3.    0.    0.    0.    7. !
!   8.    4.    9.    0.    0.    0.    6.    5.    3. !
!   5.    0.    0.    0.    4.    0.    0.    0.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !



Zeile 2
In der zweiten Zeile gibt esfreie Zellen in Spalte S4 und S6.
Für Feld X2.4 gilt wieder, dass die neue Ziffer weder in Z2, noch in S4 noch im Unterquadrat Q2.4 = Q2 vorkommen darf. Ausserdem muss Sie in allen drei potentiellen Mengen noch möglich sein.D.h.:

Z2- =  {3,8}
S4- =  {3,5,7,8,9}
Q2.4- = Q2 = {3,8}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X2.4 aus Z2- geschnitten mit  S4- geschnitten mit Q2- =  {3,8}

Für das Feld X2.6 bekommt man:

Z2- =  {3,8}
S6- =  {2,3,6,8,9}
Q2.6- = Q2 = {3,8}


Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X2.6 aus Z2- geschnitten mit  S6- geschnitten mit Q2- =  {3,8}

Hier gibt es zwei Möglichkeiten, von denen man eine auswählen muss: (i) entweder die '3' für X2.4 und die '8' für X2.6 oder umgekehrt. Entscheiden wir uns für die erste Variante: X2.4 = '3' und X.2.6 = '8'.

Die Zeile Z2 ist damit nich vollständig deterministisch. Grundsätzlich könnte es sein, dass sich in einer späteren Zeile herausstellt, dass es ein Problem gibt, und dieseswäre nur lösbar, wenn man sich  statt für die '3' in X2.4 und die '8' in X2.6 genau umgekehrt entschieden hätte.  Zum aktuellen Zeitpunkt kann man dies nicht wissen. Man muss die Kombinatorik bis zu Ende durchspielen, um die Fakten zu kennen (es deutet sich allerdings an, dass man tatsächlich auch zu diesem Zeitpunkt schon mehr wissen könnte, aber darüber später mehr).

Für Zeile Z2 gilt: free(Z2) = 2.

Wir erhalten nun folgende Situation:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   0.    0.    0.    2.    5.    4.    0.    0.    0. !
!   1.    0.    0.    0.    3.    0.    0.    0.    7. !
!   8.    4.    9.    0.    0.    0.    6.    5.    3. !
!   5.    0.    0.    0.    4.    0.    0.    0.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !

In den folgenden beiden Zeilen Z3 und Z4 müssen jeweils 6 Zellen besetzt werden.


Zeile 3
In der dritten Zeile gibt esfreie Zellen in den  Spalten S1,S2,S3, S7,S8,S9.
Wir erhalten:

Z3- =  {1,3,6,7,8,9}

S1- =  {4,9}
S2- =  {3,6,7,9}
S3- =  {1,2,3,7,8}
S7- =  {1,2,3,4,9}
S8- =  {1,2,6,8}
S9- =  {5,6}

Q1- = {7,8,9}
Q3- = {1,3,6}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X3.1 aus Z3- geschnitten mit  S1- geschnitten mit Q1- =  {9}
X3.2 aus Z3- geschnitten mit  S2- geschnitten mit Q1- =  {7,9}
X3.3 aus Z3- geschnitten mit  S3- geschnitten mit Q1- =  {7,8}
X3.7 aus Z3- geschnitten mit  S7- geschnitten mit Q3- =  {1,3}
X3.8 aus Z3- geschnitten mit  S8- geschnitten mit Q3- =  {1,6}
X3.9 aus Z3- geschnitten mit  S9- geschnitten mit Q3- =  {6}

Betrachtet man alle Möglichkeiten gleichzeitig, dann kann man mit den Feldern beginnen, die keine Wahl haben, und zugleich muss man diese Ziffern aus der Menge der möglichen Ziffern streichen, da sie ja nur 1x in einer Zeile vorkommen dürfen. Man erhält damit:

X3.1 aus Z3- geschnitten mit  S1- geschnitten mit Q1- =  {9}<-- Fixiert
X3.2 aus Z3- geschnitten mit  S2- geschnitten mit Q1- =  {7}<-- Fixiert
X3.3 aus Z3- geschnitten mit  S3- geschnitten mit Q1- =  {8}<-- Fixiert
X3.7 aus Z3- geschnitten mit  S7- geschnitten mit Q3- =  {3}<-- Fixiert
X3.8 aus Z3- geschnitten mit  S8- geschnitten mit Q3- =  {1}<-- Fixiert
X3.9 aus Z3- geschnitten mit  S9- geschnitten mit Q3- =  {6}<-- Fixiert

Damit haben alle Felder einen Wert zugewiesen bekommen. Dies führt zu folgendem Resultat:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    0.    0.    0.    3.    0.    0.    0.    7. !
!   8.    4.    9.    0.    0.    0.    6.    5.    3. !
!   5.    0.    0.    0.    4.    0.    0.    0.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8.


Für Zeile Z3 gilt: free(Z3) = 1.

Zeile 4
In der vierten Zeile gibt esfreie Zellen in den  Spalten S2,S3, S4,S6, S7, S8.
Wir erhalten:

Z4- =  {2,4,5,6,8,9}

S2- =  {3,6,9}
S3- =  {1,2,3,7}
S4- =  {5,7,8,9}
S6- =  {2,3,6,9}
S7- =  {1,2,4,9}
S8- =  {2,6,8}

Q4- = { 2,    3,   6,    7}
Q5- = {1,    2,    5,    6,    7,    8,    9}
Q6- = {1,    2,    4,    8}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q1- =  {6}
X4.3 aus Z4- geschnitten mit  S3- geschnitten mit Q1- =  {2}
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q2- =  {5,8,9}
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q2- =  {2,6,9}
X4.7 aus Z4- geschnitten mit  S7- geschnitten mit Q3- =  {2,4}
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q3- =  {2,8}

Betrachtet man alle Möglichkeiten gleichzeitig, dann kann man mit den Feldern beginnen, die keine Wahl haben, und zugleich muss man diese Ziffern aus der Menge der möglichen Ziffern streichen, da sie ja nur 1x in einer Zeile vorkommen dürfen. Man erhält damit:

X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q1- =  {6}<-- Fixiert 1
X4.3 aus Z4- geschnitten mit  S3- geschnitten mit Q1- =  {2}<-- Fixiert 1
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q2- =  {5,8,9}
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q2- =  {9}
X4.7 aus Z4- geschnitten mit  S7- geschnitten mit Q3- =  {4}
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q3- =  {8}

Als Ergebnis der ersten Fixierung ergeben sich neue Elemente mir nur einer Option:

X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q1- =  {6}<-- Fixiert 1
X4.3 aus Z4- geschnitten mit  S3- geschnitten mit Q1- =  {2}<-- Fixiert 1
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q2- =  {5}
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q2- =  {9}<-- Fixiert 2
X4.7 aus Z4- geschnitten mit  S7- geschnitten mit Q3- =  {4}<-- Fixiert 2
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q3- =  {8}<-- Fixiert 2


Als Ergebnis der zweiten Fixierung ergeben sich wieder neue Elemente mir nur einer Option:

X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q1- =  {6}<-- Fixiert 1
X4.3 aus Z4- geschnitten mit  S3- geschnitten mit Q1- =  {2}<-- Fixiert 1
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q2- =  {5}<-- Fixiert 3
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q2- =  {9}<-- Fixiert 2
X4.7 aus Z4- geschnitten mit  S7- geschnitten mit Q3- =  {4}<-- Fixiert 2
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q3- =  {8}<-- Fixiert 2

Damit haben alle Felder einen Wert zugewiesen bekommen. Dies führt zu folgendem Resultat:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    6.    2.    5.    3.    9.    4.    8.    7. !
!   8.    4.    9.    0.    0.    0.    6.    5.    3. !
!   5.    0.    0.    0.    4.    0.    0.    0.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !

Die Zeile 4 ist damit auch deterministisch. Die Zuweisungen er geben sich zwangshaft; Alternativen sind nicht möglich.

Für Zeile Z4 gilt: free(Z4) = 1.

Zeile 5
In der fünften Zeile gibt es freie Zellen in den  Spalten S4,S5, S6.
Wir erhalten:

Z5- =  {1,2,7}

S4- =  {7,8,9}
S5- =  {1}
S6- =  {2,3,6}

Q5- = {1,2,6,7,8}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X5.4 aus Z5- geschnitten mit  S4- geschnitten mit Q5- =  {7}
X5.5 aus Z5- geschnitten mit  S5- geschnitten mit Q5- =  {1}
X5.6 aus Z5- geschnitten mit  S6- geschnitten mit Q5- =  {2}

Da es für jedes Element nur genau eine Wahl gibt, ist die Belegung schon entschieden. Die Zeile 5 ist also auch deterministisch.

Für Zeile Z5 gilt: free(Z5) = 1.

Als Resultat erhalten wir:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    6.    2.    5.    3.    9.    4.    8.    7. !
!   8.    4.    9.    7.    1.    2.    6.    5.    3. !
!   5.    0.    0.    0.    4.    0.    0.    0.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !


Zeile 6

In der sechsten Zeile gibt esfreie Zellen in den  Spalten S2,S3, S4,S6, S7, S8.
Wir erhalten:

Z6- =  { 1,    2,    3,    6,    7,    8}

S2- =  {3,9}
S3- =  {1,3,7}
S4- =  {8,9}
S6- =  {3,6}
S7- =  {1,2,9}
S8- =  {2,6}

Q4- = {3,7}
Q5- = {6,8}
Q6- = {1,2}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X6.2 aus Z6- geschnitten mit  S2- geschnitten mit Q4- =  {3}
X6.3 aus Z6- geschnitten mit  S3- geschnitten mit Q4- =  {3,7}
X6.4 aus Z6- geschnitten mit  S4- geschnitten mit Q5- =  {8}
X6.6 aus Z6- geschnitten mit  S6- geschnitten mit Q5- =  {6}
X6.7 aus Z6- geschnitten mit  S7- geschnitten mit Q6- =  {1,2}
X6.8 aus Z6- geschnitten mit  S8- geschnitten mit Q6- =  {2}

Betrachtet man alle Möglichkeiten gleichzeitig, dann kann man wieder mit den Feldern beginnen, die keine Wahl haben, und zugleich muss man diese Ziffern aus der Menge der möglichen Ziffern streichen, da sie ja nur 1x in einer Zeile vorkommen dürfen. Man erhält damit:

X6.2 aus Z6- geschnitten mit  S2- geschnitten mit Q4- =  {3}<-- Fixiert 1
X6.3 aus Z6- geschnitten mit  S3- geschnitten mit Q4- =  {3,7}
X6.4 aus Z6- geschnitten mit  S4- geschnitten mit Q5- =  {8}<-- Fixiert 1
X6.6 aus Z6- geschnitten mit  S6- geschnitten mit Q5- =  {6}<-- Fixiert 1
X6.7 aus Z6- geschnitten mit  S7- geschnitten mit Q6- =  {1,2}
X6.8 aus Z6- geschnitten mit  S8- geschnitten mit Q6- =  {2}<-- Fixiert 1

Nach Eliminierung der ersten Auswahl:

X6.2 aus Z6- geschnitten mit  S2- geschnitten mit Q4- =  {3}<-- Fixiert 1
X6.3 aus Z6- geschnitten mit  S3- geschnitten mit Q4- =  {7}
X6.4 aus Z6- geschnitten mit  S4- geschnitten mit Q5- =  {8}<-- Fixiert 1
X6.6 aus Z6- geschnitten mit  S6- geschnitten mit Q5- =  {6}<-- Fixiert 1
X6.7 aus Z6- geschnitten mit  S7- geschnitten mit Q6- =  {1}
X6.8 aus Z6- geschnitten mit  S8- geschnitten mit Q6- =  {2}<-- Fixiert 1

Es bleiben nur einzelne Ziffern zur Auswahl übrig. Die Zeile erweist sich als deterministisch.

Für Zeile Z6 gilt: free(Z6) = 1.

Damit erhalten wir:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    6.    2.    5.    3.    9.    4.    8.    7. !
!   8.    4.    9.    7.    1.    2.    6.    5.    3. !
!   5.    3.    7.    8.    4.    6.    1.    2.    9. !
!   0.    0.    0.    1.    8.    7.    0.    0.    0. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !




Zeile 7
In der siebten Zeile gibt es freie Zellen in den  Spalten  S1, S2,S3,  S7, S8, S9.
Wir erhalten:

Z7- =  { 2,    3,    4,    5,    6,    9}


S1- =  {4}
S2- =  {9}
S3- =  {1,3}
S7- =  {2,9}
S8- =  {6}
S9- =  {5}

Q7- = {  1,    3,    4,    9 }
Q9- = { 2,    5,    6,    9}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X7.1 aus Z7- geschnitten mit  S1- geschnitten mit Q7- =  {4}
X7.2 aus Z7- geschnitten mit  S2- geschnitten mit Q7- =  {9}
X7.3 aus Z7- geschnitten mit  S3- geschnitten mit Q7- =  {3}
X7.7 aus Z7- geschnitten mit  S7- geschnitten mit Q9- =  {2,9}
X7.8 aus Z7- geschnitten mit  S8- geschnitten mit Q9- =  {6}
X7.9 aus Z7- geschnitten mit  S9- geschnitten mit Q9- =  {5}

Betrachtet man alle Möglichkeiten gleichzeitig, dann kann man wieder mit den Feldern beginnen, die keine Wahl haben, und zugleich muss man diese Ziffern aus der Menge der möglichen Ziffern streichen, da sie ja nur 1x in einer Zeile vorkommen dürfen. Man erhält damit:

X7.1 aus Z7- geschnitten mit  S1- geschnitten mit Q7- =  {4}<-- Fixiert 1
X7.2 aus Z7- geschnitten mit  S2- geschnitten mit Q7- =  {9}<-- Fixiert 1
X7.3 aus Z7- geschnitten mit  S3- geschnitten mit Q7- =  {3}<-- Fixiert 1
X7.7 aus Z7- geschnitten mit  S7- geschnitten mit Q9- =  {2}
X7.8 aus Z7- geschnitten mit  S8- geschnitten mit Q9- =  {6}<-- Fixiert 1
X7.9 aus Z7- geschnitten mit  S9- geschnitten mit Q9- =  {5}<-- Fixiert 1

Nach dieser ersten Dixierung ist die Zelle X7.7 auch auf eine Ziffer alleine festgelegt. Auch di3ese Zeile ist also determiistisch:
Für Zeile Z7 gilt: free(Z7) = 1.

Als Ergebnis erhalten wird:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    6.    2.    5.    3.    9.    4.    8.    7. !
!   8.    4.    9.    7.    1.    2.    6.    5.    3. !
!   5.    3.    7.    8.    4.    6.    1.    2.    9. !
!   4.    9.    3.    1.    8.    7.    2.    6.    5. !
!   6.    8.    5.    0.    2.    0.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !


Zeile 8
In der achten  Zeile gibt es freie Zellen in den  Spalten  S4 und S6.
Wir erhalten:

Z8- =  {3,9}

S4- =  {9}
S6- =  {3}

Q8- = {3,9 }

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X8.4 aus Z8- geschnitten mit  S4- geschnitten mit Q8- =  {9}
X8.6 aus Z8- geschnitten mit  S6- geschnitten mit Q8- =  {3}

Auch diese Zeile ist deterministisch.
Für Zeile Z8 gilt: free(Z8) = 1.

Wir erhalten:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    6.    2.    5.    3.    9.    4.    8.    7. !
!   8.    4.    9.    7.    1.    2.    6.    5.    3. !
!   5.    3.    7.    8.    4.    6.    1.    2.    9. !
!   4.    9.    3.    1.    8.    7.    2.    6.    5. !
!   6.    8.    5.    9.    2.    3.    7.    4.    1. !
!   7.    2.    0.    4.    6.    5.    0.    3.    8. !



Zeile 9
In der neunten Zeile gibt es freie Zellen in den  Spalten   S3 und S7.
Wir erhalten:

Z9- =  {1,9 }


S3- =  {1}
S7- =  {9}

Q7- = {1 }
Q9- = {9 }

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X9.3 aus Z7- geschnitten mit  S3- geschnitten mit Q7- =  {1}
X9.7 aus Z7- geschnitten mit  S7- geschnitten mit Q9- =  {9}

Auch diese Zeile ist deterministisch.
Für Zeile Z9 gilt: free(Z9) = 1.

Wir erhalten als Endergebnis:

!   3.    5.    4.    6.    9.    1.    8.    7.    2. !
!   2.    1.    6.    3.    7.    8.    5.    9.    4. !
!   9.    7.    8.    2.    5.    4.    3.    1.    6. !
!   1.    6.    2.    5.    3.    9.    4.    8.    7. !
!   8.    4.    9.    7.    1.    2.    6.    5.    3. !
!   5.    3.    7.    8.    4.    6.    1.    2.    9. !
!   4.    9.    3.    1.    8.    7.    2.    6.    5. !
!   6.    8.    5.    9.    2.    3.    7.    4.    1. !
!   7.    2.    1.    4.    6.    5.    9.    3.    8. !

Entsprechend der bisherigen Formel für den Schwierigkeitsgrad würden wir für dieses Beispiel bekommen:

D(M) = free(Z1) * .... * free(Z9) = PROD(i=1:9)free(Zi)
= free(Z1) * .... * free(Z9)
= 1 * 2 * 1 * 1 * 1  * 1 * 1 * 1  * 1 = 2

Dieses Beispiel scheint also besonders einfach gewesen zu sein.

Idee zu einem Sudoku-Algorithmus

So einfach das erste Beispiel war, unterstützt es doch die Idee zu einem ersten Sudoku-Algorithmus. Folgende Schritte legen sich nahe:

  1. Eingabe einer 9x9 Matrix mit vorgegebenen Ziffern; Verteilung entsprechend Sudoku-Regeln.

  2. Berechnung der Komplementmengen für die Zeilen (Z-), für die Spalten (S-), sowie wie für 3er-Quadranten (Q-).

  3. Zeilenweise: Berechne für jedes Element der Zeile die Schnittmenge entsprechend Zi- geschnitten Si- geschnitten Qi- indem man die  Schnittmengen nach Mächtigkeit ordnet:  kleinste Mächtigkeit vor grösserer Mächtigkeit; setze eindeutige Werte als fixiert; lösche fixierte Werte aus Lösungsmenge. 

  4. Falls für eine Zele mehr als 1 Option übrig bleibt, ist der Freiheitsgrad grösser als 1. In diesem Fall muss in Rechnung gestellt werden, dass eine aktuelle Auswahl zu einem späteren Zeitpunkt ('backtracking') revidiert werden muss. Daher Erweiterung der Lösungsmenge für Zeile Zi- um die Zeile Zi+1-. Verrechnung der Spalten  und Unterquadrate aus den  Zeilen Zi- + Zi+1-. (Sinnvoll für Zeilen mit den gleichen Unterquadraten!).Gehe zu (3)   Hinweis: Jede Zeile benötigt mindestens so viele verschiedene Ziffern, wie verschiedene Felder vorkommen!

  5. Wenn keine Lösung  möglich ist,dann Abbruch mit Fehlermeldung 'NO SOLUTION'.

  6. Falls Lösung möglich ist und noch eine Zeile frei, dann gehe zur nächsten Zeile und folge weiter mit (3)

  7. Falls Lösung möglich ist und keine mehr Zeile frei, dann Meldung 'SUCCESS'
 

Beispiel Nr.2 (Sumo)

 Hier das Sudokuproblem:

!   0.    6.    3.    0.    0.    0.    8.    4.    0. !
!   5.    0.    0.    3.    0.    8.    0.    0.    9. !
!   0.    7.    0.    0.    2.    0.    0.    6.    0. !
!   0.    0.    7.    0.    0.    0.    3.    0.    0. !
!   0.    3.    0.    0.    0.    0.    0.    2.    0. !
!   0.    0.    2.    0.    0.    0.    9.    0.    0. !
!   0.    1.    0.    0.    5.    0.    0.    9.    0. !
!   7.    0.    0.    4.    0.    9.    0.    0.    8. !
!   0.    8.    9.    0.    0.    0.    7.    1.    0. !


Zeile 1
In der ersten Zeile gibt es freie Zellen in den  Spalten S1,S4,S5, S6,S9.
Wir erhalten:

Z1- =  {1,2,5,7,9}

S1- =  {1,2,3,4,6,8,9}
S4- =  {1,2,5,6,7,8,9}
S5- =  {1,3,4,6,7,8,9}
S6- =  {1,2,3,4,5,6,7}
S9- =  {1,2,3,4,5,6,7}

Q1- = {1,2,4,8,9    }
Q2- = {1,4,5,6,7,9}
Q3- = {1,2,3,5,7}

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:

X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,2,9}
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,7,9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,7,9}
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {1,5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1,2,5,7}

Betrachtet man alle Möglichkeiten gleichzeitig, dann kann man mit den Feldern beginnen, die keine Wahl haben, und zugleich muss man diese Ziffern aus der Menge der möglichen Ziffern streichen, da sie ja nur 1x in einer Zeile vorkommen dürfen.

Im vorliegenden Fall gilt für die Freiheitsgrade:
free_extern(Z1-):  3 * 4 * 3 * 3 * 4 = 432

Um free_intern zu ermitteln betrachtet man die folgende Lösungsmenge:

(i)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1}<--(1), nicht (2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {7}<--(7) nicht (9)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {2}

(ii)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1}<--(1), nicht (2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5}<--(5) nicht (7)
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {9}<--(9) nicht (7)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {2}

(iii)!!!Nicht!!!

X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1}<--(1), nicht (2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5}<--(7) nicht (5) !!!Geht nicht!!!
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {9}<--(9) nicht (7)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {2,5}

Zwischenergebnis: Bei Wahl von (1), nicht (2,9) in Spalte S1- ergeben sich insgesamt 2 Möglichkeiten.

(i)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,9}<--(2) nicht (1,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,7,9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,7,9}
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {1,5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1,5,7}

(ii)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,9}<--(2) nicht (1,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5,7,9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {7,9}<--(1) nicht (7,9)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {5,7}

(iii)!!!
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,9}<--(2) nicht (1,9)!!!
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {7,9}<--(1) nicht (7,9)!!!
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5}<--(5) nicht (7) !!!Geht nicht!!!
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {7}

(iii)!!!
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1}<--(2) nicht (1,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {9}<--(1) nicht (7,9)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {7}<--(7) nicht (5)!!!
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {5}


(iii)!!!
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,9}<--(2) nicht (1,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5,9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,9}<--(7) aus (1,7,9)!!!
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {5}


(iii)!!!
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,9}<--(2) nicht (1,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5,7}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {9}<--(9) nicht (1,7)!!!
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {5,7}


Zwischenergebnis: Die Wahl von (2) aus (1,2,9) in Spalte S1 führt zu keiner Lösung

(i)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {9}<--(9) aus (1,2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,7}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,7}
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {1,5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1,2,5,7}


(ii)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {9}<--(9) aus (1,2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5,7}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1}<--(1) aus (1,7)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {2,5,7}


(iii)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {9}<--(9) aus (1,2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {5}<--(5) aus (5,7)
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1}<--(1) aus (1,7)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {2}

(iv)
X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {9}<--(9) aus (1,2,9)
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {7}<--(7) aus (5,7)
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1}<--(1) aus (1,7)
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {2}

Zwischenergebnis: Die Wahl von (9) aus (1,2,9) aus Spalte S1 führt zu 4 Möglichkeiten.

Also: free_intern(Z1-) = 2 * 4 = 8

Generell gilt also, die Freiheitsgrade sind grösser als 1. Damit sagt der Algorithmus, dass man die Lösungsmenge um eine Zeile erweitern sollte, also:


Z1- =  {1,2,5,7,9}

S1- =  {1,2,3,4,6,8,9}
S4- =  {1,2,5,6,7,8,9}
S5- =  {1,3,4,6,7,8,9}
S6- =  {1,2,3,4,5,6,7}
S9- =  {1,2,3,4,5,6,7}

Q1- = {1,2,4,8,9    }
Q2- = {1,4,5,6,7,9}
Q3- = {1,2,3,5,7}

erweitert um:

Z2- =  {1,2,4,6,7}

S2- =  {2,4,5,9}
S3- =  {1,4,5,6,8}
S5- =  {1,3,4,6,7,8,9}
S7- =  {1,2,4,5,6}
S8- =  {3,5,7,8}

Q1- = {1,2,4,8,9  }
Q2- = {1,4,5,6,7,9}
Q3- = {1,2,3,5,7}

Man kann erkennen, dass die Spalte S5 beiden Zeilen gemeinsam ist, ebenso alle drei Unterquadrate. Daraus kann man schliessen, dass sich die Menge vrfügbarer Optionen einschränkt:

Allen potentiellen Mengen gemeinsam sind die folgenden Ziffern:


X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,2,9}
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,7,9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,7,9}
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {1,5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1,2,5,7}

erweitert um:

X2.2 aus Z2- geschnitten mit  S2- geschnitten mit Q1- =  {2,4}
X2.3 aus Z2- geschnitten mit  S3- geschnitten mit Q1- =  {1,4}
X2.5 aus Z2- geschnitten mit  S5- geschnitten mit Q2- =  {1,4,6,7}
X2.7 aus Z2- geschnitten mit  S7- geschnitten mit Q3- =  {1,2}
X2.8 aus Z2- geschnitten mit  S8- geschnitten mit Q3- =  {7}

Lösungsansatz:

X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,2,9}
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,9}<--(2) 7 weg
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,9}<--(2) 7 weg
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {1,5}<--(2) 7 weg
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1,2,5}<--(2) 7 weg

erweitert um:

X2.2 aus Z2- geschnitten mit  S2- geschnitten mit Q1- =  {2,4}
X2.3 aus Z2- geschnitten mit  S3- geschnitten mit Q1- =  {1,4}
X2.5 aus Z2- geschnitten mit  S5- geschnitten mit Q2- =  {1,4,6}
X2.7 aus Z2- geschnitten mit  S7- geschnitten mit Q3- =  {1,2}
X2.8 aus Z2- geschnitten mit  S8- geschnitten mit Q3- =  {7}<--(1) betrifft Q3 und Z1 und S8

Immer noch zuviele Freiheitsgrade. Hinzunahme von Z3:



Z1- =  {1,2,5,7,9}

S1- =  {1,2,3,4,6,8,9}
S4- =  {1,2,5,6,7,8,9}
S5- =  {1,3,4,6,7,8,9}
S6- =  {1,2,3,4,5,6,7}
S9- =  {1,2,3,4,5,6,7}

Q1- = {1,2,4,8,9    }
Q2- = {1,4,5,6,7,9}
Q3- = {1,2,3,5,7}

erweitert um:

Z2- =  {1,2,4,6,7}

S2- =  {2,4,5,9}
S3- =  {1,4,5,6,8}
S5- =  {1,3,4,6,7,8,9}
S7- =  {1,2,4,5,6}
S8- =  {3,5,7,8}

Q1- = {1,2,4,8,9  }
Q2- = {1,4,5,6,7,9}
Q3- = {1,2,3,5,7}

erweitert um:


Z3- =  {1,3,4,5,8,9}

S1- =  {1,2,3,4,6,8,9}
S3- =  {1,4,5,6,8}
S4- =  {1,2,5,6,7,8,9}
S6- =  {1,2,3,4,5,6,7}
S7- =  {1,2,4,5,6}
S8- =  {3,5,7,8}

Q1- = {1,2,4,8,9  }
Q2- = {1,4,5,6,7,9}
Q3- = {1,2,3,5,7}


X1.1 aus Z1- geschnitten mit  S1- geschnitten mit Q1- =  {1,2,9}
X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,7,9}
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {1,7,9}
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {1,5,7}
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1,2,5,7}
(5 aus 5)
erweitert um:

X2.2 aus Z2- geschnitten mit  S2- geschnitten mit Q1- =  {2,4}
X2.3 aus Z2- geschnitten mit  S3- geschnitten mit Q1- =  {1,4}
X2.5 aus Z2- geschnitten mit  S5- geschnitten mit Q2- =  {1,4,6,7}
X2.7 aus Z2- geschnitten mit  S7- geschnitten mit Q3- =  {1,2}
X2.8 aus Z2- geschnitten mit  S8- geschnitten mit Q3- =  {7}
(5 aus 5)
erweitert um:

X3.1 aus Z3- geschnitten mit  S1- geschnitten mit Q1- =  {1,4,8,9}
X3.3 aus Z3- geschnitten mit  S3- geschnitten mit Q1- =  {1,4,8}
X3.4 aus Z3- geschnitten mit  S4- geschnitten mit Q2- =  {1,5,9}
X3.6 aus Z3- geschnitten mit  S6- geschnitten mit Q2- =  {1,4,5}
X3.7 aus Z3- geschnitten mit  S7- geschnitten mit Q3- =  {1,5}
X3.9 aus Z3- geschnitten mit  S9- geschnitten mit Q3- =  {1,3,5}
(6 aus 6)

Daraus kann man folgenden Lösungsansatz entwickeln:



X1.4 aus Z1- geschnitten mit  S4- geschnitten mit Q2- =  {7}<--18:(-1)/*Zeile*/<--22:(-5)/*Zeile*/<--23:(+7)/*Geringste Reichweite*/
X1.5 aus Z1- geschnitten mit  S5- geschnitten mit Q2- =  {9}<--24:(-7)/*Zeile*/
X1.6 aus Z1- geschnitten mit  S6- geschnitten mit Q2- =  {5}<--21:(+5)/*Geringste Reichweite*/
X1.9 aus Z1- geschnitten mit  S9- geschnitten mit Q3- =  {1}<--2:(-7)/*Quadrat*/<--4:(-2)/*Quadrat*/<--16:(-5)/*Quadrat*/<--17:(+1)/*Erzwungen*/
-----------------------------
X2.2 aus Z2- geschnitten mit  S2- geschnitten mit Q1- =  {4}<--4:(-2)/Zeile*/<--5:(+4)/*Erzwungen*/
X2.3 aus Z2- geschnitten mit  S3- geschnitten mit Q1- =  {1}<--6:(-4)/*Zeile*/<--7:(+1)/*Erzwungen*/
X2.5 aus Z2- geschnitten mit  S5- geschnitten mit Q2- =  {6}<--2:(-7)/*Zeile*/<--6:(-4)<--8:(-1)/*Zeile*/
X2.7 aus Z2- geschnitten mit  S7- geschnitten mit Q3- =  {2}<--3:(+2)/*Geringste Reichweite*/
X2.8 aus Z2- geschnitten mit  S8- geschnitten mit Q3- =  {7}<--1:(+7) /*Erzwungen*/
--------------------------
X3.1 aus Z3- geschnitten mit  S1- geschnitten mit Q1- =  {9}<--6:(-4)/*Quadrat*/<--8:(-1)/*Quadrat*/<--10:(-8)/*Zeile*/<--11:(+9)/*Erzwungen*/
X3.3 aus Z3- geschnitten mit  S3- geschnitten mit Q1- =  {8}<--6:(-4)/*Quadrat*/<--8:(-1)/*Quadrat*/<--9:(+8)/*Erzwungen*/
X3.4 aus Z3- geschnitten mit  S4- geschnitten mit Q2- =  {1}<--12:(-9)/*Zeile*/<--16:(-5)/*Zeile*/<--19:(+1)/*Erzwungen*/
X3.6 aus Z3- geschnitten mit  S6- geschnitten mit Q2- =  {4}<--16:(-5)/*Zeile*/<--20:(-1)/*Zeile*/
X3.7 aus Z3- geschnitten mit  S7- geschnitten mit Q3- =  {5}<--15:(+5)/*Geringste Reichweite*/
X3.9 aus Z3- geschnitten mit  S9- geschnitten mit Q3- =  {3}<--16:(-5)/*Zeile*/<--18:(-1)/*Quadrat*/

Kommentar:
  1. Entsprechend der Mächtigkeit werden Einsetzungen durch ||=1 /*Erzwungen*/
  2. Entsprechend der Koppelungen wirken sich Einsetzungen entlang der setzenden Zeile, des setzenden Quadrates wie auch der setzenden Spalte fort. /*Zeile*/, /*Quadrat*/, /*Spalte*/
  3. Bei || >1 wählt man jene Option, die die geringste Reichweite hat. Dabei muss man neben Zeile auch Quadrat und Spalte berücksichtigen. Andere Zeilen sollten möglichst nicht tangiert werden.  /*Geringste Reichweite */
  4. Dieses Beispiel zeigt, dass man von vornherein mit Lösungsblöcken arbeiten sollte: entweder alle drei Zeilen, die drei Unterquadrate gemeinsam haben oder alle drei Spalten mit gemeinsamen Unterquadraten. Mathematischer Beweis muss noch aufgeschrieben werden.

Ergebnis Zeilen Z1 - Z3:

!   2.    6.    3.    7.    9.    5.    8.    4.    1. !
!   5.    4.    1.    3.    6.    8.    2.    7.    9. !
!   9.    7.    8.    1.    2.    4.    5.    6.    3. !
!   0.    0.    7.    0.    0.    0.    3.    0.    0. !
!   0.    3.    0.    0.    0.    0.    0.    2.    0. !
!   0.    0.    2.    0.    0.    0.    9.    0.    0. !
!   0.    1.    0.    0.    5.    0.    0.    9.    0. !
!   7.    0.    0.    4.    0.    9.    0.    0.    8. !
!   0.    8.    9.    0.    0.    0.    7.    1.    0. !


Hier die Fortsetzung des Beispiels

Wir nehmen jetzt sofort die nächsten 3 Zeilen Z4-Z6 als ein 3Band B2 und wenden die vorausgehenden Überlegungen darauf an.


!   2.    6.    3.    7.    9.    5.    8.    4.    1. !
!   5.    4.    1.    3.    6.    8.    2.    7.    9. !
!   9.    7.    8.    1.    2.    4.    5.    6.    3. !
!   0.    0.    7.    0.    0.    0.    3.    0.    0. !
!   0.    3.    0.    0.    0.    0.    0.    2.    0. !
!   0.    0.    2.    0.    0.    0.    9.    0.    0. !
!   0.    1.    0.    0.    5.    0.    0.    9.    0. !
!   7.    0.    0.    4.    0.    9.    0.    0.    8. !
!   0.    8.    9.    0.    0.    0.    7.    1.    0. !

In Zeile Z4 gibt es Lösungskandidaten in den Spalten {S1, S2, S4, S5, S6, S8, S9} = cand(Z4) = C1; |C1| = 7

In Zeile Z5 gibt es Lösungskandidaten in den Spalten {S1, S3, S4, S5, S6, S7, S9} = cand(Z5) = C2; |C2| = 7

In Zeile Z6 gibt es Lösungskandidaten in den Spalten {S1, S2, S4, S5, S6, S8, S9} = cand(Z6) = C3; |C3| = 7

Dies bedeutet, dass in jeder Zeile des 3Bandes B2 7 Lösungskandidaten bedient werden müssen. Daraus folgt, dass die jeweiligen Lösungsmengen (Z- geschnitten S- geschnitten Q-) entsprechend der Ungleichung |C| < |(Z- geschnitten S- geschnitten Q-)| mindestens 7 Werte anbieten müssen.  Für jede dann folgende Operation gilt dann, dass ihr Ergebnis die Lösungsbedingungen für die beiden anderen Zeilen des 3Bandes nicht zerstören dürfen. Um dieses Ziel umzusetzen, steht die Strategie zur Verfügung, die verfügbaren Operationen nach ihrem Koordinierungsgrad (KG)  anzuwenden. Am geeignetsten ist KG=0. Wenn eine solche Operation nicht zur Verfügung steht, dann eine Operation mit KG1, dann KG2. Wenn damit eine Lösung nicht konstruiert werden kann, dann gibt es keine Lösung, da diese Operationen den gesamt Möglichkeitsraum abdecken.

Aufspannen des potentiellen Lösungsraumes

Z4- = {1,2,4,5,6,8,9}

S1- = {1,3,4,6,8}
S2- = {2,5,9}
S4- = {2,5,6,8,9}
S5- = {1,3,4,7,8}
S6- = {1,2,3,6,7}
S8- = {3,5,8}
S9- = {2,4,5,6,7}

Q4- = {1,4,5,6,8,9}
Q5- = {1,2,3,4,5,6,7,8,9}
Q6- = {1,4,5,6,7,8}

Z5- = {1,4,5,6,7,8,9}

S1- = {}
S3- = {4,5,6}
S4- = {2,5,6,8,9}
S5- = {1,3,4,7,8}
S6- = {1,2,3,6,7}
S7- = {1,4,6}
S9- = {2,4,5,6,7}

Q4- = {1,4,5,6,8,9}
Q5- = {1,2,3,4,5,6,7,8,9}
Q6- = {1,4,5,6,7,8}

Z6- = {1,3,4,5,6,7,8}

S1- = {1,3,4,6,8}
S2- = {2,5,9}
S4- = {2,5,6,8,9}
S5- = {1,3,4,7,8}
S6- = {1,2,3,6,7}
S8- = {3,5,8}
S9- = {2,4,5,6,7}

Q4- = {1,4,5,6,8,9}
Q5- = {1,2,3,4,5,6,7,8,9}
Q6- = {1,4,5,6,7,8}

Resultierende Lösungsanforderungen:

--------------------------
X4.1 aus Z4- geschnitten mit  S1- geschnitten mit Q4- =  {1,4,6,8}
X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q4- =  {5,9}
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q5- =  {2,5,6,8,9}
X4.5 aus Z4- geschnitten mit  S5- geschnitten mit Q5- =  {1,4,8}
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q5- =  {1,2,6}
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q6- =  {1,4,6}
X4.9 aus Z4- geschnitten mit  S9- geschnitten mit Q6- =  {4,5,6}
-------------------------------------------------------------------
Wegen |cand(Z4)| = 7 werden mindestens 7 Werte aus Xi.j in (Z- geschnitten S- geschnitten Q-) benötigt. Aus der Vereinigung aller Xi.j bekommt man: |{1,2,4,5,6,8,9}| = 7. Damit ist die Minimalforderung erfüllt.
---------------------------------------------------------------------
X5.1 aus Z5- geschnitten mit  S1- geschnitten mit Q4- =  {1,4,6,8}
X5.3 aus Z5- geschnitten mit  S3- geschnitten mit Q4- =  {4,5,6}
X5.4 aus Z5- geschnitten mit  S4- geschnitten mit Q5- =  {5,6,8,9}
X5.5 aus Z5- geschnitten mit  S5- geschnitten mit Q5- =  {1,4,7,8}
X5.6 aus Z5- geschnitten mit  S6- geschnitten mit Q5- =  {1,6,7}
X5.7 aus Z5- geschnitten mit  S7- geschnitten mit Q6- =  {1,4,6}
X5.9 aus Z5- geschnitten mit  S9- geschnitten mit Q6- =  {4,5,6,7}
-------------------------------------------------------------------
Wegen |cand(Z5)| = 7 werden mindestens 7 Werte aus Xi.j in (Z- geschnitten S- geschnitten Q-) benötigt. Aus der Vereinigung aller Xi.j bekommt man: |{1,4,5,6,7,8,9}| = 7. Damit ist die Minimalforderung erfüllt.
---------------------------------------------------------------------
X6.1 aus Z6- geschnitten mit  S1- geschnitten mit Q4- =  {1,4,6,8}
X6.2 aus Z6- geschnitten mit  S2- geschnitten mit Q4- =  {5}
X6.4 aus Z6- geschnitten mit  S4- geschnitten mit Q5- =  {5,6,8}
X6.5 aus Z6- geschnitten mit  S5- geschnitten mit Q5- =  {1,3,4,7,8}
X6.6 aus Z6- geschnitten mit  S6- geschnitten mit Q5- =  {1,3,6,7}
X6.8 aus Z6- geschnitten mit  S8- geschnitten mit Q6- =  {5,8}
X6.9 aus Z6- geschnitten mit  S9- geschnitten mit Q6- =  {4,5,6,7}
-------------------------------------------------------------------
Wegen |cand(Z6)| = 7 werden mindestens 7 Werte aus Xi.j in (Z- geschnitten S- geschnitten Q-) benötigt. Aus der Vereinigung aller Xi.j bekommt man: |{1,3,4,5,6,7,8}| = 7. Damit ist die Minimalforderung erfüllt.
---------------------------------------------------------------------

Konstruktion einer Lösung mittels der Strategie:


(i) Kandidaten geordnet nach kleinster Mächtigkeit; kleinste Mächtigkeit höchste Priorität
(ii) Aktionen geordnet nach Koordinierungsgrad; kleinste Koordinierung mit höchster Priorität; Innerhalb der gleichen Priorität nach Anzahl der betroffenen Elemente

--------------------------

Ordnen nach Mächtigkeit:

X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q4- =  {5,9}
X4.5 aus Z4- geschnitten mit  S5- geschnitten mit Q5- =  {1,4,8}
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q5- =  {1,2,6}
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q6- =  {1,4,6}
X4.9 aus Z4- geschnitten mit  S9- geschnitten mit Q6- =  {4,5,6}
X4.1 aus Z4- geschnitten mit  S1- geschnitten mit Q4- =  {1,4,6,8}
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q5- =  {2,5,6,8,9}
-------------------------------------------------------------------
Wegen |cand(Z4)| = 7 werden mindestens 7 Werte aus Xi.j in (Z- geschnitten S- geschnitten Q-) benötigt. Aus der Vereinigung aller Xi.j bekommt man: |{1,2,4,5,6,8,9}| = 7. Damit ist die Minimalforderung erfüllt.
---------------------------------------------------------------------
X5.3 aus Z5- geschnitten mit  S3- geschnitten mit Q4- =  {4,5,6}
X5.6 aus Z5- geschnitten mit  S6- geschnitten mit Q5- =  {1,6,7}
X5.7 aus Z5- geschnitten mit  S7- geschnitten mit Q6- =  {1,4,6}
X5.1 aus Z5- geschnitten mit  S1- geschnitten mit Q4- =  {1,4,6,8}
X5.4 aus Z5- geschnitten mit  S4- geschnitten mit Q5- =  {5,6,8,9}
X5.5 aus Z5- geschnitten mit  S5- geschnitten mit Q5- =  {1,4,7,8}
X5.9 aus Z5- geschnitten mit  S9- geschnitten mit Q6- =  {4,5,6,7}
-------------------------------------------------------------------
Wegen |cand(Z5)| = 7 werden mindestens 7 Werte aus Xi.j in (Z- geschnitten S- geschnitten Q-) benötigt. Aus der Vereinigung aller Xi.j bekommt man: |{1,4,5,6,7,8,9}| = 7. Damit ist die Minimalforderung erfüllt.
---------------------------------------------------------------------
X6.2 aus Z6- geschnitten mit  S2- geschnitten mit Q4- =  {5}
X6.8 aus Z6- geschnitten mit  S8- geschnitten mit Q6- =  {5,8}
X6.4 aus Z6- geschnitten mit  S4- geschnitten mit Q5- =  {5,6,8}
X6.1 aus Z6- geschnitten mit  S1- geschnitten mit Q4- =  {1,4,6,8}
X6.6 aus Z6- geschnitten mit  S6- geschnitten mit Q5- =  {1,3,6,7}
X6.9 aus Z6- geschnitten mit  S9- geschnitten mit Q3- =  {4,5,6,7}
X6.5 aus Z6- geschnitten mit  S5- geschnitten mit Q5- =  {1,3,4,7,8}
-------------------------------------------------------------------
Wegen |cand(Z6)| = 7 werden mindestens 7 Werte aus Xi.j in (Z- geschnitten S- geschnitten Q-) benötigt. Aus der Vereinigung aller Xi.j bekommt man: |{1,3,4,5,6,7,8}| = 7. Damit ist die Minimalforderung erfüllt.
---------------------------------------------------------------------

Anwendung der Operationen

Fortlaufende Adjustierung, wenn Mächtigkeit sich ändert

--------------------------

X4.2 aus Z4- geschnitten mit  S2- geschnitten mit Q4- =  {9}<--2:(-5)/*Wegen Q*/<--29:(+9)/*Erzwungen*/
X4.5 aus Z4- geschnitten mit  S5- geschnitten mit Q5- =  {1}<--12:(-4)/*Wegen S*/<--18:(-8)/*Wegen Z*/<--31:(+1)/*Erzwungen*/
X4.6 aus Z4- geschnitten mit  S6- geschnitten mit Q5- =  {2}<--6:(-6)/*Wegen Q*/<--32:(-1)/*Wegen Q*/<--33:(+2)/*Erzwungen*/
X4.8 aus Z4- geschnitten mit  S8- geschnitten mit Q6- =  {4}<--22:(-1)/*Wegen Q*/<--37:(+4)/*Wegen KG*/
X4.9 aus Z4- geschnitten mit  S9- geschnitten mit Q6- =  {6}<--36:(-5)/*Wegen Z*/<--38:(-4)/*Wegen Q*/
X4.1 aus Z4- geschnitten mit  S1- geschnitten mit Q4- =  {8}<--14:(-1)/*Wegen Q*/<--16:(-4)/*Wegen Q*/<--17:(+8)/*Wegen KG*/
X4.4 aus Z4- geschnitten mit  S4- geschnitten mit Q5- =  {5}<--6:(-6)/*Wegen Q*/<--18:(-8)/*Wegen Z*/<--28:(-9)/*Wegen Q*/<--34:(-2)/*Wegen Q*/<--35:(+5)/*Erzwungen*/
-------------------------------------------------------------------
X5.3 aus Z5- geschnitten mit  S3- geschnitten mit Q4- =  {4}<--2:(-5)/*Wegen Q*/<--15:(+4)/*Wegen KG*/
X5.6 aus Z5- geschnitten mit  S6- geschnitten mit Q5- =  {7}<--20:(-6)/*Zeile*/<--22:(-1)/*Wegen Z*/<--23:(+7)/*Erzwungen*/
X5.7 aus Z5- geschnitten mit  S7- geschnitten mit Q6- =  {1}<--16:(-4)/*Wegen Z*/<--20:(-6)/*Zeile*/<--21:(+1)/*Erzwungen*/
X5.1 aus Z5- geschnitten mit  S1- geschnitten mit Q4- =  {6}<--14:(-1)/*Wegen Q*/<--16:(-4)/*Wegen Q*/<--18:(-8)/*Wegen Q*/<--19:(+6)/*Erzwungen*/
X5.4 aus Z5- geschnitten mit  S4- geschnitten mit Q5- =  {9}<--6:(-6)/*Wegen Z*/<--26:(-8)/*Wegen Z*/<--27:(+9)/*Erzwungen*/
X5.5 aus Z5- geschnitten mit  S5- geschnitten mit Q5- =  {8}<--12:(-4)/*Wegen Q*/<--22:(-1)/*Wegen Z*/<--24:(-7)/*Wegen Z*/<--25:(+8)/*Erzwungen*/
X5.9 aus Z5- geschnitten mit  S9- geschnitten mit Q6- =  {5}<--8:(-7)/*Wegen Q*/<--16:(-4)/*Wegen Q*/<--20:(-6)/*Zeile*/
-------------------------------------------------------------------
X6.2 aus Z6- geschnitten mit  S2- geschnitten mit Q4- =  {5}<--1:(+5)/*Erzwungen*/
X6.8 aus Z6- geschnitten mit  S8- geschnitten mit Q6- =  {8}<--2:(-5)/*Wegen Z*/<--3:(+8)/*Erzwungen*/
X6.4 aus Z6- geschnitten mit  S4- geschnitten mit Q5- =  {6}<--2:(-5)/*Wegen Z*/<--4:(-8)/*Wegen Z*/<--5:(+6)/*Erzwungen*/
X6.1 aus Z6- geschnitten mit  S1- geschnitten mit Q4- =  {1}<--4:(-8)/*Wegen Z*/<--6:(-6)/*Wegen Z*/<--12:(-4)/*Wegen Z*/<--13:(+1)/*Erzwungen*/
X6.6 aus Z6- geschnitten mit  S6- geschnitten mit Q5- =  {3}<--6:(-6)/*Wegen Z*/<--8:(-7)/*Wegen Z*/<--9:(+3)/*Wegen KG*/
X6.9 aus Z6- geschnitten mit  S9- geschnitten mit Q6- =  {7}<--2:(-5)/*Wegen Z*/<--6:(-6)/*Wegen Z*/<--7:(+7)/*Wegen KG*/
X6.5 aus Z6- geschnitten mit  S5- geschnitten mit Q5- =  {4}<--4:(-8)/*Wegen Z*/<--8:(-7)/*Wegen Z*/<--10:(-3)/*Wegen Z*/<--11:(+4)/*Wegen KG*/
-------------------------------------------------------------------


Damit erhalten wir folgendes Zwischenergebnis:

!   2.    6.    3.    7.    9.    5.    8.    4.    1. !
!   5.    4.    1.    3.    6.    8.    2.    7.    9. !
!   9.    7.    8.    1.    2.    4.    5.    6.    3. !
!   8.    9.    7.    5.    1.    2.    3.    4.    6. !
!   6.    3.    4.    9.    8.    7.    1.    2.    5. !
!   1.    5.    2.    6.    4.    3.    9.    8.    7. !
!   0.    1.    0.    0.    5.    0.    0.    9.    0. !
!   7.    0.    0.    4.    0.    9.    0.    0.    8. !
!   0.    8.    9.    0.    0.    0.    7.    1.    0. !

Und so weiter...

Wir verlassen jetzt dieses Beispiel und wenden uns einem noch schwereren Fall zu, ein sogenanntes Kamikaze-Sudoku (Laut der Zeitschrift Stern),