Douglas Parfümerie

 Registrieren || Einloggen || Hilfe/FAQ || Suche || Memberlist || Home || Statistik || Kalender || Staff Willkommen Gast!

 Sudoku Forum » Sudoku-Hilfe » Suche nach einer Lösungsstrategie » Threadansicht

Autor Thread - Seiten: -1-
000
10.11.2010, 09:49 Uhr
Hanno



Hallo,

kann mir bitte jemand für das untenstehende Sudoku Problem eine Lösungsstrategie nennen die nicht auf Ausprobieren (damit wäre es leicht)beruht? Ich meine damit, die Lösung selbst zu finden ist nicht so das Problem, aber wie kommt man ganz gezielt dorthin.
Für jede Hilfe bin ich dankbar

5 4 7 0 6 1 0 3 2
3 1 2 5 4 0 7 6 0
0 0 0 2 0 0 1 4 5
0 5 1 0 0 0 2 0 0
0 0 0 0 1 4 5 0 0
0 0 0 0 5 2 6 0 0
0 8 0 7 0 0 0 0 0
1 7 0 4 2 0 0 5 6
0 0 0 1 0 0 0 0 0

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
001
11.11.2010, 23:30 Uhr
KODELA



Hallo Hanno,

zunächst einmal die Situation einschließlich der noch möglichen Kandidaten:


Quellcode:
*--------------------------------------------------------------------------*
| 5       4       7      | 89      6       1      | 89      3       2      |
| 3       1       2      | 5       4       89     | 7       6       89     |
| 689     69      689    | 2       3789    3789   | 1       4       5      |
|------------------------+------------------------+------------------------|
| 46789   5       1      | 3689    3789    36789  | 2       789     34789  |
| 26789   2369    3689   | 3689    1       4      | 5       789     3789   |
| 4789    39      3489   | 389     5       2      | 6       1789    134789 |
|------------------------+------------------------+------------------------|
| 2469    8       34569  | 7       39      3569   | 349     129     1349   |
| 1       7       39     | 4       2       389    | 389     5       6      |
| 2469    2369    34569  | 1       389     35689  | 3489    2789    34789  |
*--------------------------------------------------------------------------*

Diese Situation gilt es auszuwerten.

Da im Block 6 die 3 nur in der Spalte 9 vertreten ist, kann die 3 in der Spalte 9 außerhalb von Block 3 sicher nicht zugewiesen werden. Wir können die 3 in Spalte 9 Zeile 7 und 9 daher ausschließen.

Das Selbe gilt für die 4 im Block 6 Spalte 9, die ebenfalls im Block 9 Spalte 9 ausgeschlossen werden kann.

Im Block 8 ist die 6 nur in Spalte 6 vertreten und kann daher im Block 5 in dieser Spalte ausgeschlossen werden.

Die 7 ist im Block 5 nur in Zeile 4 vertreten und kann in dieser Zeile außerhalb von Block 5 ausgeschlossen werden.

Im Block 1 ist die 8 nur in Zeile 3 vertreten und kann daher im Block 2 in dieser Zeile ausgeschlossen werden.

Jetzt ist in der Spalte 4 die 3 nur im Block 5 vertreten und kann daher in allen anderen Zellen dieses Blockes ausgeschlossen werden.

Im Block 1 ist die 9 nur in Zeile 3 vertreten und kann in dieser Zeile außerhalb von Block 1 ausgeschlossen werden.

Im Block 8 gibt es drei Zellen, in denen ausschließlich die drei Kandidaten 3, 8 und 9 vertreten sind (Z7S5, Z8S6 und Z9S5). Diese drei Kandidaten können daher in allen anderen Zellen des Blockes 8 ausgeschlossen werden.

In Zeile 4 gibt es ebenfalls drei Zellen (Z4S5, Z4S6 und Z4S8), in denen ausschließlich die drei Kandidaten 7, 8 und 9 vertreten sind. Diese drei Kandidaten können daher in Zeile 4 in allen anderen Zellen ausgeschlossen werden.

