Autor Beitrag
LLCoolDave
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 212

Win XP
Delphi 2005
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 212

Win XP
Delphi 2005
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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.
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 212

Win XP
Delphi 2005
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: Do 18.05.06 13:20 
Also die "leere" Zeile/Spalte ist ein 1 dimensionales Array. Und dann vielleicht

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
//soviele Durchläufe wie es Zeichenpositionen je Zeile gibt
for i:= 0 to 10 //Anzahl der Positionen
begin
 //
 for j:= 0 to AnzZuBelegendeZeichen
 begin
  if j<10 then 
  begin
    zeile[i]:='#';
  end
  else
  begin //bei Überlauf von vorne beginnen
    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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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.

ausblenden 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 // An Pos (Row,J) kann ein Block der Länge S[i] sein
      If I = Length(S) Then // Der letzte Block wurde gefunden
        AddToCombinations (P + [J])// Der Lösungsvektor P + [J] ist eine Möglichkeit
     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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 212

Win XP
Delphi 2005
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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.
ausblenden 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;  //Wieviele sind es wirklich
          fixedlength: integer;//fest eingefuegt 
          fixedrule [1..maxrule] of boolean;//fest eingefuegt 
       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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Do 18.05.06 17:35 
user profile iconLLCoolDave 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:
ausblenden 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]; // so einen Block wollen wir plazieren
  For j:=aStartPos To Board.Width - iThisBlockWidth Do
     If Board.CanPutABlockAtPos (J,iThisblockWidth) Then Begin
       P[aBlockIndex] := J;
       If aBlockIndex = Length (B) Then Begin // Der letzte Block wurde plaziert
         Solutions.Add (P);  // Also ist P eine Möglichkeit und kommt zum Lösungsvektor
       End
       Else // Ansonsten versuchen wir, den nächsten Block zu plazieren
         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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Do 18.05.06 17:46 
das wollte ich als nächstes projekt, verdammt, da war einer schneller :)
LLCoolDave Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 212

Win XP
Delphi 2005
BeitragVerfasst: Do 18.05.06 17:52 
Schneller? Ich hab keine einzige Zeile Code :P

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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 222



BeitragVerfasst: 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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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:

ausblenden 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,       //als Laufvariable von min bis max
            MinStartPos,
            maxStartPos :integer;
            Fixed       : Boolean; //oder MinStartpos=MaxStartPos machen
          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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 212

Win XP
Delphi 2005
BeitragVerfasst: 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.