Spalte (column)---> Zeile (row) | | V |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
1 | Q1 | Q1 | Q1 | Q2 | Q2 | Q2 | Q3 | Q3 | Q3 |
2 | Q1 | Q1 | Q1 | Q2 | Q2 | Q2 | Q3 | Q3 | Q3 |
3 | Q1 | Q1 | Q1 | Q2 | Q2 | Q2 | Q3 | Q3 | Q3 |
4 | Q4 | Q4 | Q4 | Q5 | Q5 | Q5 | Q6 | Q6 | Q6 |
5 | Q4 | Q4 | Q4 | Q5 | Q5 | Q5 | Q6 | Q6 | Q6 |
6 | Q4 | Q4 | Q4 | Q5 | Q5 | Q5 | Q6 | Q6 | Q6 |
7 | Q7 | Q7 | Q7 | Q8 | Q8 | Q8 | Q9 | Q9 | Q9 |
8 | Q7 | Q7 | Q7 | Q8 | Q8 | Q8 | Q9 | Q9 | Q9 |
9 | Q7 | Q7 | Q7 | Q8 | Q8 | Q8 | Q9 | Q9 | Q9 |
![]() |
Bild: Sudoku Rahmen |
![]() |
Q | Z | S | Koordinierungsgrad (KG) | Operation |
= | = | != | 2 | a2 (alpha) |
= | != | = | 2 | b2 (beta) |
= | != | != | 1 | a1 (alpha) |
!= | = | != | 1 | b1 (beta) |
!= | != | != | 0 | g (gamma) |
! 9.
0. 0.
0. 5.
0. 0.
0. 6. ! ! 5. 6. 0. 0. 0. 0. 0. 4. 1. ! ! 0. 0. 0. 0. 1. 0. 0. 0. 0. ! ! 0. 0. 0. 1. 0. 3. 0. 0. 0. ! ! 4. 3. 9. 0. 8. 0. 7. 1. 2. ! ! 0. 0. 0. 7. 0. 2. 0. 0. 0. ! ! 0. 0. 0. 0. 7. 0. 0. 0. 0. ! ! 1. 5. 0. 0. 0. 0. 0. 3. 4. ! ! 3. 0. 0. 0. 2. 0. 0. 0. 5. ! |
Eingabe einer 9x9 Matrix mit vorgegebenen Ziffern; Verteilung entsprechend Sudoku-Regeln.
Zeilenweise: Berechnung der Komplementmengen für die Zeilen (Z-), für die Spalten (S-), sowie wie für 3er-Quadranten (Q-).
3Bandweise: Anordnung der 3Bänder B1 - B3 entsprechend der 'Zifferndichte': Man beginnt mit dem 3Band mit der höchsten Zifferndichte. Falls alle gleich, dann 'von oben nach unten'.
Zeilenweise innerhalb eines 3Bandes: Berechne für jedes Element der Zeile die Schnittmenge entsprechend Zi- geschnitten Si- geschnitten Qi-. Hinweis: Jede Zeile benötigt mindestens so viele verschiedene Ziffern ('angebotene Werte'), wie verschiedene Felder ('Lösungskandidaten') vorkommen! Ist diese Bedingung nicht erfüllt, kann es keine Lösung geben.
Falls Minimalbedingung für alle Zeilen des aktuellen 3Bandes erfüllt sind: Konstruiere für alle Zeilen des aktuellen 3Bandes eine Lösungsmenge indem (i) die Schnittmengen jedes Elementes nach Mächtigkeit geordnet werden: kleinste Mächtigkeit vor grösserer Mächtigkeit; (ii) eindeutige Werte erzwingen Auswahl und Setzung /*Erzwungen*/. (iii) Falls keine Lösungsmengen mit nur 1 Element ü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. Man wählt dann das Element mit dem kleinsten Koordinierungsgrad (KG) im aktuellen 3Band aus (es kann auch hier die Möglichkeit geben, dass eine Eindeutigkeit dadurch gegeben ist, dass die Anzahl der Schnittmengen gleich ist der Anzahl der möglichen Werte, und zwar im Bereich Q oder S oder Z!). (iv) Jede Auswahl kann zu Löschungen in anderen Schnittmengen führen (koordiniert über Unterquadrat Q, Zeile Z oder Spalte S).(v) Wiederhole 5.i - 5.iv bis entweder eine vollständige Lösung vorliegt oder aber die minimale Lösungsbedingung verletzt worden ist.
Wenn keine Lösung möglich ist,dann Abbruch mit Fehlermeldung 'NO SOLUTION'.
Falls Lösung möglich ist und noch ein 3Band frei ist, dann gehe zum nächsten 3Band und mache weiter mit (5)
! 9.
0.
0. 0.
5.
0. 0.
0. 6. ! ! 5. 6. 0. 0. 0. 0. 0. 4. 1. ! ! 0. 0. 0. 0. 1. 0. 0. 0. 0. ! ! 2. 7. 5. 1. 4. 3. 6. 8. 9. ! ! 4. 3. 9. 5. 8. 6. 7. 1. 2. ! ! 6. 1. 8. 7. 9. 2. 4. 5. 3. ! ! 0. 0. 0. 0. 7. 0. 0. 0. 0. ! ! 1. 5. 0. 0. 0. 0. 0. 3. 4. ! ! 3. 0. 0. 0. 2. 0. 0. 0. 5. ! |
|
For any node n in solution graph g with level c and depth d |
---|---|
1 |
IF node is complete, stop with SUCCESS |
2 |
IF node n has new children for c+1 select a child from left to right, operate on it, and goto (1) |
3 |
IF there are neighbours on level c then take next neighbour from left to right, operate on it and goto (1) |
4 |
IF one can go back to level c-1 goto (3) |
5 |
Stop with FAILURE |
|
---|
Figure: Algorithm with depth-first search and backtracking |
Die generelle Idee ist die, dass man einen Startzustand hat und mögliche Zielzustände (= SUCCESS) . Die Verbindung zwischen Startzustand und Zielzustände ist dadurch gegeben, dass man auf einen aktuellen Zustand bestimmte Operationen anwenden kann, die dann zum aktuellen Zustand Nachfolger (= children) erzeugen. Einer dieser Nachfolger ist dann entweder ein Zielzustand oder aber nicht. Wenn alle möglichen Nachfolger ausprobiert worden sind und kein Zielzustand gefunden wurde, dann gibt es keine Lösung (= FAILURE).
Die Verbindung von Tiefensuche und Backtracking wirkt sich dahingehend aus, dass der Algorithmus für jeden Knoten erst einmal Nachfolger sucht, unter diesen den ersten von links nach rechts auswählt, für diesen wieder Nachfolger sucht, solange, bis es keine Nachfolger mehr gibt oder zwischendurch ein Zielzustand auftrat. Findet sich kein Nachfolger mehr, dann werden zunächst die aktuellen Nachbarn (= neighbours) aufgesucht. Für jeden Nachbarn wird dann die gleiche Strategie ausprobiert: erst alle möglichen Nachfolger bis man die nächsten Nachbarn aufsucht. Sind die aktuellen Nachbarn verbraucht, dann versucht der Algorithmus eine Stufe (level) zurückzugehen, um über die unbesuchten Nachbarn dieser Stufe wieder seine Strategie von Nachfolgern zuerst und dann Nachbarn anzuwenden. Falls sich zwischendurch kein Zielzustand findet, wird dieser Algorithmus nach endlich vielen Schritten alle möglichen Knoten besucht haben. Dann stoppt er mit Misserfolg (= failure).
Ein Knoten im Lösungsgraphen (= solution graph) besteht in unserem Fall aus einem 9x9-Feld mit den bis zu diesem Zeitpunkt gesetzten Werten. Zusätzlich haben wir die drei Bänder geordnet nach ihrer Dichte mit einem Marker, der anzeigt, welches Band gerade in Bearbeitung ist. Schliesslich gibt es für alle noch nicht besetzten Felder des aktuellen Bandes die Menge der potentiellen Werte {Xi.j, .... } unter Berücksichtigung der Koordinierungen.
Eine mögliche Operationen ergibt sich aus einer simultanen Auswahl plus Löschung von Elementen in den potentiellen Werten der Lösungskandidaten{X i.j, .... }. Wenn für einen bestimmten Kandidaten Xi.j ein Wert w ausgewählt wird, dann muss dieser Wert w zugleich in den potentiellen Lösungsmengen aller Kandidaten der gleichen Zeile, der gleichen Spalte sowie des gleichen Unterquadrates gelöscht werden. Ferner folgt aus der Auswahl, dass dieser Wert an der zugehörigen Stelle im 9x9-Feld neu gesetzt wird.
Führt die Anwendung einer Operation zu einem 9x9-Feld, in dem alle Felder korrekt besetzt sind, dann liegt eine Lösung vor, d.h. dieses Feld repräsentiert einen Zielzustand.
Wenn wir dieses Konzept jetzt auf unser Beispiel an.
X4.1 aus Z4-
geschnitten
mit S1-
geschnitten mit Q4- = {2,6,7,8}
X4.2 aus Z4-
geschnitten mit S2-
geschnitten mit Q4- = {2,7,8}
X4.3 aus Z4-
geschnitten mit S3-
geschnitten mit Q4- = {2,5,6,7,8}
X4.5 aus Z4-
geschnitten mit S5-
geschnitten mit Q5- = {4,6,9}
X4.7 aus Z4-
geschnitten mit S7-
geschnitten mit Q6- = {4,5,6,8,9}
X4.8 aus Z4-
geschnitten mit S8-
geschnitten mit Q6- = {5,6,8,9}
X4.9 aus Z4-
geschnitten mit S9-
geschnitten mit Q6- = {8,9}
-------------------------------------------------------------------
X5.4 aus Z5-
geschnitten mit S4-
geschnitten mit Q5- = {5,6}
X5.6 aus Z5-
geschnitten mit S6-
geschnitten mit Q5- = {5,6}
-------------------------------------------------------------------
X6.1 aus Z6- geschnitten
mit S1-
geschnitten mit Q4- = {6,8}
X6.2 aus Z6-
geschnitten mit S2-
geschnitten mit Q4- = {1,8}
X6.3 aus Z6-
geschnitten mit S3-
geschnitten mit Q4- = {1,5,6,8}
X6.5 aus Z6-
geschnitten mit S5-
geschnitten mit Q5- = {4,6,9}
X6.7 aus Z6-
geschnitten mit S7-
geschnitten mit Q6- = {3,4,5,6,8,9}
X6.8 aus Z6-
geschnitten mit S8-
geschnitten mit Q6- = {5,6,8,9}
X6.9 aus Z6-
geschnitten mit S9-
geschnitten mit Q6- = {3,8,9}
![]() |
Bild: Anordnung der Elemente aus den Mächtigkeiten als Abhängigkeitsgraph (dependency Graph) |
Basis ==> | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
Exp. V | ||||||||||
1 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
2 | 81 | 64 | 49 | 36 | 25 | 16 | 9 | 4 | 1 | |
3 | 729 | 512 | 343 | 216 | 125 | 64 | 27 | 8 | 1 | |
4 | 6.561 | 4.096 | 2.401 | 1.296 | 625 | 256 | 81 | 16 | 1 | |
5 | 59.049 | 32.768 | 16.807 | 7.776 | 3.125 | 1.024 | 243 | 32 | 1 | |
6 | 531.441 | 262.144 | 117.649 | 46.656 | 15.625 | 4.096 | 729 | 64 | 1 | |
7 | 4.782.969 | 2.097.152 | 823.543 | 279.936 | 78.125 | 16.384 | 2.187 | 128 | 1 | |
8 | 43.046.721 | 16.777.216 | 5.764.801 | 1.679.616 | 390.625 | 65.536 | 6.561 | 256 | 1 | |
9 | 387.420.489 | 134.217.728 | 40.353.607 | 10.077.696 | 1.953.125 | 262.144 | 19.683 | 512 | 1 | |
10 | 3.486.784.401 | 1.073.741.824 | 282.475.249 | 60.466.176 | 9.765.625 | 1.048.576 | 59.049 | 1.024 | 1 | |
11 | 31.381.059.609 | 8.589.934.592 | 1.977.326.743 | 362.797.056 | 48.828.125 | 4.194.304 | 177.147 | 2.048 | 1 | |
12 | 282.429.536.481 | 68.719.476.736 | 13.841.287.201 | 2.176.782.336 | 244.140.625 | 16.777.216 | 531.441 | 4.096 | 1 | |
13 | 2.541.865.828.329 | 549.755.813.888 | 96.889.010.407 | 13.060.694.016 | 1.220.703.125 | 67.108.864 | 1.594.323 | 8.192 | 1 | |
14 | 22.876.792.454.961 | 4.398.046.511.104 | 678.223.072.849 | 78.364.164.096 | 6.103.515.625 | 268.435.456 | 4.782.969 | 16.384 | 1 | |
15 | 205.891.132.094.649 | 35.184.372.088.832 | 4.747.561.509.943 | 470.184.984.576 | 30.517.578.125 | 1.073.741.824 | 14.348.907 | 32.768 | 1 | |
16 | 1.853.020.188.851.840 | 281.474.976.710.656 | 33.232.930.569.601 | 2.821.109.907.456 | 152.587.890.625 | 4.294.967.296 | 43.046.721 | 65.536 | 1 | |
17 | 16.677.181.699.666.600 | 2.251.799.813.685.250 | 232.630.513.987.207 | 16.926.659.444.736 | 762.939.453.125 | 17.179.869.184 | 129.140.163 | 131.072 | 1 | |
18 | 150.094.635.296.999.000 | 18.014.398.509.482.000 | 1.628.413.597.910.450 | 101.559.956.668.416 | 3.814.697.265.625 | 68.719.476.736 | 387.420.489 | 262.144 | 1 | |
19 | 1.350.851.717.672.990.000 | 144.115.188.075.856.000 | 11.398.895.185.373.100 | 609.359.740.010.496 | 19.073.486.328.125 | 274.877.906.944 | 1.162.261.467 | 524.288 | 1 | |
20 | 12.157.665.459.056.900.000 | 1.152.921.504.606.850.000 | 79.792.266.297.612.000 | 3.656.158.440.062.980 | 95.367.431.640.625 | 1.099.511.627.776 | 3.486.784.401 | 1.048.576 | 1 | |
21 | 109.418.989.131.512.000.000 | 9.223.372.036.854.780.000 | 558.545.864.083.284.000 | 21.936.950.640.377.900 | 476.837.158.203.125 | 4.398.046.511.104 | 10.460.353.203 | 2.097.152 | 1 | |
22 | 984.770.902.183.611.000.000 | 73.786.976.294.838.200.000 | 3.909.821.048.582.990.000 | 131.621.703.842.267.000 | 2.384.185.791.015.620 | 17.592.186.044.416 | 31.381.059.609 | 4.194.304 | 1 | |
23 | 8.862.938.119.652.500.000.000 | 590.295.810.358.706.000.000 | 27.368.747.340.080.900.000 | 789.730.223.053.603.000 | 11.920.928.955.078.100 | 70.368.744.177.664 | 94.143.178.827 | 8.388.608 | 1 | |
24 | 79.766.443.076.872.500.000.000 | 4.722.366.482.869.650.000.000 | 191.581.231.380.566.000.000 | 4.738.381.338.321.620.000 | 59.604.644.775.390.600 | 281.474.976.710.656 | 282.429.536.481 | 16.777.216 | 1 | |
25 | 717.897.987.691.853.000.000.000 | 37.778.931.862.957.200.000.000 | 1.341.068.619.663.970.000.000 | 28.430.288.029.929.700.000 | 298.023.223.876.953.000 | 1.125.899.906.842.620 | 847.288.609.443 | 33.554.432 | 1 | |
26 | 6.461.081.889.226.670.000.000.000 | 302.231.454.903.657.000.000.000 | 9.387.480.337.647.760.000.000 | 170.581.728.179.578.000.000 | 1.490.116.119.384.770.000 | 4.503.599.627.370.500 | 2.541.865.828.329 | 67.108.864 | 1 | |
27 | 58.149.737.003.040.100.000.000.000 | 2.417.851.639.229.260.000.000.000 | 65.712.362.363.534.300.000.000 | 1.023.490.369.077.470.000.000 | 7.450.580.596.923.830.000 | 18.014.398.509.482.000 | 7.625.597.484.987 | 134.217.728 | 1 | |
28 | 523.347.633.027.361.000.000.000.000 | 19.342.813.113.834.100.000.000.000 | 459.986.536.544.740.000.000.000 | 6.140.942.214.464.820.000.000 | 37.252.902.984.619.100.000 | 72.057.594.037.927.900 | 22.876.792.454.961 | 268.435.456 | 1 | |
29 | 4.710.128.697.246.250.000.000.000.000 | 154.742.504.910.673.000.000.000.000 | 3.219.905.755.813.180.000.000.000 | 36.845.653.286.788.900.000.000 | 186.264.514.923.096.000.000 | 288.230.376.151.712.000 | 68.630.377.364.883 | 536.870.912 | 1 | |
30 | 42.391.158.275.216.200.000.000.000.000 | 1.237.940.039.285.380.000.000.000.000 | 22.539.340.290.692.300.000.000.000 | 221.073.919.720.733.000.000.000 | 931.322.574.615.479.000.000 | 1.152.921.504.606.850.000 | 205.891.132.094.649 | 1.073.741.824 | 1 | |
31 | 381.520.424.476.946.000.000.000.000.000 | 9.903.520.314.283.040.000.000.000.000 | 157.775.382.034.846.000.000.000.000 | 1.326.443.518.324.400.000.000.000 | 4.656.612.873.077.390.000.000 | 4.611.686.018.427.390.000 | 617.673.396.283.947 | 2.147.483.648 | 1 | |
32 | 3.433.683.820.292.510.000.000.000.000.000 | 79.228.162.514.264.300.000.000.000.000 | 1.104.427.674.243.920.000.000.000.000 | 7.958.661.109.946.400.000.000.000 | 23.283.064.365.387.000.000.000 | 18.446.744.073.709.600.000 | 1.853.020.188.851.840 | 4.294.967.296 | 1 | |
33 | 30.903.154.382.632.600.000.000.000.000.000 | 633.825.300.114.115.000.000.000.000.000 | 7.730.993.719.707.440.000.000.000.000 | 47.751.966.659.678.400.000.000.000 | 116.415.321.826.935.000.000.000 | 73.786.976.294.838.200.000 | 5.559.060.566.555.520 | 8.589.934.592 | 1 | |
34 | 278.128.389.443.693.000.000.000.000.000.000 | 5.070.602.400.912.920.000.000.000.000.000 | 54.116.956.037.952.100.000.000.000.000 | 286.511.799.958.070.000.000.000.000 | 582.076.609.134.674.000.000.000 | 295.147.905.179.353.000.000 | 16.677.181.699.666.600 | 17.179.869.184 | 1 | |
35 | 2.503.155.504.993.240.000.000.000.000.000.000 | 40.564.819.207.303.300.000.000.000.000.000 | 378.818.692.265.665.000.000.000.000.000 | 1.719.070.799.748.420.000.000.000.000 | 2.910.383.045.673.370.000.000.000 | 1.180.591.620.717.410.000.000 | 50.031.545.098.999.700 | 34.359.738.368 | 1 | |
36 | 22.528.399.544.939.200.000.000.000.000.000.000 | 324.518.553.658.427.000.000.000.000.000.000 | 2.651.730.845.859.650.000.000.000.000.000 | 10.314.424.798.490.500.000.000.000.000 | 14.551.915.228.366.900.000.000.000 | 4.722.366.482.869.650.000.000 | 150.094.635.296.999.000 | 68.719.476.736 | 1 | |
37 | 202.755.595.904.453.000.000.000.000.000.000.000 | 2.596.148.429.267.410.000.000.000.000.000.000 | 18.562.115.921.017.600.000.000.000.000.000 | 61.886.548.790.943.200.000.000.000.000 | 72.759.576.141.834.300.000.000.000 | 18.889.465.931.478.600.000.000 | 450.283.905.890.997.000 | 137.438.953.472 | 1 | |
38 | 1.824.800.363.140.070.000.000.000.000.000.000.000 | 20.769.187.434.139.300.000.000.000.000.000.000 | 129.934.811.447.123.000.000.000.000.000.000 | 371.319.292.745.659.000.000.000.000.000 | 363.797.880.709.171.000.000.000.000 | 75.557.863.725.914.300.000.000 | 1.350.851.717.672.990.000 | 274.877.906.944 | 1 | |
39 | 16.423.203.268.260.700.000.000.000.000.000.000.000 | 166.153.499.473.114.000.000.000.000.000.000.000 | 909.543.680.129.861.000.000.000.000.000.000 | 2.227.915.756.473.960.000.000.000.000.000 | 1.818.989.403.545.860.000.000.000.000 | 302.231.454.903.657.000.000.000 | 4.052.555.153.018.980.000 | 549.755.813.888 | 1 | |
40 | 147.808.829.414.346.000.000.000.000.000.000.000.000 | 1.329.227.995.784.920.000.000.000.000.000.000.000 | 6.366.805.760.909.030.000.000.000.000.000.000 | 13.367.494.538.843.700.000.000.000.000.000 | 9.094.947.017.729.280.000.000.000.000 | 1.208.925.819.614.630.000.000.000 | 12.157.665.459.056.900.000 | 1.099.511.627.776 | 1 | |
41 | 1.330.279.464.729.110.000.000.000.000.000.000.000.000 | 10.633.823.966.279.300.000.000.000.000.000.000.000 | 44.567.640.326.363.200.000.000.000.000.000.000 | 80.204.967.233.062.400.000.000.000.000.000 | 45.474.735.088.646.400.000.000.000.000 | 4.835.703.278.458.520.000.000.000 | 36.472.996.377.170.800.000 | 2.199.023.255.552 | 1 | |
42 | 11.972.515.182.562.000.000.000.000.000.000.000.000.000 | 85.070.591.730.234.600.000.000.000.000.000.000.000 | 311.973.482.284.542.000.000.000.000.000.000.000 | 481.229.803.398.374.000.000.000.000.000.000 | 227.373.675.443.232.000.000.000.000.000 | 19.342.813.113.834.100.000.000.000 | 109.418.989.131.512.000.000 | 4.398.046.511.104 | 1 | |
43 | 107.752.636.643.058.000.000.000.000.000.000.000.000.000 | 680.564.733.841.877.000.000.000.000.000.000.000.000 | 2.183.814.375.991.800.000.000.000.000.000.000.000 | 2.887.378.820.390.250.000.000.000.000.000.000 | 1.136.868.377.216.160.000.000.000.000.000 | 77.371.252.455.336.300.000.000.000 | 328.256.967.394.537.000.000 | 8.796.093.022.208 | 1 | |
44 | 969.773.729.787.524.000.000.000.000.000.000.000.000.000 | 5.444.517.870.735.020.000.000.000.000.000.000.000.000 | 15.286.700.631.942.600.000.000.000.000.000.000.000 | 17.324.272.922.341.500.000.000.000.000.000.000 | 5.684.341.886.080.800.000.000.000.000.000 | 309.485.009.821.345.000.000.000.000 | 984.770.902.183.611.000.000 | 17.592.186.044.416 | 1 | |
45 | 8.727.963.568.087.710.000.000.000.000.000.000.000.000.000 | 43.556.142.965.880.100.000.000.000.000.000.000.000.000 | 107.006.904.423.598.000.000.000.000.000.000.000.000 | 103.945.637.534.049.000.000.000.000.000.000.000 | 28.421.709.430.404.000.000.000.000.000.000 | 1.237.940.039.285.380.000.000.000.000 | 2.954.312.706.550.830.000.000 | 35.184.372.088.832 | 1 | |
46 | 78.551.672.112.789.400.000.000.000.000.000.000.000.000.000 | 348.449.143.727.041.000.000.000.000.000.000.000.000.000 | 749.048.330.965.186.000.000.000.000.000.000.000.000 | 623.673.825.204.293.000.000.000.000.000.000.000 | 142.108.547.152.020.000.000.000.000.000.000 | 4.951.760.157.141.520.000.000.000.000 | 8.862.938.119.652.500.000.000 | 70.368.744.177.664 | 1 | |
47 | 706.965.049.015.105.000.000.000.000.000.000.000.000.000.000 | 2.787.593.149.816.330.000.000.000.000.000.000.000.000.000 | 5.243.338.316.756.300.000.000.000.000.000.000.000.000 | 3.742.042.951.225.760.000.000.000.000.000.000.000 | 710.542.735.760.100.000.000.000.000.000.000 | 19.807.040.628.566.100.000.000.000.000 | 26.588.814.358.957.500.000.000 | 140.737.488.355.328 | 1 | |
48 | 6.362.685.441.135.940.000.000.000.000.000.000.000.000.000.000 | 22.300.745.198.530.600.000.000.000.000.000.000.000.000.000 | 36.703.368.217.294.100.000.000.000.000.000.000.000.000 | 22.452.257.707.354.600.000.000.000.000.000.000.000 | 3.552.713.678.800.500.000.000.000.000.000.000 | 79.228.162.514.264.300.000.000.000.000 | 79.766.443.076.872.500.000.000 | 281.474.976.710.656 | 1 | |
49 | 57.264.168.970.223.500.000.000.000.000.000.000.000.000.000.000 | 178.405.961.588.245.000.000.000.000.000.000.000.000.000.000 | 256.923.577.521.059.000.000.000.000.000.000.000.000.000 | 134.713.546.244.127.000.000.000.000.000.000.000.000 | 17.763.568.394.002.500.000.000.000.000.000.000 | 316.912.650.057.057.000.000.000.000.000 | 239.299.329.230.618.000.000.000 | 562.949.953.421.312 | 1 | |
50 | 515.377.520.732.011.000.000.000.000.000.000.000.000.000.000.000 | 1.427.247.692.705.960.000.000.000.000.000.000.000.000.000.000 | 1.798.465.042.647.410.000.000.000.000.000.000.000.000.000 | 808.281.277.464.764.000.000.000.000.000.000.000.000 | 88.817.841.970.012.500.000.000.000.000.000.000 | 1.267.650.600.228.230.000.000.000.000.000 | 717.897.987.691.853.000.000.000 | 1.125.899.906.842.620 | 1 | |
51 | 4.638.397.686.588.100.000.000.000.000.000.000.000.000.000.000.000 | 11.417.981.541.647.700.000.000.000.000.000.000.000.000.000.000 | 12.589.255.298.531.900.000.000.000.000.000.000.000.000.000 | 4.849.687.664.788.580.000.000.000.000.000.000.000.000 | 444.089.209.850.063.000.000.000.000.000.000.000 | 5.070.602.400.912.920.000.000.000.000.000 | 2.153.693.963.075.560.000.000.000 | 2.251.799.813.685.250 | 1 | |
52 | 41.745.579.179.292.900.000.000.000.000.000.000.000.000.000.000.000 | 91.343.852.333.181.400.000.000.000.000.000.000.000.000.000.000 | 88.124.787.089.723.200.000.000.000.000.000.000.000.000.000 | 29.098.125.988.731.500.000.000.000.000.000.000.000.000 | 2.220.446.049.250.310.000.000.000.000.000.000.000 | 20.282.409.603.651.700.000.000.000.000.000 | 6.461.081.889.226.670.000.000.000 | 4.503.599.627.370.500 | 1 | |
53 | 375.710.212.613.636.000.000.000.000.000.000.000.000.000.000.000.000 | 730.750.818.665.451.000.000.000.000.000.000.000.000.000.000.000 | 616.873.509.628.062.000.000.000.000.000.000.000.000.000.000 | 174.588.755.932.389.000.000.000.000.000.000.000.000.000 | 11.102.230.246.251.600.000.000.000.000.000.000.000 | 81.129.638.414.606.700.000.000.000.000.000 | 19.383.245.667.680.000.000.000.000 | 9.007.199.254.740.990 | 1 | |
54 | 3.381.391.913.522.730.000.000.000.000.000.000.000.000.000.000.000.000 | 5.846.006.549.323.610.000.000.000.000.000.000.000.000.000.000.000 | 4.318.114.567.396.440.000.000.000.000.000.000.000.000.000.000 | 1.047.532.535.594.330.000.000.000.000.000.000.000.000.000 | 55.511.151.231.257.800.000.000.000.000.000.000.000 | 324.518.553.658.427.000.000.000.000.000.000 | 58.149.737.003.040.100.000.000.000 | 18.014.398.509.482.000 | 1 | |
55 | 30.432.527.221.704.500.000.000.000.000.000.000.000.000.000.000.000.000 | 46.768.052.394.588.900.000.000.000.000.000.000.000.000.000.000.000 | 30.226.801.971.775.100.000.000.000.000.000.000.000.000.000.000 | 6.285.195.213.566.010.000.000.000.000.000.000.000.000.000 | 277.555.756.156.289.000.000.000.000.000.000.000.000 | 1.298.074.214.633.710.000.000.000.000.000.000 | 174.449.211.009.120.000.000.000.000 | 36.028.797.018.964.000 | 1 | |
56 | 273.892.744.995.341.000.000.000.000.000.000.000.000.000.000.000.000.000 | 374.144.419.156.711.000.000.000.000.000.000.000.000.000.000.000.000 | 211.587.613.802.425.000.000.000.000.000.000.000.000.000.000.000 | 37.711.171.281.396.000.000.000.000.000.000.000.000.000.000 | 1.387.778.780.781.450.000.000.000.000.000.000.000.000 | 5.192.296.858.534.830.000.000.000.000.000.000 | 523.347.633.027.361.000.000.000.000 | 72.057.594.037.927.900 | 1 | |
57 | 2.465.034.704.958.070.000.000.000.000.000.000.000.000.000.000.000.000.000 | 2.993.155.353.253.690.000.000.000.000.000.000.000.000.000.000.000.000 | 1.481.113.296.616.980.000.000.000.000.000.000.000.000.000.000.000 | 226.267.027.688.376.000.000.000.000.000.000.000.000.000.000 | 6.938.893.903.907.230.000.000.000.000.000.000.000.000 | 20.769.187.434.139.300.000.000.000.000.000.000 | 1.570.042.899.082.080.000.000.000.000 | 144.115.188.075.856.000 | 1 | |
58 | 22.185.312.344.622.600.000.000.000.000.000.000.000.000.000.000.000.000.000 | 23.945.242.826.029.500.000.000.000.000.000.000.000.000.000.000.000.000 | 10.367.793.076.318.800.000.000.000.000.000.000.000.000.000.000.000 | 1.357.602.166.130.260.000.000.000.000.000.000.000.000.000.000 | 34.694.469.519.536.100.000.000.000.000.000.000.000.000 | 83.076.749.736.557.300.000.000.000.000.000.000 | 4.710.128.697.246.250.000.000.000.000 | 288.230.376.151.712.000 | 1 | |
59 | 199.667.811.101.603.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 191.561.942.608.236.000.000.000.000.000.000.000.000.000.000.000.000.000 | 72.574.551.534.231.900.000.000.000.000.000.000.000.000.000.000.000 | 8.145.612.996.781.540.000.000.000.000.000.000.000.000.000.000 | 173.472.347.597.681.000.000.000.000.000.000.000.000.000 | 332.306.998.946.229.000.000.000.000.000.000.000 | 14.130.386.091.738.700.000.000.000.000 | 576.460.752.303.424.000 | 1 | |
60 | 1.797.010.299.914.430.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 1.532.495.540.865.890.000.000.000.000.000.000.000.000.000.000.000.000.000 | 508.021.860.739.623.000.000.000.000.000.000.000.000.000.000.000.000 | 48.873.677.980.689.300.000.000.000.000.000.000.000.000.000.000 | 867.361.737.988.404.000.000.000.000.000.000.000.000.000 | 1.329.227.995.784.920.000.000.000.000.000.000.000 | 42.391.158.275.216.200.000.000.000.000 | 1.152.921.504.606.850.000 | 1 | |
61 | 16.173.092.699.229.900.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 12.259.964.326.927.100.000.000.000.000.000.000.000.000.000.000.000.000.000 | 3.556.153.025.177.360.000.000.000.000.000.000.000.000.000.000.000.000 | 293.242.067.884.136.000.000.000.000.000.000.000.000.000.000.000 | 4.336.808.689.942.020.000.000.000.000.000.000.000.000.000 | 5.316.911.983.139.660.000.000.000.000.000.000.000 | 127.173.474.825.649.000.000.000.000.000 | 2.305.843.009.213.690.000 | 1 | |
62 | 145.557.834.293.069.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 98.079.714.615.416.900.000.000.000.000.000.000.000.000.000.000.000.000.000 | 24.893.071.176.241.500.000.000.000.000.000.000.000.000.000.000.000.000 | 1.759.452.407.304.810.000.000.000.000.000.000.000.000.000.000.000 | 21.684.043.449.710.100.000.000.000.000.000.000.000.000.000 | 21.267.647.932.558.700.000.000.000.000.000.000.000 | 381.520.424.476.946.000.000.000.000.000 | 4.611.686.018.427.390.000 | 1 | |
63 | 1.310.020.508.637.620.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 784.637.716.923.335.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 174.251.498.233.691.000.000.000.000.000.000.000.000.000.000.000.000.000 | 10.556.714.443.828.900.000.000.000.000.000.000.000.000.000.000.000 | 108.420.217.248.550.000.000.000.000.000.000.000.000.000.000 | 85.070.591.730.234.600.000.000.000.000.000.000.000 | 1.144.561.273.430.840.000.000.000.000.000 | 9.223.372.036.854.780.000 | 1 | |
64 | 11.790.184.577.738.600.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 6.277.101.735.386.680.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 1.219.760.487.635.840.000.000.000.000.000.000.000.000.000.000.000.000.000 | 63.340.286.662.973.300.000.000.000.000.000.000.000.000.000.000.000 | 542.101.086.242.752.000.000.000.000.000.000.000.000.000.000 | 340.282.366.920.938.000.000.000.000.000.000.000.000 | 3.433.683.820.292.510.000.000.000.000.000 | 18.446.744.073.709.600.000 | 1 | |
65 | 106.111.661.199.647.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 50.216.813.883.093.500.000.000.000.000.000.000.000.000.000.000.000.000.000.000 | 8.538.323.413.450.850.000.000.000.000.000.000.000.000.000.000.000.000.000 | 380.041.719.977.840.000.000.000.000.000.000.000.000.000.000.000.000 | 2.710.505.431.213.760.000.000.000.000.000.000.000.000.000.000 | 1.361.129.467.683.750.000.000.000.000.000.000.000.000 | 10.301.051.460.877.500.000.000.000.000.000 | 36.893.488.147.419.100.000 | 1 |
Dies ist so zu lesen: wenn man 1 Lösungsmenge hat mit 9 Elementen, dann hat man 9 Varianten. Bei 2 Lösungsmengen mit jeweils 9 Elementen hat man 9x9=81 Möglichkeiten, usw. Bei 65 Lösungsmengen (= 65 Felder, die besezt werden sollten) mit jeweils 9 Möglichkeiten (was aufhrund von Koordinierung kaum geht) hätte man dann die astronomische Zahl 106.111.661.199.647 * 1048.
Natürlich wäre ein Algorithmus, der soviele Möglichkeiten ausprobieren sollte, nicht sehr schnell....
Aufgrund des bisherigen Wissens können wir aber annehmen,1 | Bild aus den Elementen von m1 |m1|-viele Startknoten := |m1|-viele Lösungsgraphen G1, ..., Gs mit Endknoten, wobei die Endknoten zu Beginn mit dem Startknoten identisch sind. |
2 | Hänge an jeden Endknoten des aktuellen Lösungsgraphen Gi die Elemente von der nächsten Mächtigkeit mj an, die kompatibel sind. Für jeden kompatiblen Pfad reduziere die Elemente in den noch verbleibden Mächtigkeiten. |
3 | WENN ein Konflikt auftritt, DANN entferne diesen Pfad |
4 | WENN alle Pfade gschlossen sind ohne dass eine Lösung existiert DANN FAILURE |
5 | WENN alle Mächtigkeiten verarbeitet sind, DANN SUCCESS |
6 | WENN SUCCESS in mehr als einem Lösungsgraphen auftritt, DANN war die Lösung nicht eindeutig. |
7 | Gehe nach (2) |
Dazu müsste man jetzt die Menge der Lösungskandidaten auf alle Zeilen ausdehnen.
Problem:
! 9.
0. 0.
0. 5.
0. 0.
0. 6. ! ! 5. 6. 0. 0. 0. 0. 0. 4. 1. ! ! 0. 0. 0. 0. 1. 0. 0. 0. 0. ! ! 0. 0. 0. 1. 0. 3. 0. 0. 0. ! ! 4. 3. 9. 0. 8. 0. 7. 1. 2. ! ! 0. 0. 0. 7. 0. 2. 0. 0. 0. ! ! 0. 0. 0. 0. 7. 0. 0. 0. 0. ! ! 1. 5. 0. 0. 0. 0. 0. 3. 4. ! ! 3. 0. 0. 0. 2. 0. 0. 0. 5. ! |
1 | X5:Z2,S5,Q2 =
{ 3. }
|
X5:Z2,S5,Q2 =
{ 9.}*
|
2 |
X9 : Z4,S9,Q6 = { 8. }! 9. 0. 0. 0. 5. 0. 0. 0. 6. ! ! 5. 6. 0. 0. 3. 0. 0. 4. 1. ! ! 0. 0. 0. 0. 1. 0. 0. 0. 0. ! ! 0. 0. 0. 1. 0. 3. 0. 0. 8. ! ! 4. 3. 9. 0. 8. 0. 7. 1. 2. ! ! 0. 0. 0. 7. 0. 2. 0. 0. 0. ! ! 0. 0. 0. 0. 7. 0. 0. 0. 0. ! ! 1. 5. 0. 0. 0. 0. 0. 3. 4. ! ! 3. 0. 0. 0. 2. 0. 0. 0. 5. ! |
X9 : Z4,S9,Q6 = { 9. } |
X9 : Z4,S9,Q6 = { 8. } |
X9 : Z4,S9,Q6 = { 9. } |
Initial puzzle (kamikaze_1_tdformat.txt):
+---+---+---+
|9 | 5 | 6|
|56 | | 41|
| | 1 | |
+---+---+---+
| |1 3| |
|439| 8 |712|
| |7 2| |
+---+---+---+
| | 7 | |
|15 | | 34|
|3 | 2 | 5|
+---+---+---
........................
no other possibility: row: 9 column: 7 value: 8
Solved!
+---+---+---+
|971|254|386|
|562|837|941|
|843|619|527|
+---+---+---+
|725|143|698|
|439|586|712|
|618|792|453|
+---+---+---+
|284|375|169|
|157|968|234|
|396|421|875|
+---+---+---+
single possibility: 50
one in row/column/block: 24
coloring: 1
push[0] = 1
no other possibility: row: 9 column: 9 value: 5
Solved!
+---+---+---+
|637|254|189|
|459|186|327|
|128|937|546|
+---+---+---+
|596|721|834|
|371|548|962|
|284|693|751|
+---+---+---+
|942|375|618|
|865|419|273|
|713|862|495|
+---+---+---+
single possibility: 48
one in row/column/block: 4
locked candidates: 7
Initial puzzle (samurai_1_tdformat.txt):
+---+---+---+
|4 | 2 | 9|
| 7 | | 6 |
|9 8| |7 1|
+---+---+---+
| 1 |6 9| 3 |
|89 | 3 | 76|
| 6 |8 4| 5 |
+---+---+---+
|5 9| |6 3|
| 4 | | 2 |
|7 | 5 | 8|
+---+---+---+
.................
no other possibility: row: 9 column: 8 value: 9
Solved!
+---+---+---+
|456|721|389|
|173|498|265|
|928|365|741|
+---+---+---+
|215|679|834|
|894|532|176|
|367|814|952|
+---+---+---+
|589|247|613|
|641|983|527|
|732|156|498|
+---+---+---+
single possibility: 50