Autor |
Beitrag |
LLCoolDave
      
Beiträge: 212
Win XP
Delphi 2005
|
Verfasst: Do 18.05.06 08:15
Wer dieses Japanische Puzzle nicht kennt, findet eine kurze Erklärung auf Wikipedia: de.wikipedia.org/wiki/Nonogramm
Diese Rätsel haben mich seit langem in ihren Bann gezogen, und ich würde gerne einfach einmal einen Solver dafür schreiben.
Meine bisherige Idee ist:
-Erstelle eine Liste aller möglichen Anordnungen für eine Zeile/Spalte
-Schmeisse die Einträge aus der Liste, die mit der bisherigen Spielsituation nicht verträglich sind (also ein schon als schwarz eingetragenes Feld wäre weiß etc.)
-Bilde die Schnittmenge aller übrigen Einträge, und trage diese ein (ist also ein Feld in allen möglichen Anordnungen Schwarz, so wird es als schwarz eingetragen)
-Gehe zur nächsten Zeile/Spalte
-Laufe abwechselnd Zeilen und Spalten durch
-Nach jedem Vollständigen Durchgang wird ein Abbild des Spielfeldes gemacht und mit dem vorherigen verglichen. Sind sie identisch ist das Puzzle entweder gelöst oder nicht eindeutig lösbar
Dass dieser Algorithmus zum Ziel führen würde, bin ich mir recht sicher, jedoch würde er auch Ewigkeiten brauchen, weil z.B. bei einem 15*15 Feld die Zeile 2 3 2 sehr viele Möglichkeiten hat, und diese erst alle aufzustellen, um dann eh den Großteil rauszuwerfen, wirkt für mich unpraktisch.
Ach, da fällt mir gerade eine Lösungsmöglichkeit ein: Am Anfang werden einmal alle Möglichen Anordnungen aufgestellt für jede Zeile und Spalte und gespeichert. Diese Menge wird dann bei jedem Zug als Ausgangsmenge genommen. Wenn etwas im vorherigen Zug schon nicht ging, wird es in Zukunft auch nicht mehr gehen. Das sollte das Ganze deutlich beschleunigen.
Fällt vielleicht sonst noch jemandem eine Optimierung oder ein besserer Ansatz ein?
|
|
digi_c
      
Beiträge: 1905
W98, XP
D7 PE, Lazarus, WinAVR
|
Verfasst: Do 18.05.06 08:35
Aha, scheinen ja interessant zu sein.
Ich bin nur ein schlechter Algorithmierer aber ich würde vorher die Elemente ausschließen, die 0 haben und somit unbelegt sind. Ich glaube gut ist es, wenn man bei den Zeilen/Spalten anfängt, die die größten Nummern haben da da ja am wenigsten Permutationen(sind das überhaupt welche?) haben. Dann würde ich deren Nachbarfelder angehen, da diese dann ja auch eindeutiger werden...
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Do 18.05.06 09:06
Ganz billig, 'ziemlich' langsam, aber sicher zum Ziel führend ist hier mal wieder das gute, alte Backtracking. Man erzeugt einfach alle Kombinationen und gelangt somit automatisch zum Ziel.
Das ist die gute Seite.
Es kann einige Sekunden dauern. Auch bis zu 2000000000000. Oder noch etwas länger.
Das ist die schlechte Seite.
Jetzt kommt der gesunde Menschenverstand in Form von Heuristiken daher. Gibt es nicht einfache Regeln, die bestimmte Kombinationen von vorneherein ausschließen, oder einzelne Reihen/Spalten schon eindeutig vorbelegen können? Da es sich um ein Logikrätsel handelt, das ein Mensch in endlicher Zeit schaffen kann, und es nur eine Lösung gibt, sollte man so vorgehen:
Ein Feld kann drei Zustände annehmen: Schwarz, Weiss, oder Unbekannt. Alle Felder haben zunächst die Belegung: 'Unbekannt'.
Dann:
Algorithmus "Ermittle Lösung" - Liefert 'Fertig', oder 'es gibt keine Lösung':
0. Wenn alle Felder ausgefüllt sind, ist das die Lösung (Das Resultat ist 'Fertig')
1. Ermittle die Reihe/Spalte, mit der geringsten Anzahl möglicher Kombinationen (=N).
2. Wenn N=0, gibt es keine Lösung (Das Resultat des Algorithmus ist "Keine Lösung").
3. Wenn N=1, färbe die Felder entsprechend und gehe zu 1.
4. Wenn N>1 mache weiter mit Schritt 5.
5. Färbe die Felder nacheinander entsprechend den Kombinationsmöglichkeiten
6. Für jede Kombinationsmöglichkeit, führe "Ermittle Lösung" aus, das Resultat sei R
7. Wenn R='Fertig', ist das Resultat auch 'Fertig' (beende den Algorithmus)
8. Mache den 'Zug' (5) wieder rückgängig und mache weiter der nächsten Kombination.
_________________ Na denn, dann. Bis dann, denn.
|
|
LLCoolDave 
      
