Die Mathe-Redaktion - 22.10.2019 16:19 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 775 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » 16 auf einen Streich
Thema eröffnet 2019-06-08 21:40 von
haribo
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2 3 4 5]   5 Seiten
Autor
Kein bestimmter Bereich 16 auf einen Streich
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2019-06-10


Der Algorithmus wird ja schon bei 5x5 nicht fertig, da brauchen wir mit 9x9 gar nicht anfangen, ohne drastische Nebenbedingungen einzufügen wie "Strecke immer weiter bis kein freier Punkt mehr da"

PS ich habe versucht mein Algorithmus etwas aufzubohren, auf dass er auch die mit doppelten Punkten ausgeben soll.
Lt thom3 sollen das insgesamt 41 sein. Ich habe 100 und bin zu faul zum aufmalen und die doppelten suchen und schreibe deshalb einen 'A1 B2, ...' zu HTML / Bild Generator.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, vom Themenstarter, eingetragen 2019-06-11


ich dachte dein program liefert die ersten paar halbwegs schnell, darum die nachfrage nach 9 x 9...

stimmt händisch überprüfen is etwas aufwendig, hier "baeum 1-6 aus #30"
da sind schon 4mal doppelte drin, du müsstest die ver-schnittpunkte mit in die auflistung nehmen, zumindest wenn sie auf ganzzahligen plätzen innerhalb des n x n feldes liegen, dann würden doppelte doch sofort erkannt


also die markierte A5 als verschnittpunkt zwischen
E5 D5 C5 B5,via [A5], B4 C3 D2 E1,im 6. beispiel

ich hab aber wenig ahnung wie sehr dir das dein program verkomplizieren würde

1+2 liegen auf der gleichen k-gruppe
haribo





  Profil  Quote  Link auf diesen Beitrag Link
Benutzertheo
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 08.07.2018
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, eingetragen 2019-06-11


Hallo,

kannst du den Algorithmus besser beschreiben?

Grüße



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2019-06-11


So?
Quelltext meines Programms
C
#include <stdio.h>
#include <time.h>
// https://www.onlinegdb.com/online_c_compiler
/*
   2*2=4  SMAX=3 1.33
   3*3=9  SMAX=4 2.25
   4*4=16 SMAX=6 2.66
   5*5=25 SMAX=8 3.125 */
 
/* neuner Rätsel
 0 1 2
 3 4 5
 6 7 8 */
// Einzige Lösung: 0 4 8, 5 2+, 1 3+, 6 7
 
/* sechzehner Rätsel
 0  1  2  3
 4  5  6  7
 8  9  10 11
 12 13 14 15
 
 1. Lösung: A1 A2 A3 A4, B3 C1, D1 D2 D3 D4, C4 B2, B1 C2, C3 B4
             0  1  2  3 , 6 8+, 12 13 14 15+,11 5+, 4  9+, 10 7
25er Rätsel
 Eine Lösung A1 C2, E5 D5 C5 B5 A5, A2 B1, E1,E2 E3 E4, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3, C3 B3
             0  11 ,24 19 14 9  4 , 1  5,  20 21 22 23, 18 13 8  3,  2  6  10  15 16 17, 12 7
 */
 
#define N 4		                /* Anzahl der Punkte */
#define WU_N 4                  /* Seitenlänge = Wurzel N */
#define SMAX (2*(WU_N-1))		/* Anzahl der Strecken  bei 3*3=9 4, bei 4*4=16 6, bei 5*5=25 8*/
#define LOE_MAX 220             /* Speicherbegrenzung für Lösungsarray */
 
int p0;
int p[N], px[N],py[N];     // Positionen , x, und y Koordinaten des N. Punktes auf der Streckenkette
int ns[N];                 // der Streckenabschnitt zu diesem Punkt ist Bestandteil der x. Strecke
int besetzt[N];
int grund;
 
// int stop[]={0,11,24,19,14,9,4,1,5,20,21,22,23,18,13,8,3,2,6,10,15,16,17,12,7}; // Eine Lösung für debug Zwecke
 
int n_loesung=0;
int loe[150][N];   // Speicher für Lösungen
 
void drucken(int n)
{
  int i;
  if (n==N-1)
     printf(  "%4d. Lösung: ",n_loesung );
  else if (n<N-1)
     printf(  "Lösungteil bis Punkt %d:",n);
  else {
	 int r,loesung, spiegel, rueck;
	 loesung=n/32;
	 r=n-32*loesung;
	 if (rueck=(r>=8))
	   r-=8;
	 if (spiegel=(r>=4))
	   r-=4;
	 printf(  "keine neue Lösung, weil doppelt zu Lösung %d mit %s %s %d Drehungen:", loesung,(rueck) ? "rückwärts,":"", (spiegel)?"gespiegelt,":"", r); }
 
  /*
	for (i=0;i<N;++i)       // Darstellung als Liste der Punkte
	   printf(" %2d", p[i]);
	printf("\n    Strecken:");
	for (i=0;i<N;++i)
	   printf(" %2d", ns[i]);
	printf("\n");  */
 
  n=(n<N)? n+1:N;         // Max Begrenzung und +1 für Teillösung
  for (i=0;i<n;++i)       // Darstellung in Schachnotation mit Komma beim Streckenwechsel
     printf("%c%c%s",'A'+py[i],'1'+px[i], (i<(N-1) && ns[i]!=ns[i+1])?", ":" ");
  printf("\n");
}
 
void set_koo(int n,int pos)
{
	p[n]=pos;
	px[n]=pos-(py[n]=pos/WU_N)*WU_N;
}
 
 
int gleich(int *links, int *rechts)
{
	int i;
	for (i=0;i<N;++i)
	 if (links[i] != rechts[i])
	   return 0;
	return 1;
}
 
int spiegeln(int *a) // an Diagonale 0..N-1
{
	int pos,x,y,i;
	for (i=0;i<N;++i) {
	   pos=a[i];
	   x=pos-(y=pos/WU_N)*WU_N;
	   a[i]=WU_N*x+y; }  // x und y vertasucht
}
 
int drehen(int *a) // 90° mathematisch positiv
{
   int pos,x,y,x_neu, y_neu, i;
   /* Drehmatrix 90° = 0 -1   ==> x_neu=-y   y_neu=x
                       1 0 */
	for (i=0;i<N;++i) {
	   pos=a[i];
	   x=pos-(y=pos/WU_N)*WU_N;
	   /* x_neu=-y+3; y_neu=x wg Drehpunkt nicht in der Mitte sondern bei 0, 0) */
	   a[i]=WU_N*x +(WU_N-1)-y; }
}
 
