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

Zitat von Superior99

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.

Herzlich willkommen auf tutorials.de

Dir kann geholfen werden: http://www.tutorials.de/smalltalk/36...gruessung.html
Und keine Angst, die meisten haben hier mit einer Frage angefangen

Ich nehme mal an, dass es wie bei Sudoku keine Lösung in polynomialer Zeit dafür gibt.
Das einzige was man machen kann, um "Bruteforce" etwas zu verbessern, wäre Backtracking.

Zitat von Nico Graichen

Dir kann geholfen werden: http://www.tutorials.de/smalltalk/36...gruessung.html
Und keine Angst, die meisten haben hier mit einer Frage angefangen

Danke, ich werde da im laufe des Abends vorbei schauen.

Zitat von CPoly

Ich nehme mal an, dass es wie bei Sudoku keine Lösung in polynomialer Zeit dafür gibt.
Das einzige was man machen kann, um "Bruteforce" etwas zu verbessern, wäre Backtracking.

Also da ich das ganze ja in Prolog implementieren will, ist das mit dem Backtracking quasi von Hause aus schon gegeben, da Prolog selbst so arbeitet. Aber es müsste dennoch einige Kniffe geben, wie man das ganze beschleunigen kann. Ich bin zum Beispiel gerade dabei herauszufinden, in welchen Relationen welche Bedingungen gelten. Beispiel bei einem 5x5 Feld, wo 5 von 5 Häuser sichtbar sind, ist die Lösung ja trivial ersichtlich. Sind 4 von 5 zu sehen, kann das 5er Haus nur auf dem vorletzten oder letzten Feld stehen. Da dort vor 3 kleinere Häuser sein müssen, kann die 4 nicht auf Feld 1 oder 2 stehen.

Ich denke solche Regeln können die Anzahl der fehlerhaften Backtracks schon ernorm reduzieren, frage ist dann halt eher, welche Regeln sind alle aufstellbar ohne das Ergebnis zu verfälschen und machen sie das Programm später sogar effizienter oder bewirken sie vllt sogar das Gegenteil?

Weitere nützliche Eigenschaften von Prolog wären das Arbeiten mit Listen und das rekursive aufrufen der Prädikate, jedoch hab ich da noch keine besonderen Ideen gehabt, wie man diese Features für den Algorithmus schlau einsetzen könnte.

Danke aber soweit für eure Antworten.

lg