Beiträge: 212
Win XP
Delphi 2005
|
Verfasst: Do 18.05.06 11:56
Ich will ja nichts dagegen sagen, aber ich habe persönlich meine Zweifel ob diese Backtracking variante z.B. auf einem 50x50 Feld auch nur in annähernd brauchbarer Zeit abläuft. Ich könnte sie ja trotzdem mal Probieren, halte aber instinktiv meinen Ansatz für besser, da jedes Feld, das eingetragen wird, auch mit Sicherheit richtig ist, sofern eine Lösung besteht. Bei dem Backtracking Verfahren stellt sich mitunter erst nach einer hohen Tiefe heraus, dass der Ansatz bei der aller Ersten Reihe bereits falsch war, was zu einer Wahnwitzigen Rekursion führen würde. Andererseits ist mein Ansatz wohl bei 50x50 auch nicht alzu schnell. Ich werde mal versuchen, beides nacher umzusetzen, mal sehn was die besseren Resultate liefert.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 18.05.06 12:28
Hallo,
wie bei Wiki gesagt gibt es auch nicht eindeutige.
Man denke nur an eine Diagaonale in einem NxN-Feld hat N! Moeglichkeiten.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| X1111 1...o 1..o. 1.o.. 1o... Oder X1111 1o... 1..o. 1.o.. 1...0 etc... |
Trotzdem witzige Seite
puzzle.geoweb.ge/contact.htm
Etwas muss man auch beachten wenn dort eine 10 steht, bedeutet das 10 Felder sind am Stueck belegt, was die Sache extrem vereinfacht, da man nur Startkoordinate Richtung(v,h) Anzahl braucht.
Zwei Zahlen in einer Spalte uebereinader bedeutet, diese sind durch mindestens ein Feld getrennt
3 4 bedeutet das die 4 immer mindestens 4 hinter dem Startpunkt von 3 ist.
Das muss ich mir mal zu Gemuete fuehren
Gruss Horst
|
|
LLCoolDave 
      
Beiträge: 212
Win XP
Delphi 2005
|
Verfasst: Do 18.05.06 12:48
Prinzipiell sind nichteindeutige Nonogramme eher sinnlos, weil sie meistens Bilder darstellen, was ja bei nicht eindeutiger Anordnung nicht möglich ist.
Habe gerade mal versucht meinen Ansatz umzusetzen, der ist jedoch an etwas gescheitert, das ich bisher nicht bedacht hatte: Wie erstelle ich am einfachsten alle zulässigen permutationen für jede Zeile/Spalte? Hat mir da jemand nen guten Tipp, mir fällt gerade keine sinnvolle Vorgehensweise ein.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 18.05.06 13:18
Hallo,
es gibt keine Permutation einzelner Punkte, was ich im editierten Bereich sagen wollte.
Es gibt nur eine Anordung der Startpunkte
eine zeile einer beliebigen Spalte sei
3 4->das heisst ein 3-er Block wird von einem 4-er Block mit mindestens einem Abstand gefolgt
Gerechnet
X1*_+N1*o+X2*_+N2*0
Wobei N1=3 N2=4 und
X1 0..Summe[i=1..k] Ni - k = Start leere Stellen _
X2 = So, das mindestens eine Stelle hinter N1 und maximal N2 in der letzten Spalte endet.
Fuer 34 ergeben sich nur ein paar Moeglichkeiten = (Anzahl der leeren Stellen)!, hier also 3!=6
Quelltext 1: 2: 3: 4: 5: 6: 7:
| :X?????????? 34:000___0000 34:000__0000_ 34:000_0000__ 34:_000__0000 34:_000_0000_ 34:__000_0000 |
Gruss Horst
|
|
digi_c
      
