sudoku eindeutig lösbar

[$chor$ch]

Hi, bin gerade dabei ein Sudokuspiel zu programmieren nur ein problem hab ich noch.
Wie kann man rausfinden ob ein Sudoku eindeutig lösbar ist oder nicht?
Habt ihr vll. ne Idee?

 

[2nerd4u]

Ab wievielen besetzten Feldern ein Sudokuspiel eindeutig ist, ist soweit ich weiß noch ein ungelöstes mathematisches Problem.

 

[The_S]

Naja, aber vorgabe für ein Sudoku ist ja imho, dass das Feld nur eine einzige Lösungsmöglichkeit hat. Ein Algorithmus, der sowas überprüft, würde mich auch mal interessieren. Spontan fällt mir nur ein mittels Brut-Force alle Möglichkeiten auszuprobieren. Das sollte aber relativ Zeit- und Rechenaufwendig sein ...

 

[fig0]

Eine Möglichkeit immer eindeutig lösbare Sudokus zu erhalten ist folgende:

Du benutzt ein immer gleichbleibendes Spielfeld:

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
------------------------
2 3 4 | 5 6 7 | 8 9 1
5 6 7 | 8 9 1 | 2 3 4
8 9 1 | 2 3 4 | 5 6 7
------------------------
3 4 5 | 6 7 8 | 9 1 2
6 7 8 | 9 1 2 | 3 4 5
9 1 2 | 3 4 5 | 6 7 8

Nun kannst du zufällig gewählte Spalten miteinander tauschen, das gleiche kannst du natürlich auch mit zeilen machen. Daraus gewinnst du auf jeden fall immer ein lösbares Sudoku. Danach löschst du ein paar Zahlen aus den Blöcken jeweils heraus (da gibt es bestimmte löschalgorithmen). Dadurch kannst du auch ein wenig den Schwierigkeitsgrad beeinflussen, wobei sich darüber streiten lässt wann ein Sudoku schwerer/leichter wird.
Anschließend kannst du ja zur Sicherheit nochmal schauen ob es lösbar ist, wenn das nicht schon dein löschalgorithmus macht.

 

[The_S]

Es geht ja nicht darum, ob ein Sudoku lösbar ist oder nicht, das ist ja überhaupt kein Problem! Es geht vielmehr darum festzustellen, ob es wirklich nur eine einzige Lösung für dieses Sudoku gibt und nicht evtl. noch eine Zweite.