25 July 2012

Geometric problem? A dare to solve I was given.

Problem: How to cross the blue curved line only once through each line segments that make up the drawing (without using the vertices for crossing two at once).

One try could be:
As you can see in this attempt I couldn't cross one of the segments, the one with a red dash.

1st approach: brute force through every possibility. The brute: my pc, 7+ years ago.
I thought about using C or java for this but someone suggested prolog and I liked it because its about exhausting all possibilities and I wouldn't have to type so much (could have used haskell too though).

Modelling: I applied a few labels to figure out what I wanted and needed to translate the rules set out initially.

After a look it seemed all I wanted was to take a short set of domino pieces and make a single line with all of them:
So I typed the following knowledge base in Prolog describing the drawing:

Cross direction 1 Cross direction 2
muro(p1, a0, a1).
muro(p2, a0, a1).
muro(p3, a1, a2).
muro(p4, a0, a2).
muro(p5, a0, a2).
muro(p6, a1, a3).
muro(p7, a1, a4).
muro(p8, a2, a4).
muro(p9, a2, a5).
muro(p10, a0, a3).
muro(p11, a0, a3).
muro(p12, a3, a4).
muro(p13, a4, a0).
muro(p14, a4, a5).
muro(p15, a0, a5).
muro(p16, a0, a5).
muro(p1, a1, a0).
muro(p2, a1, a0).
muro(p3, a2, a1).
muro(p4, a2, a0).
muro(p5, a2, a0).
muro(p6, a3, a1).
muro(p7, a4, a1).
muro(p8, a4, a2).
muro(p9, a5, a2).
muro(p10, a3, a0).
muro(p11, a3, a0).
muro(p12, a4, a3).
muro(p13, a0, a4).
muro(p14, a5, a4).
muro(p15, a5, a0).
muro(p16, a5, a0).
%Helper to test if all elements in the list are diferent
todosdif([_|[]]).
todosdif([H|T]) :- not(member(H,T)), todosdif(T).

 The query, probably could be made faster but I had time so whatever:

?- muro(A,X1,X2),muro(B,X2,X3),B\==A,
muro(C,X3,X4),C\==A,C\==B,
muro(D,X4,X5),D\==A,D\==B,D\==C,
muro(E,X5,X6),not(member(E,[A,B,C,D])),
muro(F,X6,X7),not(member(F,[A,B,C,D,E])),
muro(G,X7,X8),not(member(G,[A,B,C,D,E,F])),
muro(H,X8,X9),not(member(H,[A,B,C,D,E,F,G])),
muro(I,X9,X10),not(member(I,[A,B,C,D,E,F,G,H])),
muro(J,X10,X11),not(member(J,[A,B,C,D,E,F,G,H,I])),
muro(K,X11,X12),not(member(K,[A,B,C,D,E,F,G,H,I,J])),
muro(L,X12,X13),not(member(L,[A,B,C,D,E,F,G,H,I,J,K])),
muro(M,X13,X14),not(member(M [A,B,C,D,E,F,G,H,I,J,K,L])),
muro(N,X14,X15),not(member(N,[A,B,C,D,E,F,G,H,I,J,K,L,M])),
muro(O,X15,X16),not(member(O,[A,B,C,D,E,F,G,H,I,J,K,L,M,N])),
muro(P,X16,X17),
todosdif([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]).

Answer, proximately 2 hours later:
No

So this problem does not have a solution.

Note: This is an old entry re-post of another blog of mine I brought down.

No comments:

Post a Comment