int doppelt() // Test, ob die Lösung p[0]...p[15] einer vorhandnen Lösung in loe[][] entspricht (gleich wenn gereht oder gedreht + gespiegelt)
{
  int i,x;
  int c[N]; // zu prüfende Lösung
 
  for (x=0; x<n_loesung;++x) {
     for (i=0;i<N;++i)  // kopieren der zu prüfenden neuen Löung
        c[i]=p[i];
 
     for (i=0;i<4; ++i) {  // 0, 90, 180, 270 Grad gedreht
	      if (gleich(loe[x],c))
	         return 32+32*x+i;
	      drehen(c);}
      spiegeln(c);
      for (i=0;i<4; ++i) {     // gespiegelte 90 180 270 360 gedreht
	  	  if (gleich(loe[x],c))
	         return 32+32*x+4+i;
	      drehen(c);   }
 
      for (i=0;i<N;++i)  // kopieren der zu prüfenden neuen Lösung rückwärts
        c[i]=p[N-1-i];
 
      for (i=0;i<4; ++i) {  // 0, 90, 180, 270 Grad gedreht
          if (gleich(loe[x],c))
             return 32+32*x+8+i;
    	  drehen(c);   }
         spiegeln(c);
      for (i=0;i<4; ++i) {     // gespiegelte 90 180 270 360 gedreht
    	  if (gleich(loe[x],c))
    	     return 32+32*x+12+i;
     	   drehen(c); } }
   return 0;
}
 
int strecken(int n)  // Rückgabe 1, wenn unzulässig insb. auch mehr als SMAX Strecken
{
 
   int dx,dy,dx2,dy2,dx3,dy3,quo, a_quo, b_quo;
   int i,x,y;
 
   double a, b, s_x, s_y;
 
 
   if (n<2)       // erste Teilstecke hat keine weiteren Bedingungen
     return 0;
 
    // nur nächste Punkte sind zulässig, bei Überstreichen weiter Punkte: Rückgabe 1
   dx=px[n]-px[n-1];  // Berechnung Steigung des letzten Abschnittes
   dy=py[n]-py[n-1];
 
 /*  ady=(dy<0)? -dy:dy;      // Überstreichverbot
   adx=(dx<0)? -dx:dx;
   if ( (0==ady && adx>1) ||  			 // waagrecht mit Überstreichen
        (0==adx && ady>1) ||			 // senkrecht mit Überstreichen
        (ady==adx && adx>1)  ) 			 // diagonal mit Überstreichen
                                         // NB bei  4x4 ist mit (schräg aber nicht diagonal) kein zweiter Punkt erreichbar. Ab 5x5 müsste man das auch abfangen. Beispiel (a1,e3) wg c2 nicht zulässig
		   i=i; // return 1; // deckt auch Rückwärts-Verbot ab, da keine Lücken entstehen // Verbot deaktiviert weil Sequenz 2 7 15 (1) damit verboten wird
*/
 
   // Fortsetzung ?
   dx2=px[n-1]-px[n-2]; // Steigung des vorletzten Abschnittes
   dy2=py[n-1]-py[n-2];
 
   if (dx2==dx && dy2==dy) {
     ns[n]=ns[n-1];
     return 0; } // Fortsetzung, Anzahl der Strecken bleibt gleich, Abschnitt zum letzten Punkt gehört zur gleichen Strecke
 
   if (2==n){          // Strecke zum 3. Punkt ist,  wenn sie nicht fortgesetzt wurde, zweite Teilstrecke
	   ns[2]=2;        // Eigentlich ns[n]=1+ns[n-1];
	   return 0; }
 
    // Hochzählen neue Strecke?
    /* Hochzählen, es sein denn, ein Zweifachknick kann zusammen geführt werden durch Knickpunkt außerhalb der Punkte. Bedingungen dafür
        Knick beim letzten Abschnitt
        (&& der Schnittpunkt und der Weg zum Schnittpunkt liegt nicht auf einem Punkt)
        && Strecken laufen zusammen */
 
     if (ns[n-1] != ns[n-2]) {  // Knick beim letzten Abschnitt
 
        dx3=px[n-2]-px[n-3]; // Steigung des vorvorletzen Abschnittes
        dy3=py[n-2]-py[n-3];
 
        quo=dy*dx3 - dx*dy3;
 
        if (0!=quo) { // nicht parallel
                    // Bedingung für Strecken laufen zusammen
                    // (1) Schnittpunkt_x = px[n-2] + a dx3  =  px[n-1] - b dx       mit a,b >0 (=Schnittpunkt in Verlängerung)
                    // (2) Schnittpunkt_y = py[n-2] + a dy3  =  py[n-1] - b dy
                    // (3) aus (1) a=( px[n-1] - px[n-2] - b dx) / dx3
                    // (3) in (2)  b=( (py[n-1] - py[n-2]) * dx3 - (px[n-1] - px[n-2]) * dy3 ) / (dy dx3 - dx dy3)
 
           b_quo = ( dy2 * dx3 -  dx2 * dy3); // b = b_qou / (double)quo;
           a_quo = ( dx2 * dy  -  dy2 * dx ); // a = a_quo / (double)quo;
 
           if ( (quo>0)? (a_quo>0 && b_quo>0) : (a_quo<0 && b_quo<0) ) { // Verlängerung der Linien kreuzen sich
			  s_x=(double)px[n-2]+(a_quo*dx3)/((double)quo);
			  if (s_x==0.0 || s_x==1.0 || s_x==2.0 || s_x==3.0 ) {      // Prüfung ob Schnittpunkt auf Gitterpunkt
		          s_y=(double)py[n-2]+(a_quo*dy3)/((double)quo);
		          if (s_y==0.0 || s_y==1.0 || s_y==2.0 || s_y==3.0 )
		             return 1; }                                         // Unzulässig weil auf Gitterpunkt
 
             // Prüfung ob auf dem Weg zum Schnittpunkt ein Gitterpunkt überstrichen wird
              b=b_quo/(double)quo;
              if (b>1)
                 for (i=1, x=px[n-1]-dx,y=py[n-1]-dy;i<b;x-=dx, y-=dy, ++i)  // rückwärts von p[n-1] bis zum Schittpunkt
                    if ((x>=0 && x<WU_N) && (y>=0 && y<WU_N)) // Gitterpunkt
                       return 1;
              a=a_quo/(double)quo;
              if (a>1)
                 for (i=1,x=px[n-2]+dx3,y=py[n-2]+dy3;i<a;x+=dx3, y+=dy3, ++i)   // vorwärts von p[n-2] bis zum Schnittpunkt
                    if ((x>=0 && x<WU_N) && (y>=0 && y<WU_N)) // Gitterpunkt
                       return 1;
 
              ns[n]=ns[n-1];     // keine neue Strecke, weil die Verlängerung [n-3 ,, n-2] sich mit der Verlängerung von [n ,, n-1] kreuzt
              return 0; } } }
 
   return (((ns[n]=1+ns[n-1])>SMAX) ? 1 : 0);  // neue Strecke
}
 