Beiträge: 1905
W98, XP
D7 PE, Lazarus, WinAVR
|
Verfasst: Do 18.05.06 13:20
Also die "leere" Zeile/Spalte ist ein 1 dimensionales Array. Und dann vielleicht
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| for i:= 0 to 10 begin for j:= 0 to AnzZuBelegendeZeichen begin if j<10 then begin zeile[i]:='#'; end else begin zeile[j-i]:='#'; end; end; end; |
Aber ob das so alles stimmt weiß ich nicht, bin da nicht so begabt
Ich fände es schön, wenn mal gemand einen Solver baut, wo man step by step die einzelnen Schritte sehen kann(welches Feld wird analysiert,...).
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Do 18.05.06 13:29
Mit ein bisserl Backtracking, womit sonst?
Sei S die Liste der Blocklängen (z.B. 1,2,4) dann ist es doch so, das erst ein Block der Länge 1 irgendwo ist, dahinter ein Block der Länge 2 und dahinter ein Block der Länge 4, oder?
Ich benötige zur Lösung also nur ein Array of 'Vektor P', wobei P[i] der Startpunkt des Blockes der Länge S[i] ist.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| Procedure CreateCombinations (S, I,K,Row, P) Begin For J := K to Board.Width - 1 do If IsBlock(Board[Row, J], S[i]) Then If I = Length(S) Then AddToCombinations (P + [J]) else CreateCombinations (S,I+1, J+S[j]+1, P+[J]) End; |
Ist natürlich pseudocode: P+[J] soll bedeuten, das an den Vektor P der Wert 'J' angehängt wird.
'AddToCombinations (P : Vektor)' fügt den Vektor P an die Liste der Kombinationen an.
Der Aufruf geht so:
CreateCombinations (S,0,0,Row,[]);
'[]' soll eine leere Liste darstellen.
_________________ Na denn, dann. Bis dann, denn.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 18.05.06 13:56
Hallo,
ich habe mal (Java aktiviert) puzzle.geoweb.ge/onl...ine_nonogram-001.htm zu loesen probiert.
Die erste Zeile kann man sofort einfuellen , da genau 2 Freistellen vorgegeben sind.
Damit hat man sofort die Startpunkte der ersten Senkrechten Bloecken.
Hinter UND vor jedem Block das Feld in Fahrtrichtung ( zeichenrichtung  ) kann man als nicht belegbar markieren.
Es sieht fuer mich als Nichtspieler so aus, das eine Kombination aus abwechselndem zeilen,spaltenweise eintragen schneller zum Ziel fuehren koennte, was meint der Autor des Threads.
Welche Loesungsstrategien gibt es?
Gruss Horst
Edit
Man kann bei langen Bloecken auch vorher einen sicher Bereich festlegen.
Wenn 10 STellen frei verfuegbar sind und ein 9er Block dahinein soll, kann man die erste und letzte Stelle als ungewiss markieren und die acht mittendrin als sicher.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 18.05.06 16:30
Hallo,
man kann sogar eine Studienarbeit daraus machen:
page.mi.fu-berlin.de...hindle/projekte.html
Gruss Horst
|
|
LLCoolDave 
      
