Sudoku automatisch lösen - Algorithmus Logik-Problem?
Ich bin momentan dabei für die Schule einen Algorithmus für einen automatischen "Sudoku Löser" zu schreiben und will folgende Regeln aus dem Internet für mich nutzen:
http://members.chello.at/ksteiner/klaus/sudokuloeser.htm
Ich verstehe allerdings nicht was Regel A bedeuten soll? Es wäre mir extrem geholfen wenn jemand, der die Logik versteht mir erklären würde was das bedeuten soll
Vielen Dank schonmal!!
3 Antworten
Wenn in n Kästchen, die sich in einer spalte oder reihe oder in einem block befinden dieselben n zahlen sind, können diese zahlen in den anderen Kästchen nicht mehr vorkommen.
z.B. wenn in einer reihe in zwei Kästchen jeweils nur 2 und 1 möglich ist, muss wenn in einem Kästchen die 1 rein kommt ins andere die zwei rein kommen, folglich können dann nur in diese 2 Kästchen 1 und 2 kommen.
Es geht darum, dass jede Zelle in dem Sudoku-Feld den Wert von 1-9 annehmen kann.
Für ein Beispiel nehme ich nun aber ein kleineres Sudoku: Bei einem 4x4 Sudoku kann jede Zelle den Wert von 1-4 annehmen:
Nehmen wir nun folgendes Beispiel:
------------------ | | 3 || | 2 | ------------------ | | || | | ------------------ ------------------ | | || | 3 | ------------------ | | || 1 | | ------------------
Aufgrund der Sudoku-Regeln, bei dem in jeder Zeile, jeder Spalte und jedem Block eine Zahl nur einmal vorkommen darf, ergeben sich hierbei Ausschluss-Kriterien, die in deinem Beispiel A auch angewendet werden:
Sagen wir mal das Kästchen ganz links oben:
Könnte zunächst alle möglichen Werte von 1-4 annehmen, also:
1 2 3 4
Durch die zuvor genannte Regel wird die Werteliste gekürzt, da sich in der ersten Zeile bereits die Werte 3 und 2 befinden. Nachdem die Regel angewendet wurde, ergibt sich eine gekürzte Werteliste:
1 4
Nehmen wir ein anderes Beispiel: ganz rechts unten:
Hier befindet sich im Block Bereits eine 1, eine 3 und in der Spalte die 2:
Also wird die Werteliste hier um diese Werte gekürzt:
4
Somit ergibt sich genau ein passender Wert. Und dieser lässt sich auch in die Zelle schreiben.
habe ich das missverstanden?
Ich denke schon.
Regel A beschreibt genau das.
Diese Regeln besagen folgendes:
Bei einem 9x9 Spielfeld hast du insgesamt 81 Felder. Wovon jedes Feld eine Werteliste hat. Regeln A bis C geben Aufschluss darüber, wie diese Wertelisten zu verkleinern sind, bis nur noch ein wert übrig bleibt.
Wenn Du in einer Zeile zwei Felder hast, die nur die Zahlen 1 und 2 erlauben, dann müssen diese Zahlen auch dort liegen. Setze mal die 1 woanders hin: Jetzt bleibt für diese beiden Felder nur noch die 2 übrig; das geht nicht.
Das gleiche gilt, wenn drei Felder zusammen nur drei Zahlen erlauben: Sie werden diese Zahlen komplett vereinnahmen. Woanders darf keine dieser drei Zahlen stehen, sonst hast Du nicht mehr genug Material, um diese drei Felder zu füllen.
Vielen Dank für die genaue Beschreibung. Allerdings ging es bei deiner Antwort nicht um die besagte "Regel A" sondern um allgemeine Sudoku Regeln oder habe ich das missverstanden?