int teiler(int a,int b) // euklidischer Algorithmus Berechnung ggT
{
	while (b!=0) {
		if (a>b)
		    a=a-b;
		else
		    b=b-a; }
    return a;
}
 
 
int uebersprung(int n)
{
	int i,dx,dy,adx,ady, flag;
	// Test ob in der Lösung Punkte übersprungen werden zB A1 D1 überspringt A2, B2
	// Soll senkrechtes, diagonales und schiefes Überspringen erfassen
	// Bei 4x4 ist nur senkrechtes und waagrechtes Überspringen aufgetreten.
	/* dx=0, ady>1 waagrecht
	   dy=0, adx>1 senkrecht
	   adx=ady && adx > 1 diagonal
       adx, ady nicht teilerfremd
       eigentlich verbotene Sprünge A1 D1 können zulässig sein, wenn die Strecke nicht dort lang geht sondern die strecken davor verlängert sind,
       zB Dach:
 
             z2 z3
          A1       D1
       B0             E2
 
       */
 
    for (i=1; i<n;++i) {
		dx=px[i]-px[i-1];  // Berechnung Steigung des letzten Abschnittes
		dy=py[i]-py[i-1];
 
		adx=(dx<0) ? -dx:dx;
		ady=(dy<0) ? -dy:dy;
		if (adx<2 && ady<2)  // Schrittweite 1: kann nicht überschreiten
		  continue;
		flag=0;
		if (adx==0 && ady>1)  // senkrecht
		  flag=1;
		else if (ady==0 && adx>1)  // waagrecht
		  flag=1;
		else if (ady==adx && adx>1)  // diagonal
		  flag=1;
		else if (teiler(adx,ady)>1) // schräg
		  flag=1;
 
		if (flag==0) // keine Überschreitung
		   continue;
		// Test ob Überschreitung zulässig weil Strecke dort nicht lang geht sondern ausgeknickt ist
		if (i<2||i==n-1) // erstes, letztes Teilstück knickt nie aus
           return 1;
		if (i<n-2 && (ns[i+1]-ns[i-2]!=1)) // Überschreitende Strecke ist separate oder durchgehende Stecke (erschlägt alle 4x4 Fälle)
		   return 1; }
    return 0;
}
 
 
 
int try_next_point(int n)
{
	int i;
	if (n==N-1) {             // Letzter Punkt: gibt nur noch einen freien
	  for (i=0;i<N;++i)
	    if (!besetzt[i])
	      break;
	//  if (i<stop[n])  // Debug vorspulen zur einer bekannten Lösung
	//    continue;
	  set_koo(n,i);
	  if (strecken(n))        // Lösung wenn Streckenzahl stimmt, keine Übersprünge, nicht doppelt
	    return 0;
	  if (uebersprung(N))
	    return 0;
 
	  if (!(grund=doppelt())) {
	    for (i=0;i<N;++i)          // Kopieren der Lösung ins Lösungsarray
	      loe[n_loesung][i]=p[i];
	    ++n_loesung;
	    drucken(N-1);
	    if (n_loesung>=LOE_MAX) {
	      printf("Maximale Anzahl speicherbarer Lösungen erreicht\n");
	      --n_loesung;
	      return 0; }
	    return 1;
	    }
  	    else {
		 /* drucken(grund); */   // Ausgabe der als doppelt markierten Lösungen mit Grund
	    return 0; }
    }
 
	for (i=0; i<N;++i) {     // Positions-Schleife für den Punkt n
	   if (besetzt[i])
	       continue;
	   set_koo(n, i);
	   if (strecken(n))
	       continue;
 
       besetzt[i]=n+1; // Punkt besetzen
	   try_next_point(n+1);
	   besetzt[i]=0;   // Punkt freigeben
	}
	return 0;
}
 
void main(void) {
  int i,p0=0;
  time_t startzeit, endzeit;
 
  printf("2019 Programm zur rekursiven Suche nach Lösungen für %d Striche durch %d x %d also %d Punkte\n",SMAX, WU_N, WU_N, N);
  time(&startzeit);
 
  for (i=0;i<N;++i)
    besetzt[i]=0;
 
  ns[0]=ns[1]=1;
  for(p0=0;p0<N;++p0) {       // Schleife für ersten Punkt separat wg Symmetiebedingung
	  set_koo(0,p0);
	  if (px[0]>=(WU_N+1)/2 || py[0]>px[0] ) // nur schräge obere Hälfte des 1. Quartals wg Dreh + Spiegelsymetrie
	     continue;
	  besetzt[p0]=1;
	  try_next_point(1);
	  besetzt[p0]=0;  }
 
  time(&endzeit);
  printf("Laufzeit:%lds\n",endzeit-startzeit);
  scanf("%*s");
 
}
 





  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, eingetragen 2019-06-11


@haribo,
such im Code nach "vorspulen zur einer bekannten Lösung".
als stop array wäre dann einzutragen zB Suchen von ausgehend der ersten Reihe waagrecht bei 5x5: int stop[]={0,1,2,3,4,0,0,0,0,...};
die angegebenen Zahlen sind die Position mit A1=0, A1=2, B1=5 , B2=6,,,E5=24.
Also der erste Punkt (Index 0) auf Position 0(=A1), ich hoffe, es ist klar.



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2019-06-11


Gesamtzahl der Lösungen für 4x4

Jetzt haben wir
- 41 von thom3 im SPON Forum
- mindestens +2 also >=43 von siehe SOP Forum #289 UliBreimaier
- 63 nach ps71
- oder 100 (- ? dopppelte) nach Bäumler



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, vom Themenstarter, eingetragen 2019-06-11


2019-06-11 15:06 - Baeumler16 in Beitrag No. 44 schreibt:
@haribo,
such im Code nach "vorspulen zur einer bekannten Lösung".

nuscht is klar, C is halt derzeit nicht in meinem repoirtoire...

aber dieser tolle ergoogelte 10x10er hier: "www.mathpuzzle.com/dots10x10.gif"

hat mich endlich auf den ersten einmaligen 9 x 9er gebracht:

er ist noch etwas unsortiert... aber hab ich jetzt lückenlos einmalige von 3x3 bis 14x14, alle mit 2(n-1)linien
haribo



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, vom Themenstarter, eingetragen 2019-06-11


möglicherweise kann man ihn systematisch um 2n erweitern?

das hätte den charme damit dann alle bis unendlich x unendlich zu haben
haribo



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, eingetragen 2019-06-11


Geht der Schmettling auch für große n? Dann wäre die Hälfte der Unendlichkeit schon geschafft.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.49, vom Themenstarter, eingetragen 2019-06-11


5/6el der unendlichkeit geht ja schon mit #36
der kann alles ausser der 6er reihe 9;15;21;...;m*6+3;unendlich+3



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.50, vom Themenstarter, eingetragen 2019-06-11


14 x14 geht, der trick ist die blaue linie in ihrer unregelmässigkeit im rechten teil

graphik einzeln anzeigen lassen vergrössert sie etwas!
haribo



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.51, eingetragen 2019-06-12


Beitrag No 36 hier? Da sehe ich nicht, wie damit 5/6 der Unendlichkeit abgedeckt sind.



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.52, eingetragen 2019-06-12


Guten Morgen ;)

Bäumler, leider hatte ich im Überschwang Deine Nachfrage in #29 hier überlesen und kann erst jetzt darauf eingehen.

Ich zeichne mit "CorelDRAW 8", für das ich eine Lizenz besitze.
Damit habe ich auch schon hochpräzise komplizierte Gleispläne für mein Modellbahnhobby erstellt, das ich mit ein paar Teppich-/Parkettbahnern teile. Als Auflösung stelle ich 600 dpi ein, bemühe mich stets um möglichst exakte und schöne Grafiken, wie ich sie einst auch für Ausarbeitungen an der Uni erstellt habe. Einzelne Elemente kann man dann bequem als PNG oder JPG exportieren, und per PDF24Creator werden entsprechende Dokumente erstellt.
Das dient mir aber lediglich zur sorgfältigen Aufbereitung meiner ansonsten flugs von Hand gepinselten Skizzen - als "BackEnd" für einen Algorithmus ist es untauglich.

