Die Häuser vom Nikolaus

CDW

0
Mitarbeiter
Jeder kennt das Haus vom Nikolaus (eine Figur mus in einem Zug gezeichnet werden - also ohne den Stift abzusetzen oder über eine bereits gezeichnete Linie zu führen) . Aber keiner weiß, dass er inzwischen mehrere davon hat und auch ein schnelleres Fortbewegungsmittel ;)
Können folgende Figuren "in einem Zug" gezeichnet werden?
Code:
                                 /\           /\
                                /  \         /  \
                               +----+       +----+
                               |\  /|       |\  /|
                               | \/ |       | \/ |
      /\            /\   /\    | /\ |       | /\ |
     /  \          /  \ /  \   |/  \|       |/  \|
    +----+        +----+----+  +    +       ......
    |\  /|        |\  / \  /|  |\  /|      /|\  /|\
    | \/ |        | \/   \/ |  | \/ |     / | \/ | \
    | /\ |        | /\   /\ |  | /\ |    /  | /\ |  \
    |/  \|        |/  \ /  \|  |/  \|   /   |/  \|   \
    +....+        +....+....+  +....+  /....+....+....\
Wenn ja, wieviele Möglichkeiten gibt es (auch Spiegelungen usw. zählen mit)?
Euer Programm sollte bei einer Eingabe sagen, ob es eine Möglichkeit gibt und wenn ja, möglichst alle auflisten.

Damit es nicht zur GUI Plackerei ausartet (wer mag, kann natürlich trotzdem eine anbieten ;) ) - einfachkeitshalber kann die Eingabe in solcher Form erfolgen:
Wir bezeichnen einzelne Punkte mit Buchstaben oder Ziffern:
Code:
%                                   G             G
%                                  /\            /\
%                                 /  \          /  \
%                                E----F        E----F
%                                |\  /|        |\  /|
%       E              G   H     | \/ |        | \/ |
%       /\            /\   /\    | /\ |        | /\ |
%      /  \          /  \ /  \   |/  \|        |/  \|
%     C----D        D----E----F  C    D        C....D
%     |\  /|        |\  / \  /|  |\  /|       /|\  /|\
%     | \/ |        | \/   \/ |  | \/ |      / | \/ | \
%     | /\ |        | /\   /\ |  | /\ |     /  | /\ |  \
%     |/  \|        |/  \ /  \|  |/  \|    /   |/  \|   \
%     A....B        A....B....C  A....B   H....A....B....I
Und sagen: von A führt eine Linie nach B, nach D, nach C. Von E führt eine Linie nach D und nach C, von B führ eine Linie nach C und nach D (die nach A haben wir ja schon) usw.
also: Input: punkt(A,B),punkt(A,C), punkt(A,D),punkt(E,D), punkt (E,C), punkt(D,C),punkt(D,B).
Nur als Beispiel - ihr dürft das natürlich gerne variieren (z.B jeden Punkt aufzählen) oder im Programm festkodieren.
Das Programm gibt dann einfach aus, in welcher Reihenfolge man den Stift führen müsste: z.B für das erste Haus: a, b, c, a, d, c, e, d, b
 
Hab mal nen Programm geschrieben. Es gibt 88/3328/624/243712 Lösungen aus. Kann das stimmen?
Oder hab ich wieder die "Koordinaten" falsch eingegeben :D

Source kommt noch... aber erstmal den anderen noch ne Chance geben :P
 
Man, und ich dachte mir, dass ich euch meine Hausaufgaben erledigen lassen kann *Mist*.
Ist ja eine Pein, die Koordinaten einzugeben ;).
B2T: Hab die gleichen Lösungen heraus.

