AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Sudoku

Ein Thema von NicNacMan · begonnen am 22. Aug 2005 · letzter Beitrag vom 15. Apr 2007
Antwort Antwort
Seite 1 von 4  1 23     Letzte » 
Benutzerbild von NicNacMan
NicNacMan
Registriert seit: 28. Mai 2004
hi,

diese sudoku rätsel aus japan dürften inzwischen bekannt sein
(sonst einfach mal googlen Bei Google suchenSudoku).

ich hab mich mal an einem kleinen prog versucht, das diese rätsel lösen soll.
die einfachen schafft es ohne probleme, aber bei den schweren,
wo sich die möglichen wege verzweigen muss man immer noch per hand nachhelfen.
da werde ich mich aber demnächst nochmal dran versuchen.

würde mich über verbesserungsvorschläge zu funktionen,
design, aber auch zum code freuen.

thx nicnacman

[edit]
ich hab nur eine komponente verwendet: RakUndoRedo
für die rückgängig funktion
[/edit]
Miniaturansicht angehängter Grafiken
sudoku_207.gif  
Angehängte Dateien
Dateityp: zip sudoku_demo_179.zip (301,7 KB, 629x aufgerufen)
Dateityp: zip sudoku_source_169.zip (21,0 KB, 572x aufgerufen)
The Double-Crunch-Peanuts!
SwapIt:
 
Benutzerbild von faux
faux

 
Turbo Delphi für Win32
 
#2
  Alt 22. Aug 2005, 19:47
Wow, nicht schlecht!
Ich bin auch grad dabei sowas zu programmieren (seit ein paar Tagen), weil ich dieses Rätselch ziemlich lustig finde...
Was du noch verbesseren könntest wäre, dass man auch mit den Horizontalen Pfeiltasten Navigieren kann.
Was ich besonders cool finde, ist die Funktion "Mögliche Werte anzeigen".
Faux Manuel
  Mit Zitat antworten Zitat
Benutzerbild von sECuRE
sECuRE

 
Delphi 7 Professional
 
#3
  Alt 22. Aug 2005, 20:24
Hi,

solche Programme gibt's schon zuhauf. Von Sudoku Solver (nur Lösen) bis zu Simple Sudoku (erstellen, helfen, lösen). Was mich interessieren würde, wäre ein Sourcecode, wie man diese Rätsel selbst generiert. Sowas gibt's zwar bisher, aber nur in VB (börks) und Javascript (ähem..). Denkanstöße sind willkommen .

cu
  Mit Zitat antworten Zitat
Benutzerbild von NicNacMan
NicNacMan

 
Delphi 2005 Personal
 
#4
  Alt 22. Aug 2005, 21:21
@faux: thx, die idee mit den cursor tasten ist gut, werds morgen mal versuchen.

@sECuRE: nimm doch n fertiges rätsel, und vertausche dann einzelne zeilen bzw spalten mit anderen, aus dem selben block (1 mit 3, 2 mit 1, 5 mit 6, usw. aber nicht 2 mit 9 oder 3 mit 4, ...).
kannst es auch drehen, oder spiegeln. dann musst du nur noch n paar felder wieder weg machen, wobei dann aber die richtigen stehen bleiben müssen, damit es noch eindeutig zu lösen ist.
  Mit Zitat antworten Zitat
Benutzerbild von sECuRE
sECuRE

 
Delphi 7 Professional
 
#5
  Alt 22. Aug 2005, 21:28
Hi,

Sinn und Zweck des Programms wäre es, meine Homepage automatisch mit neuen, selbstgenerierten Sudokus zu füllen - da mag ich nicht jeden Tag ein vorhandenes Rätsel einfügen .

cu
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins
 
#6
  Alt 22. Aug 2005, 21:28
Das benutzerinterface ist gelungen

Aber du solltest das so machen, dass die Pfeiltasten in die jeweilige Richtung navigieren (oben/unten) und nach Eingabe ein Feld nach rechts gegangen wird

Ach, und wenn nur eine Zahl in ein Feld reinkann, warum nicht gleich automatisch einsetzen ?
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH
 
#7
  Alt 22. Aug 2005, 22:46
@NicNacMan:

kannst du deinen Algorithmus zum Lösen solcher Gitter mal genauer beschreiben ?

Was ich bis jetzt an deinem Source erkennen konnte ist das er rein kombinatorisch alle Lösungen versucht durchzutesten. Das dürfte aber in diesem Falle ziemlich ineffizient sein. Man kann nämlich schon von Anfang an bestimmte Ausschlußannahmen treffen.

Desweiteren ist mir aufgefallen das deine Datenstrukturen, sprich dein Datenhandling sehr ineffizient ist. Statt eigene und auf Effizienz getrimmte Datenstrukturen zu benutzen, benutzt du Strings und ständige String Konvertierungen. Diese Funktionen sind enorm langsame Vertreter für solche Probleme.