Beiträge: 212
Win XP
Delphi 2005
|
Verfasst: Do 18.05.06 16:35
Also, nochmal zur Erklärung, das wäre mein Lösungsansatz:
Zunächst wird für jede Zeile und Spalte eine Liste aller Möglichen Einträge erstellt.
Dann werden abwechselnd alle Zeilen, dann alle Spalten, durchgelaufen. Tritt nach einem vollständigen Durchlauf keine Änderung mehr ein, ist der Solver am Ende seiner Kräfte angekommen: Entweder, weil das Puzzle fertig ist, weil es nicht eindeutig lösbar ist, oder weil mein Verfahren vielleicht doch nicht 100% funktioniert.
Dabei geschieht bei jeder Zeile/Spalte folgendes: Die einzelnen Elemente der Zeile werden durchlaufen. Ist bereits etwas eingetragen, werden alle Möglichkeiten aus der Liste herausgeschmissen, die in diesem Feld etwas anderes stehen haben, da diese für eine Lösung nicht in Frage kommen. (Alle im Spielfeld markierten Felder haben sich zwingend logisch ergeben). Ist die Zeile so komplett durchlaufen, befinden sich in der Liste nur noch Möglichkeiten, die auf die aktuelle Spelsituation passen. Anschließend wird geprüft, ob für eines der freien Felder in allen Möglichkeiten der selbe Wert steht. Wenn ja, ergibt sich dieser als logisch zwingend für das Feld und wird im Spielfeld eingetragen.
So weit, so gut. Das einzige was mir bei diesem Ansatz Probleme bereitet, ist das Erstellen der Liste mit allen Möglichkeiten. Ich hab mir dafür zwar im Chemieunterricht etwas überlegt, das wirkt aber so ineffektiv und langsam, dass ich es vorerst für mich behalten will. Der Ansatz mit den Vektoren scheint interessant zu sein, ich kann ihn nur leider nicht ganz nachvollziehen, eine Erklärung wäre nett, weil das ganze recht einfach und effektiv zu sein scheint.
PS: Was auf Wikipedia nicht erwähnt wurde, es gibt auch mehrfarbige Nonogramme, mit etwas anderen Regeln. Ich habe jedoch berechtigte Zweifel, das mein Lösungsansatz auch in diesem Fall funktioniert, da die Mehrfarbigkeit auch andere logische Ansätze erlaubt, die mein Lösungsalgorithmus schlicht übersieht. (Z.B.: Wenn es nur ein einziges rotes Feld gibt, ist dies durch den Schnittpunkt der Zeile und Spalte, die den Roten Block enthalten, eindeutig bestimmt. Mein Algorithmus übersieht meines erachtens diese Begebenheit schlicht und einfach. Mitunter ergibt sich aber nur durch eintragen dieses Feldes ein logisch zwingender Lösungsweg für das Nonogramm.)
Edit: Mmh, hab die Studienarbeit nur überflogen, aber meinen Lösungsansatz hab ich darin nicht entdeckt. Daher interessiert mich nun erst recht, ob mein Algorithmus alle eindeutigen Nonogramme löst.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 18.05.06 17:13
Hallo,
www.comp.lancs.ac.uk...s/nonogram/fmt2.html findet sich vielleicht ein Dateiformat, mit dem man etwas fuer Testprogramme anfangen kann, sodass man hier etwas einheitliches verwendet.
Damit hat man dann einheitliches Testnonogramme bis 100x100 :
www.comp.lancs.ac.uk...onogram/puzzles.html
Somit kann man sich jetzt ein internes Datenformat ueberlegen.
maxrule gibt ja maximale Anzahl von Abschnitte in Zeile oder Spalte an.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| tRule = record rules :array[1..maxrule] of integer; startpt :array[1..maxrule] of integer; rulesCnt : integer; fixedlength: integer; fixedrule [1..maxrule] of boolean; end;
tSpalte = array[1..weidth] of tRule; tZeile = array[1..height] of tRule; |
Das Spielfeld hat mehrere Moeglichkeiten:
unbelegt,garantiert belegt,garantiert frei
Hat jemand dazu ergaenzende Vorschlaege?
Gruss Horst
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Do 18.05.06 17:35
LLCoolDave hat folgendes geschrieben: | ADer Ansatz mit den Vektoren scheint interessant zu sein, ich kann ihn nur leider nicht ganz nachvollziehen, eine Erklärung wäre nett, weil das ganze recht einfach und effektiv zu sein scheint. |
Kein Problem. Ich mach das mal für Reihen. Für Spalten ist es ja das Selbe in Grün.
Meine Routine findet nun alle Kombinationen, in einer Reihe die Blöcke mit einer bestimmten Folge von Blocklängen zu setzen. Die Blocklängen sind in B, wobei B ein Vektor (Array) ist. Sagen wir, B= (1,2,4). Wir suchen also alle Möglichkeiten, in einer Reihe (Breite = W) diese Blöcke zu plazieren.
Eine Möglichkeit ist P, wobei P wieder ein Vektor ist. z.B. P= (0,3,9). Dann fängt der 1er Block bei Spalte 0 an, der 2er Block bei 3 und der 4er Block bei 9. Daneben gibt es ja noch weitere Möglichkeiten, die stehen dann in dem Lösungsvektor L hintereinander. Z.B.:
L = ( (0,3,9), (1,4,9) )
Es gibt dann zwei Möglichkeiten in dieser einen Reihe die Blöcke mit der Länge 1,2 und 4 zu plazieren, nämlich an den Positionen 0,3 und 9 sowie an 1,4 und 9.
Ich probiere einfach alle Möglichkeiten, den 1.Block zu plazieren. Für die rekursive Lösung ersetze ich 'alle' durch 'nächste'. Also nochmal...
Ich suche die 'nächste' Möglichkeit, den 1.Block zu plazieren. Ich fange also bei 0 an. Nehmen wir an, an Position J habe ich einen freien Platz. Also kommt J in meinen Lösungsvektor P an die 1.Stelle, denn der 1.Block (Länge = 1) könnte an Position J kommen. Alle folgenden Blöcke müssen mindestens ab Position J+<Länge 1.Block>+1 anfangen. Wenn ich keinen folgenden Block mehr habe, habe ich ja eine Möglichkeit gefunden.
Wie man sieht, sagt ein Code mehr als 1000 Worte:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| Procedure FindRowCombinations (B : TPosArray; aRow, aBlockIndex, aStartPos : Integer; P : TPosArray); Var J, iThisBlockWidth : Integer;
Begin iThisBlockWidth := B[aBlockIndex]; For j:=aStartPos To Board.Width - iThisBlockWidth Do If Board.CanPutABlockAtPos (J,iThisblockWidth) Then Begin P[aBlockIndex] := J; If aBlockIndex = Length (B) Then Begin Solutions.Add (P); End Else FindRowCombinations (B, aRow, aBlockIndex + 1, J + iThisblockWidth + 1, P); End End; |
Ehrlich gesagt glaube ich, das mein Ansatz besser ist. Aber nur deshalb, weil Ich bei deinem Ansatz nicht durchblicke  . Vermutlich gibt es immer eine Reihe/Spalte, die eindeutig zu belegen ist. Nachdem dies geschehen ist, fängt mein Algo ja von vorne an und sucht wieder eine R/S, die eindeutig zu belegen ist. Zum Schluss bleiben (bei einem gemeinen Nonogramm) vielleicht ein paar R/S übrig, die alle mehre Möglichkeiten haben, die Gesamtanzahl der zu prüfenden Möglichkeiten dürfte aber minimal sein. Und erst dann setzt das Backtracking an. Die gleiche Strategie führte bei Sudoku zum Ziel. Das Backtracking wurde da nur bei mehrdeutigen Sudoku's (die per definitionem Keine sind) angeworfen.
Lass uns doch einfach die Lösungen vergleichen.
_________________ Na denn, dann. Bis dann, denn.
|
|
F34r0fTh3D4rk
      