Edit: warum nur so wenig Interesse ?
Man stelle sich vor,es gibt eine Liste mit Knoten und wo diese hin führen:
Code:
%Haus: [k(a,b), k(a,c), k(a,d), k(b,d),k(b,c),k(c,d),k(e,c),k(e,d)]
%      e
%     /\
%    /  \
%  c/____\d
%   |\  /|
%   | \/ |
%   | /\ |
%   |/__\|
%   a     b
nun braucht man einfach die Liste durchzugehen und sich Knoten herauszupicken.
Dann sucht man nach "Verbundknoten" - mit denen also eine Verbindung existiert.
Exisitiert eine Veribindung "durch alle Knoten" hindurch, hat man eine Lösung.
Anzahl aller Lösungen=Anzahl aller Zeichenmöglichkeiten.
Code:
haus(X,[],[X]).                                                                 %wenn alle Knoten abgearbeitet wurden - fertig
haus(X,Knotenliste,[X|Sol]):-select(k(Y,X),Knotenliste,Rest),haus(Y,Rest,Sol).  %sonst, suche einen Knoten raus, der mit X verbunden ist
haus(X,Knotenliste,[X|Sol]):-select(k(X,Y),Knotenliste,Rest),haus(Y,Rest,Sol).
select ist ein Build-In Prädikat(SWI,GNUProlog,Sicstus), welches einen Eintrag auswählt und die Liste ohne den Eintrag zurückgibt. Da man dies ja als Cheaten bezeichen könnte (immerhin ist es nicht in ISO ;) )
einmal ohne Buildins:
Code:
sel(X,[X|Tail],Tail).                                                     %wurde ein Element gefunden - fertig
sel(X,[K|Tail],[K|DeltaTail]) :- sel(X,Tail,DeltaTail).                   %sonst gehe die Liste durch:

haus(X,[],[X]).                                                              %wenn alle Knoten abgearbeitet wurden - fertig
haus(X,Knotenliste,[X|Erg]):-sel(k(X,Y),Knotenliste,Rest),haus(Y,Rest,Erg);  %sonst, suche einen Knoten raus, der mit X verbunden ist
                             sel(k(Y,X),Knotenliste,Rest),haus(Y,Rest,Erg).  %für beide Richtungen (von X nach Y und Y nach X)
Anfrage wäre:
Code:
Anfrage nach Lösungen:
65 ?- haus(_,[k(a, b), k(a, c), k(a, d), k(b, d), k(b, c), k(c, d), k(e, c), k(e, d)],Loesung).

Ausgabe:
Loesung = [a, b, d, a, c, d, e, c, b] ;
Loesung = [a, b, d, a, c, e, d, c, b] ;
Loesung = [a, b, d, c, a, d, e, c, b]
indem man bei der Anfrage haus(_,...) keinen bestimmten Knoten, sondern einen Platzhalter "_" angibt, zwingt man Prolog dazu, alle Möglichkeiten in Betracht zu ziehen. Gibt man einen Knoten an, erhält man alle Zeichenmöglichkeiten von diesem Punkt aus.

Anfrage nach Anzahl:
Code:
Haus=[k(a,b), k(a,c), k(a,d), k(b,d),k(b,c),k(c,d),k(e,c),k(e,d)],
|    findall(Loesung,haus(_,Haus,Loesung),Loesungenliste),length(Loesungenliste,Anzahl).
Ausgabe:
Loesungenliste = [[a, b, d, a, c, d, e, c|...], [a, b, d, a, c, e, d|...] ...],
Anzahl = 88.
 
Einerseits weil ich es gerade erst gesehen habe und zugegebener massen noch keine Ahnung habe wie ich das in ein Programm umsetzten könnte, muss mir mal gedanken machen ob ich nen Lösungsansatz finde. (Von der fertigen Programmierung ganz zu schweigen).

greetz
chris
 
Ob noch was von anderen kommt!?
Ka... aber hier mal mein Source Code:
Code:
#include <iostream>
#include <list>

using namespace std;

class hvn
{
private:
	struct edge
	{
		int a, b, c;
		edge(int _a, int _b) : a(_a), b(_b), c(-1) {}
		edge(edge _e, int _c) : a(_e.a), b(_e.b), c(_c) {}
	};
	list<edge> edges, way;
	list<int> vertices;
	int num;
	void printway(int cur)
	{
		cout << ++num << ". ";
		for (list<edge>::reverse_iterator it = way.rbegin(); it != way.rend(); ++it)
			cout << it->c << "-";
		cout << cur << endl;
	}
	void nextstep(int cur)
	{
		if (way.size() == edges.size())
			printway(cur);
		for (list<edge>::iterator it = edges.begin(); it != edges.end(); ++it) {
			if (it->a == cur || it->b == cur) {
				bool valid = true;

				list<edge>::iterator it2;
				for (it2 = way.begin(); it2 != way.end(); ++it2) {
					if (it->a == it2->a && it->b == it2->b) {
						valid = false;
						break;
					}
				}

				if (valid) {
					way.push_front(edge(*it,cur));
					nextstep((it->a == cur)?it->b:it->a);
					way.pop_front();
				}
			}
		}
	}
public:
	void addEdge(int a, int b)
	{
		edges.push_front(edge(a, b));
		vertices.push_front(a);
		vertices.push_front(b);
	}
	void calc()
	{
		vertices.sort();
		vertices.unique();
		num = 0;
		for (; !vertices.empty(); vertices.pop_front())
			nextstep(vertices.front());
		cout << num << " Loesungen." << endl;
	}
};