Beim "A1B2C3D4C4B3A2..."-Grafikkonverter nach HTML kann ich Dir leider nicht helfen. Aber da ist mein Zutrauen in Dich nahezu grenzenlos ;)

Meinen ersten "Schuss" zur topologischen Typenübersicht mit den 40(!) Lösungen werde ich wohl heute im Laufe des Tages hier als PNG einstellen und dann im SPON-Forum darauf verweisen.
Die Arbeit wartet...

Liebe Grüße - auch an [haribo]



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.53, eingetragen 2019-06-12


Konverter ist fertig und poduziert zB aus einem Textfile mit

Spon #289
Uli+1  A1-C2-X-D4-C4-B4-A4-X-A2-B1-X-C1-C2[d]-C3-B3-A3-B2-C1[d]-X-D1-D2-D3
Uli+2  A1-C2-C-D4-C4-B4-A4-X-A3-B2-C1-C2[d]-C3-B3-A3[d]-X-A2-B1-X-D1-D2-D3.

den Text, den man in das jcsahnwaldtsche html (hier) einfügen kann.
solution(120, ['Uli+1'],  300, 330, 60, 80, [[0,0],[3.00,6.00],[3.00,-2.00],[-1.00,2.00],[2.00,2.00],[2.00,0.00],[-1.00,3.00],[2,3]],'');
solution(120, ['Uli+2'],  300, 330, 60, 80, [[0,0],[3.00,6.00],[3.00,-1.00],[0.00,2.00],[2.00,2.00],[2.00,-1.00],[-2.00,3.00],[2,3]],'');

Und sieht dann so aus:

Kann ich bei Bedarf auch als C-File oder .exe zur Verfügung stellen.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.54, vom Themenstarter, eingetragen 2019-06-12


2019-06-12 09:20 - Baeumler16 in Beitrag No. 51 schreibt:
Beitrag No 36 hier? Da sehe ich nicht, wie damit 5/6 der Unendlichkeit abgedeckt sind.


so sieht das aus:


systematische anweisung:
-bei n/n nach oben starten bis a/n
-die diagonale runter bis n/1
-GUZ weiter hineinwickeln bis nur noch ein punkt frei ist
-bei 1/1 eine zweite schnecke nach unten starten
-GUZ reinwickeln bis auch dort nur ein punkt frei ist
- beide freien punkte verbinden und mit den startstrecken der schnecken verschneiden

die formel für die differenz der einzelnen punkte ist in der zeichnung angegeben, jeweils bei der schon angegebenen sechserreihe 3;9;15;21; ergeben sich für dx/dy zwei zahlen die 2 als gemeinsamen teiler besitzen, drum geht die verbindungsgerade u.A. dort durch einen schon besetzten punkt (es ist der mittelpunkt im feld) womit die einmaligkeit gestört wird

die idee der formel für dx/dy stammt von dir bei einer anderen schneckenvariante (irgendwo im spon forum), ich glaube du hattest aber einen fehler in deiner formel(bei y), und damals dann folglich fehlerhaft daraus geschlossen dass für grosse n immer doppelt besuchte punkte sich ergeben müssen... (dein beispiel war n=29... )

n=29 geht aber, sowohl für obige doppelschnecke als auch für deine schnecke, denn für beide schneckengebilde sind die dx/dy abstände der letzten beiden freien punkte bei gleichem n gleich!
haribo


