Flaschenproblem

Hallo. ICh habe mal eine Frage. ICh bin dabei dieses Problem zu lösen. Ich soll es in C# programieren. Vllt kann mir ja einer von euch helfen. Es soll eine Konsolenanwendung werden die alle möglichen ergebnisse am Ende ausgibt.Ich habe schon ein Array angelegt welches das Raster dastallen soll. Aber ich komme nicht im geringsten weiter. Würde mich über antworten freuen.

MfG Sinio

Hallo Sinio und Herzlich willkommen,

Ich mach Dir mal einen Vorschlag, versuch es ersteinmal alleine und wenn du Irgendwelche spezifischen Fragen zu diesem Problem hast kannst du gerne wieder auf dieses Forum zurückgreifen, jedoch ohne eine wirklich Frage zu stellen und unter umständen zu erwarten, dass dir hier einer die Lösung niederschreibt wird dir von unseren meisten mitgliedern keine Antwort erfolgen.

Verstehe diese Beitrag bitte nicht falsch, wir hlefen gerne jedoch muß auch ein wenig eigeninitiatieve von Dir ausgehen.

EDIT
Schreibe doch mal genau auf wo dein Problem liegt und was du bisher schon rausgefunden hast

mfg

Hallo Sinio,

da es m.E. recht schwer ist, ein Schlussfolgerungssystem zu realisieren (so nach dem Motto in der untersten Zeile sind 10 Flaschen von denen genau 9 gefüllt sein müssen, also muss eine von den 10 leer sein und da insgesamt nur eine leer sein darf, müssen alle Flaschen weiter oben gefüllt sein), bleibt eigentlich nur das mehr oder weniger intelligente, systematische Ausprobieren aller Möglichkeiten, die die Rahmenbedingungen einhalten.

herbivore

Hallo Sinio

auf den ersten Blick sieht das ganz doch aus wie ein gleichungssystem

natürlich erst mal händisch, ob natürlich die Gravitation dabei so einfach zu berücksichtigen ist, ist ne andere Frage aber an deiner stelle würde ich es erst einmal in diese richtung versuchen weiter zu verfolgen.

ich würde mich freuen, wenn du uns deinen Lösung mal kurz aufschreibst wenn du es gelöst hast

mfg

Das klingt doch nach einem Backtracking-Problem.
Wurde vor kurzem auch in der c't am Beispiel von Sudoku erläutert.

1. Dr. Michael Hund, Harald Bögeholz (bo)
   Zeigerhüpfen
   Backtracking mit verketteten Datenstrukturen
   Know-how,Backtracking,Dancing Links, DLX, c't-Puzzle, Sudoku, Monte Carlo, Donald E. Knuth
   c't 20/06, Seite 218

Original von blackcoin
auf den ersten Blick sieht das ganz doch aus wie ein gleichungssystem

Mitm Gleichungssystem ist gar net so einfach wies scheint. Problem ist das du im schlimmsten Fall 100 Unbekannte hast bei 10*10 Raster aber nur 20 Gleichungen.

Die leeren Felder zwischendrin vereinfachen das, trotzdem wird das per Hand immer noch nichts. Wenn man irgendwie die Tatsache mit de Gravitation reinbringt dann müsste das System schon eindeutiger werden, aber immer noch alles andere als leicht.

Hallo zusammen,

ich habe das Teil mal von von Hand gelöst und da macht man sich dauernd sowas zu nutze, dass z.B. in der vierten Spalte in der oberen Flasche mindestens 4 und in der unteren mindestens 3 Einheiten enthalten sein müssen und andersherum, dass in der zweiten Spalte die beiden oberen Einheiten der oberen Flasche und die obere Einheit der unten Falsche leer sein müssen. Weiß nicht, ob sowas auch für die automatische Lösung hilft.

herbivore

Hmm, auf der seite sind ja die Lösungen angegeben. Hatte vorher net auf deine Formulierung geachtet das es mehrere Lösungen gibt. Dann kann man den Gleichungssystemansatz natürlich vergessen weil der nicht eindeutig ist.

Ich würds einfach mit der Brechstange machen, einfach einsetzen und probieren. Das dürfte alles andere als die Optimallösung sein, aber de rPc dürfte trotzdem schnell zu Lösungen kommen 😉

Hmm, auf der seite sind ja die Lösungen angegeben. Hatte vorher net auf deine Formulierung geachtet das es mehrere Lösungen gibt. Dann kann man den Gleichungssystemansatz natürlich vergessen weil der nicht eindeutig ist.

nicht eindeutig lösen aber es kann einem der lösung erheblich näher bringen

mfg

Imo ist das ein ganzzahliges Optimierungsproblem und damit NP-schwer. Also wird ein "cleveres Durchprobieren" nicht um Klassen schlechter sein als ein optimales Lösungsverfahren.
Weil ganzzahlige Optimierung NP-schwer ist, muss dieses Problem hier nicht auch unbedingt NP-schwer sein. Aber für mich sieht es doch ähnlich genug aus, um das erstmal anzunehmen. Außerdem sind die meisten interessanten Rätsel NP-schwer 😁

Man muss nur die Zeilen- und Spaltensummen als Schranken verstehen, und für zwei Teile einer Flasche die Schranke einfügen, dass das obere Teil höchstens so viel enthält wie das Teil direkt darunter. Dann ist es nur noch formale Umformarbeit das ganze als ganzzahliges lineares Maximierungsproblem sauber auszuformulieren.

Wenn man die Zeilen und Spaltensummen als Gleichungssystem betrachtet und lösen will (z.B. über gaußsche Eliminationsverfahren), bekommt man einen ganzen Raum möglicher Lösungen. Da muss man dann erstmal alle rausfinden, die ganzzahlig sind (was mit ggT gut möglich sein müsste), und dann alle finden, die die Schwerkraftsbedingung erfüllen.

Hol dir Prolog für .NET(P# glaube ich). Damit sollten solche Lösungen ein Kinderspiel sein.

Allerdings ist es, wenn du nur die Prolog-Klasse einbindest wohl kein richtiges C#-Projekt mehr.

Grüße, Christoph