int main()
{
	cout << "Das \"Haus vom Nikolaus\" und seine Verwandten." << endl;

	hvn x;

	for (;;) {
		cout << "Jeweils zwei Punkte (Zahlen), die mit einer Linie verbunden sind (Strg-D für Ende):" << endl;
		int a, b;
		if (! (cin >> a >> b))
			break;
		x.addEdge(a, b);
	}
	x.calc();
}
 
Auch in Prolog:
Code:
solveNikohaus([], Location, Way, Acc):- Acc = [Location|Way].
solveNikohaus(LeftList, Location, Way, Acc):-
    (select(con(Location, Dest), LeftList, RestList);
     select(con(Dest, Location), LeftList, RestList)),
    solveNikohaus(RestList, Dest, [Location|Way], Acc).

solve(Solution):-
    Knodes = [con(a, b), con(b, d), con(d, e), con(e, c), con(c, a),  con(a, d), con(d, c), con(c, b)],
    solveNikohaus(Knodes, _, [], Solution).

solve(Start, Solution):-
    Knodes = [con(a, b), con(b, d), con(d, e), con(e, c), con(c, a),  con(a, d), con(d, c), con(c, b)],
    solveNikohaus(Knodes, Start, [], Solution).
Code:
?- solve(R).

R = [b, c, d, a, c, e, d, b, a] ;

R = [b, c, a, d, c, e, d, b, a] ;

R = [b, c, e, d, a, c, d, b, a] ;

R = [b, c, a, d, e, c, d, b, a]
etc. pp.
Ich komm fürs einfache Haus auch auf 88 Lösungen.
edit: Hm, sieht CWD's Lösung schon gefährlich ähnlich. :|
Aber das ist halt die einfachste/intuitivste Lösung des Problems. (Ihmo).
Mit vordefinierten Fakten für die Knoten und dann wildem rumprobieren aller Möglichkeiten, bis mal ne Verbindung möglich ist (und sich dann noch die gegangenen Verbindungen zu merken), ist im Vergleich zu select doch sehr um die Ecke.


EDIT:
Falls Jemand noch nach nem Lösungsansatz für dieses Problem sucht, mit der richtigen Datenstruktur ist es ziemlich trivial. Die "richtige" Datenstruktur wäre hier eine Adjazenzmatrix, implementiert als 2dimensionales Array.
Mehr dazu hier.
 
In Python:
Code:
from time import time

def solve(edges, currEdge, currVertice, way=[]):
    global sols
    if len(way) == len(edges):
        sols.add("%s" % map(lambda w: w[1], way))
    for nextEdge in edges:
        if currVertice in (nextEdge[0], nextEdge[1]):
            if nextEdge not in map(lambda w: w[0], way):
                nextVertice = nextEdge[1] if nextEdge[0] == currVertice else nextEdge[0]
                if nextVertice not in map(lambda w: w[1], way[-1:]):
                    solve(edges, nextEdge, nextVertice, way + [(currEdge, currVertice)])

def process(edges):
    global sols
    sols = set()
    for currEdge in edges:        
        for currVertice in currEdge:
            solve(edges, currEdge, currVertice)
    return len(sols)

if __name__ == '__main__':
    h1 = [("A","B"),("A","C"),("A","D"),("B","D"),("B","C"),("C","D"),("E","C"),("E","D")]
    h2 = [("A","B"),("A","E"),("A","D"),("B","C"),("B","F"),("B","D"),("C","F"),("C","E"),("F","E"),("F","H"),("E","H"),("E","G"),("E","D"),("D","G")]
    h3 = [("A","B"),("A","D"),("A","C"),("B","D"),("B","C"),("C","F"),("C","E"),("D","E"),("D","F"),("F","G"),("F","E"),("E","G")]
    h4 = [("H","A"),("H","C"),("A","B"),("A","D"),("A","C"),("B","I"),("B","D"),("B","C"),("I","D"),("C","D"),("C","F"),("C","E"),("D","F"),("D","E"),("F","G"),("F","E"),("E","G")]
    for house in [h1, h2, h3, h4]:
        t = time()
        print ">> count: %i\ttime: %.2fs" % (process(house), time() - t)
>> count: 88 time: 0.03s
>> count: 3328 time: 2.99s
>> count: 624 time: 0.48s
>> count: 243712 time: 98.35s

Gruß
Felix
 
Zurück
Oben