In Zeile 8 ist die 8 nur noch in zwei Zellen vertreten (Z8S6 und Z8S7). Im Block 2 ist die 8 ebenfalls in Spalte 6 vertreten. Außerdem noch in Z1S4. Wäre in Zeile 8 die 8 in der Zelle der Spalte 6 zuzuweisen, müsste im Block 2 die 8 der Zelle in Z1S4 zugewiesen werden und könnte nicht mehr der Zelle in Z1S7 zugewiesen werden. Wäre in Zeile 8 die 8 jedoch der Zelle in Spalte 7 zuzuweisen, könnte sie nicht auch der Zelle in Z1S7 zugewiesen werden. Unabhängig davon, welcher Zelle in Zeile 8 die 8 zugewiesen wird, in Z1S7 kann die 8 nicht ebenfalls zugewiesen werden. Wir können sie dort also ausschließen und den einzig verbleibenden Kandidaten 9 dieser Zelle zuweisen.

Danach kann den Zellen in Z1S4 und Z2S9 die 8 und anschließend der Zelle in Z2S6 die 9 zugewiesen werden.

In Zeile 8 ist die 9 nur noch in Spalte 3 vertreten und kann dort zugewiesen werden.

Im Block 5 ist die 8 nur in Zeile 4 vertreten und kann daher in dieser Zeile außerhalb von Block 5 ausgeschlossen werden. In Bertracht kommt nur die Zelle in Z4S8, der darauf hin der einzig verbliebene Kandidat 9 zugewiesen werden kann.

Im Block 6 ist die 8 nur in Spalte 6 vertreten und kann daher außerhalb von Block 6 (in Z9S8) ausgeschlossen werden.

In der Zeile 6 in den Spalten 2 und 4 sind ausschließlich die beiden Kandidaten 3 und 9 vertreten. Diese können daher in allen anderen Zellen dieser Zeile ausgeschlossen werden.

In Spalte 1 gibt es drei Zellen (Z4S1, Z7S1 und Z9S1), in denen ausschließlich die drei Kandidaten 2, 4 und 6 vertreten sind. Diese drei Kandidaten können in allen übrigen Zellen der Spalte 1 ausgeschlossen werden.

Danach ist die 2 in der Zeile 5 nur noch in der Spalte 2 vertreten und kann dieser Zelle zugewiesen werden.

Jetzt haben wir folgende Situation:


Quellcode:
*--------------------------------------------------------*
| 5     4     7    | 8     6     1    | 9     3     2    |
| 3     1     2    | 5     4     9    | 7     6     8    |
| 89    69    68   | 2     37    37   | 1     4     5    |
|------------------+------------------+------------------|
| 46    5     1    | 36    78    78   | 2     9     34   |
| 789   2     368  | 369   1     4    | 5     78    37   |
| 78    39    48   | 39    5     2    | 6     178   147  |
|------------------+------------------+------------------|
| 246   8     3456 | 7     39    56   | 34    12    19   |
| 1     7     9    | 4     2     38   | 38    5     6    |
| 246   36    3456 | 1     389   56   | 348   27    79   |
*--------------------------------------------------------*

In der Zelle Z6S3 sind nur noch die beiden Kandidaten 4 und 8 vertreten. Ist dieser Zelle die 4 zuzuweisen, dann wäre in der Zelle in Z4S1 die 4 auszuschließen und die 6 zuzuweisen. Wäre der Zelle in Z6S3 jedoch die 8 zuzuweisen, wäre die 8 in Z3S3 auszuschließen und dieser Zelle die 6 zuzuweisen.