[Die Antwort wurde nach Beitrag No.52 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.55, eingetragen 2019-06-12


Meine aktuell Sammlung als HTML (basierend auf jcsahnwaldt) der 4x4 Lösungen (sortiert nach erstem Punkt, zweitem Punkt ..., entspricht Spiegelonline IQ149 (#275)). Ja es fehlen ein paar.
Neben Dreh/Spiegel/rückwärts sind auch alle Endlinien soweit wie möglich zurückgenommen. Die Liste war eine generierte, die ich manuell reduziert habe. Interessanterweise hat dort auch Uli+1 und Uli+2 gefehlt.
HTML Code
HTML
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>Lösung 4x4</title>
<meta name="viewport" content="initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"/>
<script>
function solution(pos, text, width, height, x0, y0, path, link) {
  const v = document.createElement('canvas');
  v.width = width;
  v.height = height;
  v.style = 'vertical-align: middle;';
  v.title = '(' + path.join(') -> (') + ')';
  const c = v.getContext("2d");
 
  if (link) {
    const a = document.createElement('a');
    a.href = link;
    a.appendChild(v);
    document.body.appendChild(a);
  }
  else {
    document.body.appendChild(v);
  }
 
  const s = 16;
  c.fillStyle = 'black';
  c.font = s + 'px sans-serif';
  c.textAlign = 'center';
  let y = 0;
  for (let line of text) {
    y += s;
    c.fillText(line, pos, y);
  }
 
  const d = 40;
  c.fillStyle = '#80C0F0';
  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      const x = x0 + d * i;
      const y = y0 + d * j;
      c.beginPath();
      c.arc(x, y, 10, 0, 2 * Math.PI);
      c.fill();
    }
  }
 
  c.strokeStyle = 'black';
  c.lineWidth = 2.5;
  c.beginPath();
  let o = null;
  for (let p of path) {
    if (p) {
      const x = x0 + d * p[0];
      const y = y0 + d * p[1];
      if (o) c.lineTo(x, y);
      else c.moveTo(x, y);
    }
    o = p;
  }
  c.stroke();
}
 
</script>
</head>
<body style="font-family: sans-serif">
<h3>
L&ouml;sung 4x4</a>
</h3>
 
 
<script>
 
solution(120, ['   1. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,0.00],[-2.00,3.00],[5.00,3.00],[-1.00,0.00],[1.50,2.50],[3,1]],'');
solution(120, ['   2. Lösung'],  300, 330, 60, 80, [[0,0],[3.00,0.00],[0.00,3.00],[0.00,0.50],[5.00,3.00],[1.00,3.00],[3,1]],'');
solution(120, ['   4. Lösung'],  300, 330, 60, 80, [[0,0],[3.00,0.00],[0.00,3.00],[5.00,3.00],[0.00,0.50],[0.00,4.00],[3,1]],'');
solution(120, ['   5. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,0.00],[0.00,4.00],[0.00,0.50],[5.00,3.00],[0.00,3.00],[2,1]],'');
solution(120, ['   6. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,0.00],[1.50,2.50],[-1.00,0.00],[5.00,3.00],[-2.00,3.00],[2,1]],'');
solution(120, ['  10. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,0.00],[1.00,3.00],[5.00,3.00],[0.00,0.50],[0.00,3.00],[2,1]],'');
solution(120, ['  11. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,0.00],[0.00,4.00],[0.00,1.00],[3.00,1.00],[3.00,4.00],[1,2]],'');
solution(120, ['  12. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,0.00],[0.00,4.00],[0.00,1.00],[3.00,4.00],[3.00,1.00],[1,1]],'');
solution(120, ['  13. Lösung'],  300, 330, 60, 80, [[0,0],[7.00,0.00],[-1.00,4.00],[1.50,1.50],[4.00,4.00],[-2.00,1.00],[3,1]],'');
solution(120, ['  14. Lösung'],  300, 330, 60, 80, [[0,0],[2.00,0.00],[2.00,3.00],[-1.00,3.00],[3.00,-1.00],[3.00,4.00],[0,1]],'');
solution(120, ['  37. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,4.00],[1.67,-0.67],[-0.50,1.50],[1.67,3.67],[4.00,-1.00],[0,3]],'');
solution(120, ['  38. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,4.00],[1.50,-1.00],[-1.00,4.00],[4.00,-1.00],[1.50,4.00],[0,1]],'');
solution(120, ['  39. Lösung'],  300, 330, 60, 80, [[0,0],[3.00,3.00],[3.00,-4.00],[-1.00,4.00],[4.00,-1.00],[-4.00,3.00],[2,3]],'');
solution(120, ['  59. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,2.00],[-1.00,2.00],[3.00,-2.00],[3.00,3.00],[-1.00,3.00],[2,0]],'');
solution(120, ['  61. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,2.00],[0.00,2.00],[3.00,-1.00],[3.00,3.00],[-2.00,3.00],[1,0]],'');
solution(120, ['  62. Lösung'],  300, 330, 60, 80, [[0,0],[4.00,2.00],[-1.00,2.00],[1.50,-0.50],[5.00,3.00],[-3.00,3.00],[3,0]],'');
solution(120, ['  64. Lösung'],  300, 330, 60, 80, [[0,0],[6.00,3.00],[-2.00,3.00],[3.00,-2.00],[3.00,2.00],[0.00,2.00],[2,0]],'');
solution(120, ['  65. Lösung'],  300, 330, 60, 80, [[0,0],[6.00,3.00],[-1.00,3.00],[3.00,-1.00],[3.00,2.00],[-1.00,2.00],[1,0]],'');
solution(120, ['  69. Lösung'],  300, 330, 60, 80, [[0,0],[2.00,4.00],[2.00,0.00],[-1.00,3.00],[3.00,3.00],[3.00,-2.00],[0,1]],'');
solution(120, ['Uli+1'],  300, 330, 60, 80, [[0,0],[3.00,6.00],[3.00,-2.00],[-1.00,2.00],[2.00,2.00],[2.00,0.00],[-1.00,3.00],[2,3]],'');
solution(120, ['Uli+2'],  300, 330, 60, 80, [[0,0],[3.00,6.00],[3.00,-1.00],[0.00,2.00],[2.00,2.00],[2.00,-1.00],[-2.00,3.00],[2,3]],'');
solution(120, ['  73. Lösung'],  300, 330, 60, 80, [[0,0],[3.00,6.00],[3.00,-1.00],[-1.00,3.00],[2.00,3.00],[2.00,-1.00],[0,1]],'');
solution(120, ['  75. Lösung'],  300, 330, 60, 80, [[1,0],[-1.00,0.00],[3.00,4.00],[3.00,-1.00],[-1.00,3.00],[2.00,3.00],[2,1]],'');
solution(120, ['  77. Lösung'],  300, 330, 60, 80, [[1,0],[3.00,0.00],[0.00,3.00],[0.00,-1.00],[3.00,5.00],[3.00,1.00],[1,3]],'');
solution(120, ['  79. Lösung'],  300, 330, 60, 80, [[1,0],[4.00,0.00],[0.00,4.00],[0.00,-3.00],[4.00,5.00],[-1.00,0.00],[3,2]],'');
solution(120, ['  83. Lösung'],  300, 330, 60, 80, [[1,0],[4.00,0.00],[0.00,4.00],[0.00,-1.00],[3.00,5.00],[3.00,0.00],[1,2]],'');
solution(120, ['  92. Lösung'],  300, 330, 60, 80, [[1,0],[2.50,1.50],[0.00,4.00],[0.00,-1.00],[3.00,5.00],[3.00,-2.00],[1,2]],'');
solution(120, ['  99. Lösung'],  300, 330, 60, 80, [[1,0],[4.00,3.00],[-1.00,3.00],[4.00,-2.00],[1.67,2.67],[-1.50,-0.50],[3,1]],'');
solution(120, [' 101. Lösung'],  300, 330, 60, 80, [[1,0],[4.00,3.00],[0.00,3.00],[0.00,0.00],[3.00,3.00],[3.00,-2.00],[1,2]],'');
solution(120, [' 105. Lösung'],  300, 330, 60, 80, [[1,0],[-1.00,4.00],[4.00,-1.00],[1.50,4.00],[-1.00,-1.00],[4.00,4.00],[2,0]],'');
solution(120, [' 108. Lösung'],  300, 330, 60, 80, [[1,0],[3.00,4.00],[3.00,-1.00],[-1.00,3.00],[6.00,3.00],[-2.00,-1.00],[1,2]],'');
solution(120, [' 109. Lösung'],  300, 330, 60, 80, [[1,0],[2.50,3.00],[-1.00,3.00],[3.00,-1.00],[3.00,4.00],[-2.00,-1.00],[2,1]],'');
solution(120, [' 113. Lösung'],  300, 330, 60, 80, [[1,0],[3.00,4.00],[3.00,-1.00],[-1.00,3.00],[6.00,3.00],[-2.00,-1.00],[1,2]],'');
solution(120, [' 114. Lösung'],  300, 330, 60, 80, [[1,0],[3.00,4.00],[3.00,-1.00],[-1.00,3.00],[2.00,3.00],[-2.00,-1.00],[2,1]],'');
solution(120, [' 133. Lösung'],  300, 330, 60, 80, [[1,1],[3.00,3.00],[3.00,0.00],[-1.00,0.00],[2.00,3.00],[-2.00,3.00],[2,1]],'');
 
</script>
 
</body>
</html>
 




[Die Antwort wurde nach Beitrag No.53 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.56, eingetragen 2019-06-12


Ich gehe immer noch davon aus, dass meine Formel für meine Kringel richtig ist, aber egal, der Nachteil meiner Kringellösung ist, dass der freie Punkt in der Mitte bei ca. einem Drittel liegt und über A1-(Freier Punkt) mit der nach ganz rechts geführt werden muss.
Deine Lösung ist besser, als sie die beiden Punkte in die Mitte legt. Wenn das teilerfremd ist wird im Drittel links und im drittel rechts kein Punkt berührt (ich bin nicht 100% sicher, aber fast).
Als Vorschlag: Ändert sich der freie Mittelpunkt, wenn du einen Kringel andersrum drehst?

PS , ja es kam ein anderer letzter Punkt raus, aber dafür schneidet sich die jetzt waagrechte Gerade nicht mehr mit der Verbindungslinie der beiden letzten Punkte. Schade ...


Mein 5x5 brute Force Ansatz hat bei 180000s die Lösung 117 beginnend mit A1 B3 gefunden.



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.57, eingetragen 2019-06-12


Noch einen Vorschlag zu auf das wir das fehlende 1/6 des (2 dimensionalen, nicht kontinuierlichen) Universums abdecken können.
Passt es wenn man das obere Dreieck 1 oder 2 kleiner macht (und das untere entsprechend größer)?
Eins kleiner (A1...G1, ...A7..A2) habe ich bei 9x9 schon probiert, hilft nichts.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.58, vom Themenstarter, eingetragen 2019-06-12


kleiner grösser und richtungen ändern der dreiecke hatte ich schon, bisher vergeblich, probiert

macht man das obere dreieck ganz klein ist es deine schneckenlösung...(den gedanken rückwärts war ja mein start-ansatz...)

ich komm auch mit den dx/dy weiter, deine formel ist richtig, sorry
du gibst die feldnummer aus und ich die feld-differenz

beste chancen für die unendlichkeit sehe ich momentan in einer besseren variante der schmetterlinge für ungerade n´s... kann aber noch dauern



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.59, eingetragen 2019-06-12


Ich habe eine Lösung für 9x9, wenn man das obere Dreieck zwei kleiner macht:
Das untere Dreieck fängt an mit I9..A1, A7..G1, I1..I8 usw.
Dabei bleibt F5 übrig. Oben A1..F1..A6..A2 usw übrig bleibt B3. dx=3, dy=4.
Ich vermute das geht immer, also wenn die ursprüngliche Anleigung nicht passt, die Dreiecke etwas verschieben, so dass dx und dy sich um eins unterscheiden.




  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.60, vom Themenstarter, eingetragen 2019-06-12


wäre schön gewesen, es sind zwei fehler, der erste zug ist sicher ein schreibfehler, muss heissen "I9..A9"
der zweite ist leider ein rechnefehler... dx...von F5 nach B3: fünf minus drei ist "zwei"



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.61, eingetragen 2019-06-12


Ja, ich hatte schräg gezeichnet und schlecht gezählt



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.62, eingetragen 2019-06-12


Servus bei'n'and ;)

Mit heißer Nadel vorhin fertiggestrickt -
meine subjektiv-topologische Gesamtschau derjenigen 40 Lösungen
für das 4x4-Raster, die ich bislang eindeutig identifiziert habe:



Legende (wers "schöner" mag, kopiere halt den Text und formatiere Ihn nach Gusto):

GRÜNE Grundfarbe der Punkte: als "bevorzugt echt" verstandene Figur
BLAUE Grundfarbe der Punkte: als "eher unecht" verstandene Figur
HELLGRÜNER/GELBER Punkt: Abbiegepunkt in als "echt" verstandener Figur
ORANGEFARBENER Punkt: doppelt durchzogener Punkt in als "unecht" verstandener Figur
GRÜNER Kringel um Punkt: Punkt ist sowohl Abbiege- wie auch Durchzugspunkt
ORANGEFARBENER Kringel um Punkt: "loser" Abbiegepunkt in als "unecht" verstandener Figur

"T1" - SECHS Schrägen, dabei vier mit Nicht-45-Grad-Steigung
[Die erste und "schönste" Leserlösung - in beiden Konfigurationen nach außen schließbar und in einer Konfiguration symmetrisch - sollte den ersten "Rang" einnehmen!]
"T2" - SECHS Schrägen, dabei aber nur zwei mit Nicht-45-Grad-Steigung
"T3" - FÜNF Schrägen
"T4" - VIER Schrägen, dabei zwei mit Nicht-45-Grad-Steigung, und zusätzlich zwei Horizontalen (parallel)
"T4a" - Linienzug singulär (nur EINER möglich) und scheinsymmetrisch
(fällt bei Spiegelung an Mittelsenkrechter genau auf den Rückweg des Spiegelbildes)
"T4b" - DREI "waschechte" Linienzüge möglich, aber kein weniger "echter"
"T4c" - nur EIN "waschechter" Linienzug möglich, und zusätzlich vier "ganz klar unechte"
"T5" - VIER Schrägen, dabei zwei mit Nicht-45-Grad-Steigung, und zusätzlich je eine Horizontale und Vertikale
"T5a" - EIN "so gut wie echter" Linienzug möglich, und zusätzlich drei "leider knapp unechte"
"T5b" - EIN einziger, also singulärer Linienzug möglich, dabei "ganz klar unecht"
"T6" - DREI Schrägen mit drei unterschiedlichen Steigungen
"T7" - DREI Schrägen, davon zwei parallel
"T7a" - VIER "so gut wie echte" Linienzüge möglich, aber kein "weniger echter"
Unterkriterien: Anzahl der Abbiegepunkte, danach Linienzugbeginn an "Vorzugspunkten"
"T7b" - nur EIN "so gut wie echter" Linienzug möglich, und zusätzlich drei "ganz klar unechte"
"T7c" - zusätzlich zu "T7a" vertikale "Zacke"; lediglich ZWEI "erkennbar unechte" sowie ZWEI "ganz glar unechte" Linienzüge möglich
"T8" - ZWEI 45-Grad-Schrägen, zwei Horizontalen und zwei Vertikalen
"T8a" - mehr als zwei "Zacken" nach außerhalb des Punkterasters
"T8b" - höchstens zwei "Zacken" nach außerhalb des Punkterasters
Unterkriterien: Grad der "[Un]Echtheit", danach Linienzugbeginne/-ende an "Vorzugspunkten"

"G1" ("ohne jede Einschränkung echt"):
Kein Punkt wird mehrfach "besucht", und alle Punkte werden von einer(!) Linie durchzogen.
"G2" ("genau so gut wie echt"):
Kein Punkt wird mehrfach "besucht", aber in einem bis drei der Punkte treffen einander zwei(!) Linien.
"G3" ("echt - mit Augenzwinkern"):
Ein Punkt oder zwei werden doppelt "besucht", dabei aber jeweils nur einmal durchzogen, und sind eben auch Abbiegepunkte. Andersartige Abbiegepunkte enthält die Figur nicht!
"G4" ("halbecht - mit Augenzudrücken"):
In "Abwertung" von "G3" enthält die Figur zusätzliche Abbiegepunkte.
"G5" ("leider knapp unecht")
In drei Varianten von "T5a", dem "orellino-Stern", werden sämtliche Punkte von den Linien durchzogen - Abbiegepunkte gibt es keine. Leider wird jeweils genau ein Punkt doppelt "besucht".
"G6" ("erkennbar unecht")
Die Figur enthält genau einen doppelt durchzogenen Punkt sowie mindestens einen streitbaren Abbiegepunkt.
"G7" ("ganz klar unecht")
Die Figur enthält sowohl mindestens einen doppelt durchzogenen Punkt sowie zusätzlich mindestens einen "losen" Abbiegepunkt.

p.s.
Die Grafik enthält (bislang) mindestens zwei darstellungstechnische Unzulänglichkeiten.
Wer findet sie?



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.63, eingetragen 2019-06-12


Bäumler, mein Zutrauen war also gerechtfertigt (Beitrag 53) - Chapeau!
Dass "Uli+1" und "Uli+2" in der späteren Liste "gefehlt" haben (Beitrag 59),
hat den Grund, aus dem mich [thom3] schon im SPON-Forum zu Recht getriezt hat: Die haben SIEBEN Linien... Muss ich im Delirium verbrochen haben ;)

Was meine zunächst intuitiven Aufzeichnungen zu einem eigenen Algorithmus anbelangen: [haribo] und Bäumler, hattet Ihr bei Euerem Tummeln in größeren Rastern je den Fall, dass eine neue Linie lediglich einen einzigen zusätzlich Punkt "besucht", ehe sie wieder abbiegt bzw. die Figur vervollständigt? Meine Annahme für die Begrenzung der möglichen Startlinien sowie für das spätere Erlauben von Abbiegepunkten ist nämlich genau das:
Lass Dir bloß nicht einfallen, Algorithmus, eine neue Richtung einzuschlagen, bevor Du mit der vorherigen mindestens zwei neue Punkte "besucht" hast!
Oder hinke ich da wieder längst gewonnener Erkenntnis hinterher?



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.64, eingetragen 2019-06-12


[haribo], im 4x4 scheint mir diejenige Lösung in unserem Sinne, bei der das Punkteraster am weitesten nach außerhalb verlassen wird, "T4c\1" bzw. "K11-5". Ich meine da mit Wohlwollen so eine Art "halben Schmetterling" zu erkennen.
Wie weit musstest Du denn bei Deinen bisherigen Flattermann-Erkundungstouren "höchstens" nach "draußen" (in Rasterweiten)? 2n?
Das wäre ja als Vorab-Außengrenze für den Raum erlaubter Abbiegepunkte hilfreich.
Und Steigungen kleiner 1:5 meine ich beim 14x14-Falter auch nicht zu erkennen.
In der Art was wäre als Vorab-Steigungsgrenze für erlaubte Abbiegevektoren auch nicht dumm.

Bäumler, falls ich da "hinterher" bin, schilt mich ruhig!
Meinem eigenen Algorithmus möchte ich eben von vornherein so viel wie möglich "Effizienz-Spaßbremsen" austreiben. Ich nehm, was ich kriegen kann ;)



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.65, vom Themenstarter, eingetragen 2019-06-12


sieht jetzt sehr gut aus cram-ilu!

nein ich hatte noch nie ne lösung mit nur einem besuchspunkt einer linie, das wäre wenn auch nicht eindeutig, man könnte die linie um den punkt, im gewissen rahmen, drehen und neu verschneiden

hier ein neu sortierter 9 x 9er, den müsste man doch systematisch auf mindestens die (3);9;15;21.. erweitern können

scheints muss die doppelspirale in achten durchlaufen werden


haribo

nachtrag: geringste steigung ist hier die rote mit 1/n und sie geht 4n nach aussen...



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.66, eingetragen 2019-06-12


[haribo] Supi, danke! Also muss man tatsächlich Liniensteigungen von 1:(n-1) erlauben. Grmpf! "Muss" die nach 4n außerhalb wieder rein, um speziellen grundfigurtechnischen Ansprüchen zu genügen, oder würde ihr Wendenachfolger auch etwas sinnvolles "treffen" können, wenn sie noch weiter raus liefe?



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.67, eingetragen 2019-06-12


Es kommt drauf an. Willst du Lösungen finden oder alle Lösungen finden?
Mein Ziel war letzteres und deshalb habe ich auf Einschränkungen verzichtet.
Statt der Steigungsbegrenzung würde ich ein "Geradeaus Gebot" einführen.
Wenn A1 A2 dann auch alle folgenden Punkte mitnehmen (wenn sie noch frei sind).
Einmal ums Eck (also 90° und gleich wieder 90°)zb A1 A2 A3 B4 B3 B2 habe ich noch nicht gesehen. Ich könnte mir auch vorstellen, dass es das nicht genen darf.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.68, vom Themenstarter, eingetragen 2019-06-12


diese lösung funktioniert für alle ungeraden n´s
die geraden werden nach der lösung aus #54 gelöst
damit ist der beweis für alle n x n von 3x3 bis "unendlich x unendlich" mit 2(n-1) strichen ohne doppelte punktberührungen erbracht

hurra haribo



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.69, vom Themenstarter, eingetragen 2019-06-12


@bäumler zwei fragen:
-hast du den im letzten beitrag links mittig abgebildeten 5x5er schon gefunden? du müsstest ihn zweimal finden einmal 90°UZ gedreht mit start A2, und das zweite mal 90°GUZ gedreht dann auch mit start A2, zumindest letzteren würdest du also evtl. vermissen mit deinem "GradeausGebot"?
-würde dein program ggfls. eine lösung mit weniger strichen als 2(n-1) erkennen? wir haben diese grenze ja als bisherige kleinste linienzahl erkoren und jetzt bewiesen das es damit immer geht, aber natürlich keineswegs bewiesen das es ein absolutes minimum darstellt bei grösseren n´s



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.70, eingetragen 2019-06-12


Huch!?

Verrutscht?!



6+5 = 11 ; 11-2 = 9

Na, wenigstens... Ich frage mich, ...

Sag' mal, Bäumler, wenn Dein Algorithmus mit "5x5" durch ist...
Nein: Sobald er durch ist...
Könnte er auch 4x3, 5x3, 5x4 zwecks Zeitabschätzung für n>5?
Nur so'n Gedanke!

Guten Nacht ;)



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.71, eingetragen 2019-06-12


zu No 69 links mitte gefunden: nein, wir sind noch eine ganze Weile bei A1, dann erst kommt A2, dort sollte er dann als A2 A3 A4 B4 ... gefunden werden

zu No 69 kleiner n-1: ja, das ist "nur" eine Abbruchbedingung bei der Suche. Wenn meine Prüfung strecke() immer sagen würde, ok geht weiter gerade aus würde auch eine Lösung mit einer Strecke gefunden werden.

zu No 70 n*m: Ginge prinzipiell schon, würde aber schon an einigen Stelle  Eingriffe erfordern (Überall da wo WU_N steht)



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.72, vom Themenstarter, eingetragen 2019-06-12



2+3=5 5-2=3 aber unendliche anordnungsmöglichkeiten

[Die Antwort wurde nach Beitrag No.70 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.73, vom Themenstarter, eingetragen 2019-06-13


ansatz eines beweises über die mindest-linienmenge

man müsste wohl noch meine beobachtung der immer aufretenden n un-waagerechten in zwei aufeinanderfolgenden zeilen beweisen... oder wiederlegen
dann wäre die mindest-linienmenge 2(n-1) bewiesen/wiederlegt


haribo



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.74, eingetragen 2019-06-13


Ich habe für 4x4 jetzt 45 Lösungen (Dreh/Spielel/Rückwärts und letzter Punkt zurückgezogen).
Sie sind nach Punkten sortiert. Ich sehe keinen doppelten?



Die mit A1 anfangen haben keine Beschränkung hinsichtlich des Endpunktes. die mit B1 beginnen dürfen an keinem Eckpunkt (=A1 + Symmetrie) enden, und die B2 düren nur an einem Punkt in der Mitte enden.

Der 5x5 spuckt immer mal wieder Lösungen aus: gestern dieses nette Pärchen, in dem nur das Doppeldreieck links anders durchlaufen wird.
A1 B5, D5 D4 D3 D2 D1, xxx B1 A4, A5 B3 C1, xxx E1 E2 E3 E4 E5, C5 B4 A3, A2 B2 C2, C3 C4
A1 B5, D5 D4 D3 D2 D1, xxx C1 B3 A5, A4 B1, xxx E1 E2 E3 E4 E5, C5 B4 A3, A2 B2 C2, C3 C4


passt auch sehr schön zu Beweisansatz von haribo.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.75, vom Themenstarter, eingetragen 2019-06-13


anhand deiner 45 varianten nochmal all die bänder ohne mitlaufende linien



manche bänder werden von mehr als n linien gequert, aber mindestens n sind es immer!
manchmal könnten die bänder auch breiter sein... u.A. die gelben 18,20;35 sind wohl auf die schnelle ungeschickt gewählt, aber auch dort gibt es passende gelbe positionen

da es nicht unendlich viele verläufe (jedenfals mit n querenden linien) innerhalb der bänder gibt könnte das ggfls ein program beschleunigen mit solchen bänder-sets zu starten?



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.76, eingetragen 2019-06-13


zum 4x4 Lösungssatz und allgemein der Unterdrückung von doppelten Ergebnissen:
Ich denke folgende Bedingung ist ausreichend:
Wenn man den Endpunkt in die obere Hälfte des ersten Quartals legt (rotiert und spiegelt) darf das kein, nach der Sortierung früheres oder gleiches Ergebnis liefern.
Einen beliebigen Lösungssatz (A1, ...) kann man also nach folgendem Vorgehen sortieren und von doppelten befreien:
für jede Lösung:
Die beiden Endpunkte ins 1. Quartal drehen und den nach Sortierung kleineren Wert aufnehmen und einsortieren.
Zu beachten: die einzelnen Lösungen sollen aufgefüllt sein, also doppelte Punkte auch doppelt enthalten sein.

[Die Antwort wurde nach Beitrag No.74 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.06.2019
Mitteilungen: 42
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.77, eingetragen 2019-06-13


Ich warte noch auf Widerspruch der 40er, 41er oder 42er Fraktion zu meiner vergrößertem Lösungsliste ...

Nachtrag: ps71 hat die Nummern (10,12) (38,42) (39,41) als doppelt identifiziert. Und falsch einsortiert waren die Doppel natürlich auch!
Damit bin ich jetzt auch bei 42.

Zum Beweis: das sieht doch als Ansatz schon ganz gut aus.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2120
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.78, vom Themenstarter, eingetragen 2019-06-13


zweiter versuch eines beweises über die mindestanzahl der linien 2(n-1)

gleichzeitig ein beweisversuch warum es zwei nebeneinanderliegende zeilen geben muss in denen keine waagerechten linien vorkommen... zwischen denen aber n schräge linien sich befinden(pinkes band im vorherigen beitrag)

vorab: wir haben bewiesen das es für jedes n eine lösung gibt mit 2(n-1) linien, die frage ist "könnte es sein dass es lösungen mit weniger linien gibt"

A: gäbe es in jeder zeile eine waagerechte linie, dann wären dies n linien (blau), sie hätten 2n offene enden, zwei davon könnten anfang und ende des weges sein die anderen müssten jeweils durch neue linien verbunden werden, dazu sind mindestens n-1 linien erforderlich(gelb), als summe macht das also 2n-1 linien

2n-1>2(n-1) also gibt es damit keine lösung mit weniger als 2(n-1) linien


B: wäre in einer zeile keine waagerechte linie, dann müssten in dieser zeile alle n punkte einzeln durch neue schräge linien berührt werden, wäre nur eine der linien waagerecht läge ja fall A vor, es gibt also in dem fall mindestens n-1 blaue linen und n gelbe(schräge), als summe macht das also 2n-1 linien

2n-1>2(n-1) es kann damit lösungen geben aber eben mit zu vielen linien, also sind damit keine lösung mit weniger als 2(n-1) linien möglich


C: wären zwei zeilen ohne waagerechte linien, und diese beiden zeilen wären nicht benachbart, dann gäbe es mindestens n-2 blaue linien und wieder die n gelben für eine der zeilen (hier die untere), als summe macht das also 2n-2 = 2(n-1) linien

es sind also jetzt schon genau die mindestanzahl linien vorhanden, eine der schrägen linien muss ein ende der in der zwischenzeile waagerechten linie (rot) erreichen, das ist ohne probleme machbar, das andere ende der roten linie könnte start oder zielende des weges sein muss also nicht unbedingt erreicht werden

aber

alle n punkte der oberen zeile (ohne waagerechte linien) müssen auch von den schon vorhandenen n schrägen linien berührt werden, es können nicht zwei der punkte miteinander (durch eine dann waagerechte linie) verbunden werden denn dann läge fall B vor, also muss jede schräge linie der unteren zeile einen punkt der oberen zeile erreichen, damit liegt ein widerspruch vor denn mindestens eine der schrägen linien endet ja schon an der roten zwischenlinie...


D: es müssen also zwei benachbarte zeilen geben ohne waagerechte linien, und jeder punkt der unteren zeile muss einen anderen der der oberen zeile erreichen, damit befinden sich im pinken band zwischen zwei zeilen immer n verschiedene linien welche das pinke band durchqueren

es gibt damit lösungen mit 2(n-1)linien

damit ist IMO die pink-band beobachtung aus #73 bestätigt, oder?


ich bin aber immer noch nicht sicher ob mit dieser beweisführung gleichzeitig die mindestzahl 2(n-1) abgesichert ist, es könnte sein das man noch zeigen muss das n schräge auch nicht gleichzeitig drei oder mehr zeilen in jedem punkt berühren können???

denn wir haben ja durchaus lösungen mit 2(n-1)die weit weniger waagerechte linien haben

haribo



  Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 09.06.2019
Mitteilungen: 103
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.79, eingetragen 2019-06-13


na, [haribo], das bestätigt doch das gesamtvorgehen eindringlich:
1. gesammelte figuren chronologisch kategorisieren/katalogisieren ("Kx")
2. sammlung topologisch typisieren ("Tx")
3. topologische gemeinsamkeiten verschiedener typen aufspüren
4. [zwingende] rückschlüsse für algorithmische effizienzkriterien ziehen
5. ...

so wie ich das sehe, erschlägt dein "beweis" (nicht abschätzig, sondern bloß, weil ich nicht [mehr] beurteilen kann, wie mathematisch zwingend er ist - bin da zu lange aus den tiefen der materie draußen) locker meine typen "T4" und "T7". "T5" und "T7" ist zudem die eine senkrechte gemeinsam, welche mutmaßlich verantwortlich ist für abbiegepunkte zusätzlich zu reinen durchgangspunkten. wenn man "T3" nach rechts dreht, hat er mit "T5" gemein: starte bei "A2" (etc.), fahre schräg ganz nach oben bzw. rechts außerhalb des rasters, besuche alle Punkte einer äußeren waage- oder senkrechten bis übers raster raus und sammle danach alle übrigen im zick-zack ein. oder so. sowas wie "T1" und "T2" ist ggf. nur bei geraden rastern möglich, weil sich da die hauptdiagonalen nicht in einem rasterpunkt schneiden etc. wenn man solcherlei erkenntnisse nun genügend abweichungsfrei belegt, lassen sich für die algorithmische wege-analyse sicher zusätzliche einschränkende bedingungen aufstellen, um die rechenzeit zu drücken, OHNE dass man auf den leim geht, nur die Figuren finden zu können, die man finden wollte ;)



  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 2Gehe zur Seite: 1 | 2 | 3 | 4 | 5  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]