Beiträge: 5284
Erhaltene Danke: 27
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: Do 18.05.06 17:46
das wollte ich als nächstes projekt, verdammt, da war einer schneller 
|
|
LLCoolDave 
      
Beiträge: 212
Win XP
Delphi 2005
|
Verfasst: Do 18.05.06 17:52
Schneller? Ich hab keine einzige Zeile Code
Naja, erst dachte ich ich habs verstanden, und jetzt bin ich wieder verwirrt. Ist das da jetzt eine Lösung zum finden aller möglichen Anordnungen in einer Spalte/Zeile oder gleich eine Idee für das Lösen eines ganzen Nonogramms?
Naja, meine Idee war folgende:
Es wird festgestellt, wie viele leerstellen in einer zeile/spalte zu vergeben sind. Einfach Zeilenlänge - Summe der Blocklängen - Anzahl der Blöcke +1. Dann wird diese Restleerzeichenzahl einfach in allen möglichen Summenzerlegungen auf die Anzahl der Blöcke + 1 möglichen Plätze verteilt, in denen sie stehen können. Daraus kann ich mir dann auch die Liste aller Möglichkeiten generieren.
Nur die Startstellen der Blöcke anzugeben ist für meinen Algorithmus unbrauchbar, aber beim Eintragen in die Lösungsmenge kann das ganze ja bereits umgeschrieben werden, finde deinen Ansatz jetzt auch besser, auch wenn ich ih noch nicht ganz verstanden hab (hab heute Denkblockade XD). Damit mach ich mich vielleicht nacher nochmal ran an das Problem.
|
|
Jetstream
      
