PDA

Vollständige Version anzeigen : Aufgabe mit Makro lösen


Eschl
02.09.2017, 16:18
Hallo,
möchte gerne dieses Problem mit VBA lösen:
In ein Raster 8x8 sollen die Zahlen von 1 bis 18 eingetragen werden.
-Zweistellige Zahlen werden in zwei benachbarte Felder eingetragen.
-Die Zahlen dürfen sich nur diagonal berühren.
-Jede nächsthöhere Zahl steht entweder rechts neben der Vorgängerzahl, oder aber in der Zeile unter dieser.
Die Summe der Spalten sind(von rechts nach links): 9,7,15,20,7,8,6,18.
Das ist keine Preis- oder Schulaufgabe. Ich habe ein Makro gebastelt, doch wahrscheinlich nicht optimal, nach ein paar Stunden Laufzeit habe ich abgebrochen. Kann mir jemand helfen?
Gruß, Eschl

aloys78
02.09.2017, 16:43
Hallo Eschl,
Jede nächsthöhere Zahl steht entweder rechts neben der Vorgängerzahl, oder aber in der Zeile unter dieser.
Verstößt das nicht gegen die Regel der diagonalen Berührung.

Stell mal ein Beispiel-Raster zur Verfügung, wie das praktisch aussieht (die Spaltensummen brauchen da natürlich noch nicht nicht Deinen Vorgaben zu entsprechen) sowie Deinen bisherigen Lösungsansatz.

Und woher nimmst Du die Zuversicht, dass diese Aufgabe entsprechend Deinen Vorgaben lösbar ist ?

Gruß
Aloys

Eschl
02.09.2017, 18:20
Hallo,
man stelle sich ein Schachbrett vor. Dann könnte auf auf a8,b8...oder h8 die Zahl "1" stehen.(die Zahlenwerte steigen von links nach rechts und von oben nach unten. Falls die "1" auf d8 stehen sollte, darf auf d7,e8 und c8 keine Ziffer stehen. auf e7 und c7 könnten welche stehen, müssen aber nicht. Meine Zuversicht entnehme ich der Tatsache, dass mein Makro 4 Zeilen schafft, ohne die Summen zu beachten. Mein Lösungsansatz: 64 Variabeln einsetzen. Dann Zeile für Zeile mit: For Each Variable in Array("x",1,2,3) für die erste Zeile. Hier könnte unter anderen der String "xx1x2xxx" entstehen. Der wird mit Split in ein Feld umgewandelt. Das Feld ist hier F=array(1,2). Dann habe ich eine Funktion, welche die richtige Verbindung zwischen den Zeilen bewerkstelligt. Der erste nummerische Wert in der nächsten Zeile ist genau mit 1 größer, als der letzte Wert in der vorigen Zeile. "x" für die leeren Felder. Eine Funktion, welche prüft, ob links, rechts,oben unten von der Variabeln sich keine andere befindet. Die Anzahl der "x"(Füller):64-27=37.
Eschl

Eschl
03.09.2017, 13:25
Hallo,
ein Beispiel:
Zeile 1: 1x2x3x4x
Zeile 2: x5x6xxx7
Zeile 3: 8x9x10xx
Zeile 4: xxxxxx11
Zeile 5: 12x13xxx
Zeile 6: xxxxxx14
Zeile 7: 15xx16xx
Zeile 8: xx17xx18
Gruß, Eschl

Oge
03.09.2017, 16:57
Hallo Eschl,

A) lösbar?
Die wichtigste Frage von aloys hast du noch nicht beantwortet.
Und woher nimmst Du die Zuversicht, dass diese Aufgabe entsprechend Deinen Vorgaben lösbar ist ?

B) zu deinem Ansatz
Wenn du schon einen richtigen Algorithmus hast kannst du ihn ja einmal hochladen. Vielleicht lässt sich durch programmtechnische Änderung die Laufzeit verkürzen. Ich halte zB die Nutzung einer Zeichenkette für den Inhalt einer Zeile für sehr ungünstig. Hier wäre ein 8*8 Array wohl besser.

C) erste Überlegungen für einen anderen Algorithmus
1) Auf jeden Fall recursiv vorgehen
2) Wahrscheinlich ist es besser von hinten (18) nach vorne (1) zu arbeiten, da ich bei zweistelligen Zahlen schneller vorwärtskomme.
3) Durch überprüfen folgender Bedingungen bei jedem möglichen Eintrag den recursiven Baum kürzen.
a) prüfen, ob die Spaltensumme nicht schon überschritten ist oder -in der ersten Zeile- auch wirklich richtig ist.
b) prüfen, ob die aktuelle Position für die aktuelle Zahl nicht schon zu weit oben/vorne ist. Dafür vorher für die Zahlen (bei den ersten x genau) das früheste Auftreten ermitteln.
(zB: 5:Z2S1; 10:Z3:S5; 11 Z4S1)

Oge
04.09.2017, 20:04
Hallo Eschl,

