Sudoku Löser

[simonko]

Hier ein einfacher Sudoku Löser in C gschrieben. Er liest die Werte aus einer txt datei ein und gibt sie in einer anderen aus. Ich hab andere Lösungen hier gesehen, und hab mich aufgeregt, dass die
objektorientierung alles so kompliziert macht.

MFG

[simonko]

ich hab es jetzt so gedreht

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


stimmt das?
es gibt jedenfalls keine lösung

[omata]

Ja, ich weiss es gibt keine Lösung. Das ist richtig. Das ist ja gerade der Witz.

Aber das Programm soll ja selber eine Lösung finden und nicht eine vereinfachte Lösung lösen. Beim Drehen ist ja noch deine Intelligenz mit eingeflossen. Naja, dein Programm ist doch ok. Es kann eben sehr viele Möglichkeiten geben und dann dauert das auch entsprechend lange. Das ist ja bei den meisten dieser Lösungsprogramme so. Deshalb habe ich mich ja auch damit beschäftigt eine Lösung zu finden, die diese unlösbaren Sudokus schneller findet.

Also nix für ungut...

[simonko]

ich hab das sudoku umgedreht. und da hatte ich innerhalb ein paar ms die lösung. es gibt
keine. wenn ich eine funktion schreibe die dass erkennt dass in der unteren hälfte mehr zahlen drin sind. und dass dann umdreht dann passts ja. und das dürfte nicht all zu schwer sein. irgendwie ist das logisch der computer rechnet und kommt dan unten an und sieht dass nichts mehr passt und muss wieder ganz zurück.

[omata]

Ja, so könnte man das machen.

Aber was ist mit dieser Vorgabe...

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

Ich habe die unlösbare Stelle genau in die Mitte gelegt und außen sind überall gleich viele Zahlen gleich angeordnet. Da wird es schwierig mit dem Drehen.

MfG
Thorsten

[simonko]

weiss nicht. hast du eine lösung dafür?

[omata]

Ja, in meiner oben erwähnten Lösung habe ich zwei Algorithmen zur Lösung implementiert. Deine Variante verbirgt sich hinter Fertig lösen (schnell aber dumm).
Dieser Ansatz ist normalerweise sehr schnell, bei unlösbaren Sudokus kann man diesen Ansatz aber vergessen, da er einfach zu lange braucht (Stunden).
Der andere Lösungsansatz, der auch mit diesen gemeinen Varianten zurechtkommt heißt Fertig lösen (langsam aber schlau). Dieser ist im Normalfall etwas langsamer als der erste Ansatz, aber eben in den Speziellfällen wesentlich schneller (Sekunden).

Ich habe einige Tage an der Lösung gesessen. Vielleicht veröffentliche ich sie irgendwann mal.
Macht euch doch selber mal Gedanken...

MfG
Thorsten

[simonko]

poa alter das gibs doch gar nicht dass jemand sich das zeugs für sich behaltet.
man programmiert für sich und für die anderen menschen, für die menschheit damit jeder
was davon hat. wenn du angst hast dass dir jemadn in code klaut dann gib ihn doch unter
der gnu public license...

[omata]

nu bleib mal locker im schritt.

ich habe hier schon so viel code veröffentlicht. diesen code habe ich jetzt mal als einziges nicht veröffentlicht.

schalte dein gehirn ein und versuch es doch mal selber.

nur weil man dir das jetzt nicht in den hintern pustet, so nun auch wieder nich.

[simonko]

beruhig dich mal ey. mein ziel war nie unlösbare sudokus zu lösen.
ich red ja nur von dir. kommst du dir nicht selbst blöd vor mit dieser
geheimnisgehtuerei?

[negaH]

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


Das Ding kann keine Lösung haben

in 2. Zeile

9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
x | 8 | 6 | 5 | 4 | 3 | 2 | 1 | y
0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0

bei X und Y können nur noch die 7 oder 9 rein weil in dieser Zeile alle anderen Zahlen schon vergeben sind. Da aber im 9er Block bei X schon die 9 und auch 7 enthalten sind ist das nicht mehr lösbar.

Gruß Hagen