Beiträge: 222
|
Verfasst: Do 18.05.06 19:41
Moin moin,
ich versuch mich auch mal an deinem Algo, ist natürlich nur ein Ansatz
Gehen wir mal davon aus, wir haben ein zweidimensionales Array aus Integern von der Größe
des Feldes, das die möglichen Färbungen darstellen. Eine Null steht dabei für "nicht eingefärbt",
eine Eins für "eingefärbt" und eine Zwei für "steht noch nicht fest".
Dann brauchen wir noch zwei Arrays, die die Abschnitte angeben, dort sollte sowas wie "4 2 1" oder "3" stehen können.
Dafür könnte man zwei Arrays aus LinkedLists, oder einfach wieder zweidimensionale Arrays aus Integern nehmen.
Pseudo-Code:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| Schleife: Wiederhole das so lange, bis sich nichts mehr verändert hat:
Schleife: Gehe alle Zeilen/Spalten durch, wenn die Anzahl der eingefärbten Felder der Summe der Elemente des darauf bezogenen Arrays entspricht, setze alle ungewissen Felder auf Null.
Schleife: Gehe alle Zeilen/Spalten durch, wenn die Anzahl der ungewissen Felder der Summe der Elemente des darauf bezogenen Arrays minus der bereits eingefärbten entspricht, setze alle ungewissen Felder auf Eins.
Schleife: Suche nach fertigen Abschnitten im Feld, und setze das Feld hinter dem Abschnitt auf Null. |
Ich weiss nicht, ob mein Ansatz bereits jedes Feld eindeutig löst, aber wenn der Code erst mal implementiert ist
und du ihn an ein paar Beispielen getestet hast, wirst du schnell eventuell vorhandene Grenzen bemerken.
mfg Jetstream
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 19.05.06 09:53
Hallo,
nochmals zur Vereinheitlichung, damit man kooperieren kann, sollte eine sinnhafte Datenstruktur erzeugt werden.
Statt rule koennte man auch Block sagen:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| maxBlkcnt :integer = const tBlock = record BlkLength : integer; StartPos, MinStartPos, maxStartPos :integer; Fixed : Boolean; end; tRowCol = record Blocks : array[1..maxBlkcnt] of tBlock; BlockCnt : integer; Blockfixed: array[1..Blkcnt] of boolean; end;
tSpalte = array[1..weidth] of tRowCol; tZeile = array[1..height] of tRowCol; |
Man kann ja auch statt array[1..maxBlkcnt] of ?? mit dynamischen Feldern arbeiten.
In der Studienarbeit wird auch dass Programm des italienischen Mathematik Professors Maurizio Paolini erwaehnt:
Zitat: |
Der Algorithmus sucht sich die Zeilen oder Spalten mit den geringsten Möglichkeiten der Verteilungen der Blöcke(-> moeglichst wenig >freie< Zwischenraeume(Weite- (Gesamtlaenge der n Bloecke + (n-1){Zwischenraeume})und am besten mit geringer Blockanzahl) und sucht dann Überschneidungen, die keinen Widerspruch zu schon gesetzten Einträgen ergeben.
|
Dies scheint mir eine gute Ausgansgsbasis, um anschliessend Brute-Force darauf loszulassen.
Gruss Horst
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Fr 19.05.06 11:41
Moin
Mein Ansatz, die möglichen Kombinationen zu finden, ist Müll. Vergesst ihn. Ich poste abends vielleicht eine erste Lösung...
_________________ Na denn, dann. Bis dann, denn.
|
|
LLCoolDave 
      
Beiträge: 212
Win XP
Delphi 2005
|
Verfasst: Fr 19.05.06 13:46
Horst_H: Für meinen Ansatz ist die Datenstruktur der Blöcke absolut und völlig ungeeignet. Ich brauch für eine auch nur annähernd effektive Arbeitsweise einen Array für die einzelnen Blöcke in der Spalte/Zeile.
Und da ich das Gefühl habe, das wir sowieso aneinander vorbeiarbeiten, ich will KEIN Bruteforce verwenden. Mir geht es nicht darum, am Ende die Lösung zu haben, sondern ich will heraus finden, ob mein Ansatz a) Die meisten Nonogramme löst bzw b) Alle logisch zwingenden Nonogramme löst. Bei nicht eindeutigen Nonogrammen besteht bei mir absolut kein Interesse, diese sind allerhöchstens aus theoretischer Sicht von Interesse, praktisch finden sie keine Anwendung als Rätsel.
Daher sehe ich in der von Horst vorgeschlagenen Datenstruktur für mich keinerlei Nutzen. Ich habe nichts dagegen, wenn ihr auch an Lösungsansätzen arbeitet, so können wir am Ende unsere Resultate vergleichen, aber mir geht es hauptsächlich darum, zu testen, ob dieser Algorithmus, den ich seit einem guten Jahr im Kopf habe, auch die richtigen Resultate liefert.
Daher vereinfache ich meine Frage bezüglich der Permutationen auf folgende Aufgabenstellung:
Gegeben seien zwei Zahlen m und n. m soll nun auf alle möglichen Weisen in n Summanden (jeder dabei >= 0) zerlegt werden, und alle Permutationen der möglichen Zerlegungen zurückgegeben werden.
Beispiel: m=4 n=3
L=((4,0,0),(0,4,0),(0,0,4),(3,1,0),(3,0,1),(1,3,0),(1,0,3),(0,3,1),(0,1,3),(2,2,0),(2,0,2),(0,2,2),(2,1,1),(1,2,1),(1,1,2))
Hoffe ich habe keine vergessen, aber das Prinzip sollte klar sein.
Edit: Dank eines Freundes habe ich nun einen Algorithmus, der mir alle Möglichkeiten ausgibt, und soweit ich mich an den Algorithmus weiter oben erinnern kann, funktioniert er ähnlich. Angesichts der Tausenden von Möglichkeiten bei größeren Rätseln, ist evt. nur das Speichern der Anfangsstellen eines Blocks effektiver, auch beim berechenen, sollte aber trotzdem am Ende in einen Array oder String umgewandelt werden zwecks Auswertung. Das sind aber Kleinigkeiten, an denen ich auch später noch feilen kann. Laufzeit scheint auch gut zu sein, braucht ca. 0.004 s zum berechnen aller 330 Möglichkeiten für (2,2,1,5) bei einer Zeilenbreite von 20. Jetzt mach ich mich mal an den Rest des Algorithmus.
Edit2: So, das ganze funktioniert jetzt, ist nur alles andere als Benutzerfreundlich. Dafür ist es einigermaßen schnell, ein 20x20 Nonogramm (das schwerste auf Griddlers.net) wird in etwa einer halben Sekunde gelöst, das Problem entsteht bei größeren: Bei dem Berechnen von allen Möglichkeiten für (1,2,1,1,1,1) bei Spaltengröße 30 steigt mein programm mit einer Out of Memory Meldung aus, also muss ich schauen ob ich da vielleicht was verbessern kann, ich kann euch nacher auch mal den Quellcode geben, falls ihr mir dabei helfen wollt. Ich schau nacher mal nach 30x30 Nonogrammen, die keine Zeilen mit 120.000 Möglichkeiten haben  Mal schaun wie mein Programm da abschneidet.
|
|
|