Wir können also feststellen, dass die 6 mit Sicherheit entweder der Zelle in Z4S1 oder in Z3S3 zuzuweisen ist. Damit kann in allen Zellen, die zum Schnittbereich dieser beiden Zellen gehören, die 6 sicher ausgeschlossen werden. Betroffen davon ist die 6 in der Zelle in Z5S3.

Damit sind alle Klippen umschifft und Du solltest den Rest eigentlich ohne weitere Hilfe selbst lösen können.

Mit freundlichem Gruß,

KODELA
Dieser Post wurde am 12.11.2010 um 08:53 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
002
12.11.2010, 09:08 Uhr
Hanno



Hallo KODELA,

erstmal herzlichen Dank für die Mühe die du dir gemacht hast. Das Ganze dient dazu den Lösungsalgorithmus meines Sudokuprogramms zu verbessern. Der erste Schrtt der mir fehlt ist:

"In Zeile 8 ist die 8 nur noch in zwei Zellen vertreten (Z8S6 und Z8S7). Im Block 2 ist die 8 ebenfalls in Spalte 6 vertreten. Außerdem noch in Z1S4. Wäre in Zeile 8 die 8 in der Zelle der Spalte 6 zuzuweisen, müsste im Block 2 die 8 der Zelle in Z1S4 zugewiesen werden und könnte nicht mehr der Zelle in Z1S7 zugewiesen werden. Wäre in Zeile 8 die 8 jedoch der Zelle in Spalte 7 zuzuweisen, könnte sie nicht auch der Zelle in Z1S7 zugewiesen werden. Unabhängig davon, welcher Zelle in Zeile 8 die 8 zugewiesen wird, in Z1S7 kann die 8 nicht ebenfalls zugewiesen werden. Wir können sie dort also ausschließen und den einzig verbleibenden Kandidaten 9 dieser Zelle zuweisen.
"

und der Zweite
"In der Zelle Z6S3 sind nur noch die beiden Kandidaten 4 und 8 vertreten. Ist dieser Zelle die 4 zuzuweisen, dann wäre in der Zelle in Z4S1 die 4 auszuschließen und die 6 zuzuweisen. Wäre der Zelle in Z6S3 jedoch die 8 zuzuweisen, wäre die 8 in Z3S3 auszuschließen und dieser Zelle die 6 zuzuweisen."

Mal sehen wie ich das in eine vernünftige Stück Software bekomme

Mit freundlichen Grüßen
Markus Hannweber

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
003
12.11.2010, 11:34 Uhr
KODELA



Hallo Markus,

Du schreibst also an einem Sudoku-Programm. Das mache ich auch. Derzeit setze ich eine Excel-Sudoku-Anwendung per Java in ein eigenständiges Programm um. Den Code für die Excel-Anwendung, in die auch die Lösungsstrategie der Y-Gabel, besser bekannt als Y-Wing (Dein zweiter Schritt), eingearbeitet ist, und auch den Code für die Java-Anwendung, auch in ihr wird die Y-Gabel eingesetzt, allerdings noch nicht für die Tipps, kannst Du über meine Homepage bekommen.

Bei dem Problem des ersten Schrittes handelt es sich um das Empty Rectangle, oder wie ich sage, um eine RW-Gabel.

Mit freundlichem Gruß,
KODELA
Dieser Post wurde am 12.11.2010 um 11:36 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
004
12.11.2010, 13:37 Uhr
Hanno



Hallo KODELA,

ich hab mir deine Programme angesehen, leider will das Excel Programm hier nicht laufen, aber das Java Programm läuft sehr gut. Wenn man sich sowas anschaut bekommt man immer wieder neue Ideen. Wenn ich mal wieder einen stabilen Stand habe werd, ich dir mein Programm schicken. Wahrscheinlich hast du dann noch einige Anregungen

Grüße
Markus

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
Seiten: -1-     [ Sudoku-Hilfe ]  


Kontakt | Impressum | powered by ThWboard 3 Beta 2.84-php5 © by Paul Baecher & Felix Gonschorek