Als aller erstes solltest du also anfang eigene und effizentieren Datenstrukturen aufzubauen. Zb.

Delphi-Quellcode:
type
  TFieldNumber = (1..9);
  TFieldNumbers = set of TFieldNumber;

  TField = record
    PossibleNumbers: TFieldNumbers;
    ActualNumber: TFieldNumber;
   ... etc. pp.
  end;
Nun kannst du als allererstes vor dem .Solve() das Spielfeld analysieren. Im obigen Link das erst Game hat zb. in Spalte 4 senkrecht die Zahlen 1,3,4,9,2,5 schon gesetzt, also fest. Es verbleiben nur 3 freie Felder in denen die Nummern 6,7,8 reinpassen können. Aber in der Zeile 5 findet man schon die 6 im mittleren 3x3 Kasten, ergo kann dort eben nicht die 6 stehen sondern nur 7 oder 8. Man kann also herausfinden:

1.) mit welcher Zeile/Spalte dein Suchalgorithmus beginnen muß, nämlich mit der Spalte/Zeile die die geringsten Zugmöglichkeiten zulässt.
2.) zu jedem Feld in deinem Brett kannst du wie oben schon angedeutet von Anfang an ermitteln welche Zahlen überhaupt möglich wären und welche sozusagen von vorhinein ausgeschlossen werden müssen. Im obigen Type -> TField.PossibleNumbers würden diese drinnen stehen. Dies Taktik reduziert enorm die Anzahl der möglichen Kombinationen die dein Algo. druchprobieren muß.

So, nun zum Suchalgo. Dieser sollte sozusagen parallel arbeiten. Das bedeutet, statt immer eine komplette Kombination eines Spielanfanges bis zum maximalen Ende durchzutesten geht man Parallel vor. Dabei muß man aber die Möglichkeit haben
1.) eine ganze Reihen von Kombinationsmöglichkeiten als Zugreihenfolge zu speichern
2.) gleiche Kombinations-Wege auszuschließen, also nicht doppelt/mehrfach zu berechnen
3.) jeder Kombinations-Möglichkeit ein Punktezahl zu vergeben die angibt wie wahrscheinlich man ausgehend von dieser Startkombiantion eine gültige Lösung finden kann

Der Suchalgo. initialisiert nun eine bestimmte Anzahl solcher Suchwege, und legt diese als Objekte in einem Priority Stack ab. Die Priorität welche dieser vielen Kobinationen nun einen/oder mehrere Schritte weitergerechnet werden häng von deren Punktezahl ab. Nach diesen par Schritten wird dieser Such-Weg anhand seiner Punktezahl neu im Priority Stack geordnet. Somit erhalten also diejenigen Such-Wege eine höhere CPU-Zeit und ergo Such-Tiefe die mit höherer Wahrscheinlichkeit eine korrekte Lösung finden werden.

Du musst das sogar so machen wenn du zb. kompliziertere Gitter in sehr kurzer zeit lösen möchtest.

Auf alle Fälle mach weiter, such nach besseren Datenstrukturen und Algorithmen, denn zum Erlernen von komplexen Spielmaschinen und eventuell KI's ist dieses Rätsel idel geeignet. Hast du dich schon mal mit genetischen Algorithmen befasst ? Das könnte dir eventuell weiterhelfen.

Gruß Hagen
  Mit Zitat antworten Zitat
Palando
 
#8
  Alt 22. Aug 2005, 23:46
Nettes Program!

Ich hatte ein kleines Problem:
Wenn ich eine Zahl in ein Feld eingegeben habe, wurde manchmal ein noch nicht definiertes Feld konfliktrot gefärbt, weil ers mit der Lösung vergleichen hat (?), ich hatte die Zahl allerdings noch nicht. Das war auf die schnelle nicht reproduzierbar und scheint auch nur zufällig aufzutreten, also nicht bei speziellen Zahlen oder Feldern, wenn man das Rätsel neu lädt.
Kannst ja mal schauen ob du was findest.

Fallses was hilft: Es is auf dem einfachen Feld passiert, die andern hab ich nicht versucht.
Markus
  Mit Zitat antworten Zitat
Benutzerbild von NicNacMan
NicNacMan

 
Delphi 2005 Personal
 
#9
  Alt 23. Aug 2005, 18:07
@sECuRE: du brauchst ja nur ein paar verschiedene, dadurch, dass du die zeilen,... verschiebst und andere werte löschst, erhältst du ja jedes mal ein neues rätsel.

@jfheins: die pfeiltasten stehen schon auf meiner list, aber das automatische ausfüllen macht sinn, thx