woher ist denn die Aufgabe?
Man kann auch ohne Programm einfach nachweisen, dass die Aufgabe nicht lösbar ist.
Mich hatte das "von rechts nach links" direkt gewundert.
Eine Summe von 18 ist in der ersten Spalte nicht möglich.

Eschl
04.09.2017, 20:32
Hallo Oge,
das sollte natürlich "von links nach rechts" heißen.
Eschl

Oge
05.09.2017, 14:30
Hallo Eschl,

da du auf unsere bisherigen Fragen nicht geantwortet hast, gehe ich davon aus, dass du nur an der Lösung interessiert bist.

Hier die eindeutige Lösung (auf meinem Rechner benötigt das Programm ca 0,03 Sekunden).

x,1,x,2,x,x,3,x
x,x,4,x,5,x,x,6
7,x,x,8,x,x,x,x
x,x,9,x,x,x,1,0
1,1,x,x,1,2,x,x
x,x,1,3,x,x,1,4
1,5,x,x,1,6,x,x
x,x,1,7,x,x,1,8

ps. Wenn man die Summenprüfung der Spalten wegläst ermittelt das Programm 6389 mögliche Kombinationen in 3,6 Sekunden.

Eschl
05.09.2017, 20:24
Hallo Oge,
Der Weg ist das Ziel. An der Lösung bin ich überhaupt nicht interessiert, meine Absicht war:"möchte gerne dieses Problem mit VBA lösen". Um die Frage, die "euch" so sehr beschäftigt zu beantworten: Das Problem wirst du nirgendwo finden, denn es ist von mir selber konzipiert. Leider gehst du von der falschen Voraussetzung aus, dass ich an dem Programm nicht interessiert bin.
VG, Eschl

Oge
06.09.2017, 13:18
Hallo Eschl,

na dann in der Anlage ein Lösungsbeispiel.

Das Programm ist so aufgebaut wie im Beitrag #5 "C) erste Überlegungen für einen anderen Algorithmus" beschrieben.

Da ich jetzt das Programm nach der ersten gefundenen Lösung abbreche, benötigt es auf meinem Rechner jetzt ca 0,01 Sekunden.
Die richtige Lösung ist ja am Anfang der Suche (18 ganz hinten) .

Eschl
06.09.2017, 16:28
Hallo Oge,
zunächst vielen Dank für das Programm. Es ist sicher kein Geheimnis, dass dahinter ein schwereres Aufgabe steckt. Dieses beinhaltet mehr Zeilen und mehr Spalten. Zahlen von 1 bis N. Nun verstehe ich zu wenig von Userform, um das anzupassen. Was muss ich ändern, um mit den neuen Daten eine Lösung zu finden? Auch hier sind Spaltensummen angegeben.
Viele Grüße, Eschl

Oge
06.09.2017, 17:00
Hallo Eschl,

A) zu:Nun verstehe ich zu wenig von Userform, um das anzupassen.
Diese Aussage habe ich nicht verstanden. Wofür sollte man eine Userform nutzen?

B) Ansonsten
habe ich nur verstanden: Was muss ich ändern wenn sich was ändert?
Ohne genauere Spezifikation der mögliche Änderungen kann ich nichts sagen.
Im Programm ist zur Zeit neben der Anzahl der Werte, Zeilen und Spalten auch fest eingebaut, dass die zweistelligen Werte eine 1 vorne haben.

Eschl
06.09.2017, 19:02
Hallo Oge,
Die 1 als ersten Wert der zweistelligen Zahlen bleibt bestehen. Habe versucht, meine Werte einzugeben, doch wegen "Außerhalb des gültigen Bereichs" klappt es nicht. Die Werte 8,8,18 sind im neuen Fall verändert. Erster Wert: Zeilenanzahl, zweiter Wert Spaltenanzahl und dritter Wert größte Zahl. (die kleinste bleibt 1) Auch die Summen sind andere. Die könnte ich in der Tabelle ändern. Die Bedeutung der Werte in der Liste mit den Summen, habe ich nicht verstanden. Das mit der UserForm kommt von der Ausgabeform des Ergebnisses. Da habe ich wohl etwas falsch verstanden. Das Maß des jetzigen Aufgabe ist 8x8 und erlaubt nicht mehr Einträge, als 64. Das neue Raster hat die Form eines Rechteckes, da es mehr Spalten, als Zeilen beinhaltet.
Eschl

Eschl
08.09.2017, 16:56
Guten Tag,
ich stelle jetzt mein Makro ein, um dem Wunsch von Aloys entgegen zu kommen. Das Makro braucht zwar nur 2,5 Sekunden bis zur Lösung. Das ist deswegen, weil ich praktisch zu wenige Möglichkeiten offen gelassen habe.
Zur Erinnerung. In ein Raster mit 7 Zeilen und 9 Spalten sollen die Zahlen von 1 bis 16 eingetragen werden. Diese Demo weicht etwas ab von der ursprünglichen Aufgabe. Die Zahlen steigen im Wert genau mit 1. Von oben nach unten und von links nach rechts. Ich denke, da kann man einiges optimieren. Die Summen der Spalten sind im Code definiert.
Gruß, Eschl