|
Sudoku Löser
Liste der Anhänge anzeigen (Anzahl: 3)
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 |
Re: Sudoku Löser
Hallo simonko,
schönes Programm. Etwas unschön ist der harte Programmabsturz, wenn die Input.txt-Datei nicht da ist. Und sonst ist das wie gehabt. Bei folgender Vorgabe braucht dein Solver wie viele andere eben etwas länger... 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 0 | 0 | 0 | 0 | 5 | 0 | 0 | 0 | 0 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 | 0 0 | 0 | 0 | 0 | 0 | 0 | 7 | 0 | 0 0 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 schade, es geht auch schneller. siehe  hierAber trotzdem :thumb: MfG Thorsten |
Re: Sudoku Löser
naja es geht eigentlich um die 2 hauptfunktionen und nicht um die benutzerschnittstelle...
du kannst aber gern alle fehler die dumme benutzer machen könnten abfangen.. ich hab anderes zu tun |
Re: Sudoku Löser
@Omata eigentlich müsste es ja schneller gehen, wenn ich das sudoku einfach drehe, weil du hast ja am ende mehr zahlen reingemacht. dann sind alle kombinationen die er am anfang rechnet umsonst.
|
Re: Sudoku Löser
So wie ich den Code interpretiere, löst er nur eindeutige Sudokus. Wenn es mehrere Lösungen gibt, wird der nicht funktionieren, oder?
|
Re: Sudoku Löser
Doch es funktioniert. Er nimp dabei die erste lösung auf die er kommt.
wenn du das exit(0) entfernst und bei der datei anstatt write append nimmst würde er alle sudokus reinschreiben. das kann aber gefährlich werdn wenn du nur ein paar zahlen vorgibst dann gibt es sehr viele lösungen und die ausgabedatei wird hunderte von MB gros. :) |
Re: Sudoku Löser
@simonko: ja natürlich könntest du es drehen. Nur das Programm müsste dann so schlau sein und das vorher wissen. Das Programm soll es ja lösen und nicht du.
@3_of_8: Wenn es mehrere Lösung gibt, wird bei der ersten gültigen aufgehört - das ist doch völlig ausreichend |
Re: Sudoku Löser
ja dann muss man eben eine funktion schreiben die es dreht. es ist doch nicht so schwer
zu ermitteln wo am meisten werte eingetragen wurden. oder? :) |
Re: Sudoku Löser
Backtracking?
|
Re: Sudoku Löser
ja
|
Re: Sudoku Löser
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 |
Re: Sudoku Löser
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... |
Re: Sudoku Löser
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. |
Re: Sudoku Löser
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 |
Re: Sudoku Löser
weiss nicht. hast du eine lösung dafür?
|
Re: Sudoku Löser
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 |
Re: Sudoku Löser
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... |
Re: Sudoku Löser
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. |
Re: Sudoku Löser
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? |
Re: Sudoku Löser
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 |
Re: Sudoku Löser
Hallo Hagen,
das ist schon klar. Das ist ja gerade der Witz. Es gibt keine Lösung. Die Frage ist wie lange brauchst das Lösungsprogramm, um das herauszufinden. MfG Thorsten |
Re: Sudoku Löser
Schon beim Eintippen der Zahlen in meinen Sodoku Solver hat dieser erkannt das es nicht gehen kann. Dh. mein Solver überprüft schon beim Laden des Games das es nicht gehen kann. Er macht dies einfach per logischer Analyse der Abhängigkeiten. Übrigens kannst du die Sourcen meines Solvers hier in der DP finden.
http://www.delphipraxis.net/internal...oduko&start=26Gruß Hagen |
Re: Sudoku Löser
Ja stimmt, habe mir mein Beispiel nochmal angesehen. Da sieht man schon gleich das es nicht gehen kann.
Folgende Variante ist da besser... 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 1 | 0 | 0 | 2 | 0 | 0 | 3 | 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 0 | 3 | 4 | 2 | 0 | 0 | 0 0 | 4 | 0 | 5 | 0 | 1 | 0 | 6 | 0 0 | 0 | 0 | 9 | 6 | 7 | 0 | 0 | 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 0 | 7 | 0 | 0 | 8 | 0 | 0 | 9 | 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 Dein Programm ist super. Dort wird leider diese Problematik gar nicht zugelassen. Das heisst man kein deinem Programm gar kein ungültiges Sudoku unterjubeln. Das ist ja ok. Ist allerdings nicht das was ich meinte. Aber ist natürlich auch eine Lösung. MfG Thorsten |
Re: Sudoku Löser
Hi Thorsten,
naja das Ziel im Sodoku ist es ja nur durch reine logische Überlegung das Game zu lösen. Dh. die Trial&Error Methode und das Backtracking sind unter Sodoku-Solvern verpönt. Auch Rätsel die mehrere Lösungen haben sind verpönt. Und da ist mein Solver noch nichtmal ein besonders guter (ok besser als viele andere die nur Trial&Error benutzen). Es gibt im WEB Solver die jede bekannte logische Taktik anwenden, was meiner definitiv nicht kann. Wichtig ist eben nur das schon die logischen Regeln was geht und was nicht gehen kann in der Gameengine integriert sind, eben wie in meinem Solver. Davon mal abgesehen: warum soll ein Sodoku Solver überhaupt versuchen ein per Definition unlogisches Rätsel lösen zu wollen ? Gruß Hagen |
Re: Sudoku Löser
Hallo Hagen,
ja natürlich. So sehe ich das ja auch. Nur hier werden immer wieder solche Solver veröffentlicht (was ich als gute Übung sehe) und ich bin bei meinem eigenen eben genau auf das Problem der ungültigen Sudokus gestoßen. Und da war einfach nur die Frage wie löst man das. Wenn man nämlich so einen einfachen Solver hat, dann kann man den nach einem Tag abbrechen und man hat immer noch keine Lösung. Ok es gibt auch keine - und da war ja setzt nun genau meine eigentlich Frage. Kann man das schneller herrausfinden als da Tage rumzuprobieren. Wenn man das so wie in deinem Programm gar nicht erst zulässt, ist das ja auch eine super Lösung. Meine Intention war ja nur mal darauf aufmerksam zu machen, was passiert bei einem ungültigen Sudoku? Weiter war nichts. Zu deinem Edit... Warum soll man ungültige Sudokus lösen? Na ganz einfach, wenn ich mich z.B. bei diesem Solver in der Input.txt Datei vertippe, versucht der Solver da eine Woche etwas zulösen. Nur um dann irgendwann mal festzustellen, das es keine Lösung gibt. Das wäre doch schöner wenn man das schneller wüste. Ausserdem, wenn ich das nicht so löse wie du, also eine ungültige Situation erst gar nicht zulasse ist ja alles ok, aber so wie bei dem hier vorgestellen Solver gibt es keine solche Kontrolle. Also was passiert im worst case? Zitat:
Ich weiss das sind nur theoretische Fragen. Aber warum kann ich sie nicht stellen? Ist doch nur eine Frage. Grüsse Thorsten |
Re: Sudoku Löser
Hi Thorsten,
Zitat:
Gruß Hagen |
Re: Sudoku Löser
Zitat:
Gruß Jörg |
Re: Sudoku Löser
Zitat:
mein Programm benötigt 0 Millisec. Gruß, Andreas |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 14:44 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz