Sudoku Lösungsprogramm algorithmus (nicht Bruteforce)

[XxbambamxX]

Hi zusammen
Ich wollte mir mal nen Sudoku solver basteln.
Für die die nicht Wissen wie Sudoku „funktioniert“… http://de.wikipedia.org/wiki/Sudoku
Dazu habe ich mir Folgendes überlegt:
Als erstes erstelle ich ein 9*9 Array das je 2 Variablen hat:

struct SFeld
{
bool free;
int number;
};

SFeld Feld[9][9];

danach setze ich überall free auf true und die nummern auf 0 (mit 2 ineinander verschachtelten For schleifen).
Anschliessend fordere ich den Benutzer auf die Vorgegebenen Werte einzutippen.
Diese übertrage ich in das Array und setze dort free auf false damit ich später weiss, dass diese Werte „unveränderbar“ sind bzw die Vorgegebenen Werte für das Sudoku.
Nun erhalte ich ein Lineares (Un-)Gleichungssystem mit einer Variablen anzahl an Variablen und ich weiss nicht wie ich das Lösen kann. Ich habe mir alle Un/Gleichungen aufgeschirben.
Als erstes habe ich natürlich, dass alle Spalten 45 Ergeben. Und da es 9 Spalten gibt sind das 9 Gleichungen. Dann das Gleiche für die Zeilen(nochmal 9) macht insgesamt 18 Gleichungen.
Dann noch die 9 Felder innerhalb. Macht noch mal 9. Also habe ich insgesamt 27.
Dann bekomme ich noch Einen Haufen ungleichungen ( in jeder Zeile,Spalte und Viereck darf ja jede Zahl nur einmal vorkommen).
Nun habe ich aber keine Ahnung wie ich das meinem Programm „beibringen“ soll..
Mit Bruteforce bzw backtracking habe ich schon ein Funktionierendes Programm gemacht allerdings erscheint mir diese Lösung ein bisschen zu wenig elegant
Vielleicht könnt ihr mir ja eine kleine Hilfe/Idee geben. Wäre sehr dankbar!
mfg

 

[Jennesta]

Hi,
ich habe selbst ein Soduko mit ausprobieren gemacht und ich fand das eig schon elegant .
Aber ich weiß was du meinst
Jedoch weiß ich nicht, was du genau mit Ungleichungen meinst bzw wie du dein Sudoku damit lösen willst.

Aber als Ansätze ein Sudoku zu lösen würde ich dann generell so vorgehen, wie du als Mensch auch vorgehen würdest.
Erstmal schaun, wo man sowieso nur eine Zahl einsetzen kann, bzw mögliche Zahlen für Felder speichern und mit anderen vergleichen.
Ich habe ein SudokuHeft, wo in der Einleitung weitere "Verfahren" bzw rein logische Schlüsse erläutert werden. Vielleicht kannst du diese deinem Programm beibringen. Diese zu erklären würde den Rahmen sprengen, aber google mal nach "Versteckter Single", "Nackter Single", "Nacktes Paar", "Verstecktes Paar", "Nackter Dreier", "Versteckter Dreier", "Block-Reihe-Check (BRC)", "Reihe-Block-Check (RBC)", "Erweiterter BRC", vielleicht findest du dazu etwas. Habe das noch nicht ausprobiert.

Und du solltest dich darauf einstellen, zwischendurch auchmal raten zu müssen. Ich habe selbst diverse Sudokus gehabt, wo man zwischendurch mal raten musste um zum richtigen Ergebnis zu kommen bzw weil es keine eindeutigen Schlüsse mehr zu ziehen gab, ohne vorrauszudenken.

Grüße Jennesta