Superior99
Grünschnabel
Hallo,
ich bin gerade erst auf diese Seite aufmerksam geworden und muss sagen, ich bin begeistert. Einen kleinen Vorstellungsbereich fänd ich gut, hätte ich nämlich direkt genutzt, aber da ich keinen gefunden habe (oder ich hab einfach noch keinen Überblick), seid mir nicht böse, wenn ich direkt mit der Tür ins Haus falle mit meinem Anliegen. Ich werde demnächst mit Sicherheit des öfteren wieder reinschauen und meine anfängliche Einseitigkeit versuchen wieder auszubügeln.
Also es geht um folgendes:
Ich versuche einen Algorithmus herauszufinden, der möglichst effizient Zahlen- bzw. Logikrätsel der Art "Wolkenkratzer" bzw. auch "Skyscrapers" berechnen kann.
Ziel des Ganzen ist eine implementierung in Prolog, um die es hier aber eigentlich nicht geht, sondern nur um die grobe herangehensweise. Der Programmiertechnische Teil sollte kein Problem mehr für mich darstellen, jedoch würde ich mich über Hilfe beim knobeln freuen. Denn manchmal steht man einfach zu dicht vor der Wand, um etwas zu erkennen.
Also wie diese Rätsel aussehen, werde ich mal lieber nicht mit eigenen Worten erklären, denn besser als auf der folgenden Seite kann man es wohl nicht umschreiben und ich möchte jetzt auch nicht fremd zitieren.
Das ganze macht übrigens auch spaß mal selbst durchzuspielen, anfänglich sollte ein 4x4 Feld ausreichen und es hilft auch dem Spielverständnis.
Hier der Link: http://www.janko.at/Raetsel/Wolkenkratzer/
Mein erster Ansatz für einen Algorithmus wäre, bruteforcemäßig jedem kleinen Feld eine Variable zuzuordnen und diese mit den anderen Variablen und den ganzen Bedingungen zu prüfen. Sicherer Weg um auf eine Lösung zu kommen nehme ich an, jedoch eine exponentiell steigende Fehlerquote und Berechnungszeit machen diese Methode recht unbrauchbar, zumindest in ihrer Grundfassung.
Natürlich könnte man dies reduzieren, wenn man z.B. dort wo eine 1 am Rand steht gleich das höchste Haus setzt und ähnliches.
Anderer Ansatz von mir ist die Gleichsetzung aller Höhen auf 1 und eine Schrittweise erhöhung der Variablen unter jeweiligen Test mit allen Bedingungen. Durch Backtracking sollte dies auch recht leicht umzusetzen sein, allerdings ist auch hier eine lange Rechenzeit von nöten.
Nun halt meine Frage an ein paar helle Köpfe, ob jemand eine Idee hätte wie man dieses Spiel am effektivsten algorithmisiert.
Wäre über jeden noch so kleinen Hinweis sehr erfreut.
Mit freundlichen Grüßen
Superior
ich bin gerade erst auf diese Seite aufmerksam geworden und muss sagen, ich bin begeistert. Einen kleinen Vorstellungsbereich fänd ich gut, hätte ich nämlich direkt genutzt, aber da ich keinen gefunden habe (oder ich hab einfach noch keinen Überblick), seid mir nicht böse, wenn ich direkt mit der Tür ins Haus falle mit meinem Anliegen. Ich werde demnächst mit Sicherheit des öfteren wieder reinschauen und meine anfängliche Einseitigkeit versuchen wieder auszubügeln.
Also es geht um folgendes:
Ich versuche einen Algorithmus herauszufinden, der möglichst effizient Zahlen- bzw. Logikrätsel der Art "Wolkenkratzer" bzw. auch "Skyscrapers" berechnen kann.
Ziel des Ganzen ist eine implementierung in Prolog, um die es hier aber eigentlich nicht geht, sondern nur um die grobe herangehensweise. Der Programmiertechnische Teil sollte kein Problem mehr für mich darstellen, jedoch würde ich mich über Hilfe beim knobeln freuen. Denn manchmal steht man einfach zu dicht vor der Wand, um etwas zu erkennen.
Also wie diese Rätsel aussehen, werde ich mal lieber nicht mit eigenen Worten erklären, denn besser als auf der folgenden Seite kann man es wohl nicht umschreiben und ich möchte jetzt auch nicht fremd zitieren.
Das ganze macht übrigens auch spaß mal selbst durchzuspielen, anfänglich sollte ein 4x4 Feld ausreichen und es hilft auch dem Spielverständnis.
Hier der Link: http://www.janko.at/Raetsel/Wolkenkratzer/
Mein erster Ansatz für einen Algorithmus wäre, bruteforcemäßig jedem kleinen Feld eine Variable zuzuordnen und diese mit den anderen Variablen und den ganzen Bedingungen zu prüfen. Sicherer Weg um auf eine Lösung zu kommen nehme ich an, jedoch eine exponentiell steigende Fehlerquote und Berechnungszeit machen diese Methode recht unbrauchbar, zumindest in ihrer Grundfassung.
Natürlich könnte man dies reduzieren, wenn man z.B. dort wo eine 1 am Rand steht gleich das höchste Haus setzt und ähnliches.
Anderer Ansatz von mir ist die Gleichsetzung aller Höhen auf 1 und eine Schrittweise erhöhung der Variablen unter jeweiligen Test mit allen Bedingungen. Durch Backtracking sollte dies auch recht leicht umzusetzen sein, allerdings ist auch hier eine lange Rechenzeit von nöten.
Nun halt meine Frage an ein paar helle Köpfe, ob jemand eine Idee hätte wie man dieses Spiel am effektivsten algorithmisiert.
Wäre über jeden noch so kleinen Hinweis sehr erfreut.
Mit freundlichen Grüßen
Superior