@negaH: jo, bis jetzt ist er sehr ineffizient , am anfang werden die möglichen werte für jedes feld aktualisiert,
wobei für jedes feld die reihe, spalte und der 3x3 block durchgegangen wird.

und die sache mit den strings ist leider wahr.
ich hatte die felder anfangs als komponenten, die alle schon zur designtime existierten.
da hatte ich schon die idee statt nem string ein array [1..9] of boolean zu nehmen, aber das ging als komponenteneigenschaft nicht.
und auf die idee mit den teilbereichen und mengen bin ich nicht gekommen .
da werde ich mich dann als erstes mal dransetzen, danke.

zum suchalgo: dafür, dass ich das nur so 4fun gemacht hab, ist das ganze ja doch extrem ausbaufähig...
das "logische" durchgehen der zeilen, spalten, blöcke wäre auf jeden fall die bessere wahl,
demnach müsste ich fast alles nochmal überarbeiten, damit nicht mehr jedes der 81 felder überprüft wird.

hab mich grade mal bei wiki durch die genetischen algorithmen gelesen, ... da werde ich n weilchen brauchen um das richtig zu verstehen.
die theorie ist mir inzwischen etwas klarer, aber ich hab absolut 0 ideen wie ich das umsetzen kann.

aber die sache mit dem priority stack hört sich sehr interessant an, wie kann ich sowas am besten realisieren? (gibts da gute tuts?)
da werde ich mich auf jeden fall als nächstes (gleich nach der datenstruktur) dran machen.
DANKE!


@Palando: es werden auch felder rot gefärbt, in denen kein wert mehr drin stehen kann, weil alle möglichen zahlen schon in der spalte, zeile oder in dem 3x3 block enthalten sind.
wenn du die möglichen werte anzeigen lässt, müsste das feld leer sein.
falls nicht, muss ich nochmal nach fehlern suchen.
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH
 
#10
  Alt 23. Aug 2005, 22:36
Ich habe die Nacht nochmal drüber geschlafen und mich gefragt wie ich es anpacken würde.
Nur mal so als Anregungen:

1.) das Gitter besteht aus 9x9 Cardinal's, jeder speichert Bitcodiert die möglichen Zahlen. D.h. die 1 wäre (1 shl 1) die 2 wäre (1 shl 2) usw. bis (1 shl 9). Dies wäre im grunde identisch mit meinem obigen Vorschlag mit Mengen und Sets zu arbeiten, hat aber einen gravierenden Vorteil diesem gegenüber. Mit solchen Cardinals kann man per Boolscher Algebra, sprich AND, XOR, NOT, OR, viel effizienter nun die Mengen der möglichen Zahlen abfragen.

2.) zu jeder Spalte und Zeile wird parallel zum Gitter ebenfalls ein bitcodierter Cardinal gespeichert. Sobald man also eine Zahl in einer Zelle einfügt/löscht werden diese Spalten/Zeilen Werte ebenfalls per AND/OR aktualisiert.
Du hast also mit diesen Werten die exakte Kontrolle welche Zahlen pro Spalte und Zeile noch frei verfügbar und unbenutzt sind.

3.) zu jedem 3x3 Feld wird ebenfalls ein solcher bitcodierter Cardinal geführt. Auch hier die Grundbedingung das er beim Einfügen/Löschen einer Zahl in einer Zelle entsprechend aktualisiert wird.

4.) der kombinatorische Such-Algortihmus sollte nun absolut deterministisch sein, d.h. komplett ohne irgendwelches Random auskommen. Wird nun eine Countervariable der rekursiven Suchtiefe mitgeführt so indentifiziert diese Countervariable absolut exakt eine gefundene Lösung. Der Suchalgo. könnte nun beginnend mit diesem Counter die logisch nächstfolgende Lösung suchen, usw. usw. Mit dieser Methode ist es also möglich nicht nur eine beliebige Lösung zu finden sondern alle möglichen Lösungen zu errechnen, ohne das man eine auslässt.

5.) ändert man diesen algo so ab das er ohne schon fixierte/vorgegebene Zahlen arbeitet so hast du in fact statt eines Rätsel-Lösungs-Algos einen Rätsel-Erzeugungs-Algo. Dieser Algo kann dann succesive mit Hilfe der Countervariablen ein Rätsel nach dem anderen produzieren.

6.) es ist nämlich für deinen Algo. im grunde egal ob er ein schon bestehendes Rätsel lösen soll oder ob er ein neues Rätsel erzeugen soll. Die Suchstrategie unterscheidet sich in keinster Weise, dereinzigste Unterschied besteht nur darin das in einem Rätsel fixierte Zahlen eingetragen wurden.

Gruß Hagen
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 03:42 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf