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 6]   6 Seiten
Autor
Kein bestimmter Bereich 16 auf einen Streich
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
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 ;)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
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 ;)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
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 ;)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.80, eingetragen 2019-06-15


Beweisansatz für 2 (n-1)
Ich denke darüber nach ob der Beweis im Übergang von n×n nach (n+1)×(n+1) möglich ist. Sei m=m+1
Idee ist zu beweisen, dass man, wenn man zu einer bestehenden Lösung für nxn ein L hinzufügt (mit 2n+1 Punkten) man dafür immer 2 Striche braucht.
Das wäre nicht der Fall, wenn bei der nxn Lösung die nächste Spalte schon komplett abgedeckt sein könnte.
Wenn man zeigen könnte, dass das nicht geht hätten wir den Beweis.
Es sei denn, die Lösung mit einer Strecke weniger hätte keinen Strich außen (Wie es beim Weihnachtstern der Fall ist)
Deshalb allgemeiner: Wenn man zeigen kann, dass es nicht möglich ist vom hinzukommenden L (mit den 2n+2 Linien) bereits n Punkte abzudecken ist man fertig.
Oder von m (der hypothetischen Lösung mit nur 2m-1 Linie) kommend:
Ich nehme einen Strich weg und ein äußeres L (2n+1 Punkte). Der höchste Verlust an abgedeckten Punkten durch den entfernten Strich sind 2 Punkte wenn der entfernt Strich nicht im L lang, sonst n+1 Punkte.
Die Fälle diskutiere ich morgen weiter ...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.81, vom Themenstarter, eingetragen 2019-06-15


moin bäumler,

schau mal das bild in #75 an, unter (fast)jeder kreuzung von pink und gelb befindet sich ein gekreuzte linie... es gibt gar nicht so viele möglichkeiten kreuzungen in feldmitte zu bekommen, evtl kann man darüber irgendwie die permutationen abzählen?


bei den ausreissern gehört wohl das gelbe band verschoben...?
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.82, eingetragen 2019-06-15


Die Festlegung für die Bänder war mir noch nicht verständlich zB beim Weihnachtsstern ist doch gar keine Reihe/Spalte ausgezeichnet??



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.83, eingetragen 2019-06-15


Sortierung
ps71 hat in den 5x5 Lösungen eine Namenkonvention verwendet, die in zwei Punkten von meinem bisherigen Verständnis abweicht, aber den Charme hat, immer gleich lang (zwei mal die Streckenzahl) zu sein.
(Leerzeichen von mir hinzugefügt.)

1) Unterschied: Knickpunkte doppelt
Die 3x3 Lösung in "meinem" Verständnis
048 52 13 67  Wenn es mehrfache Punkte gibt,wird der String länger.
Nach ps71 (nur 1. Unterschied) 048 852 13 67 d.h. die Knickpunkte (hier 8) werden mit doppelt aufgezählt, weil sie zu zwei Linien gehören.

2) Unterschied: Er nimmt nur die Endpunkte jeder Linie auf
also 08 82 13 67  

Eigentlich wäre es nicht so entscheidend, aber dadurch ändert sich leider die Sortierung:
Vergleich
A) Punktfolge: 5(B3) 4(B2) 0 (A1)  ==> ps71: 5440 ==> Baeu 540
B) Punktfolge: 5(B3) 4(B2) 3 (B1)  ==> ps71: 53__ ==> Baeu 543
Nach Reihenfolge der Punkte ist A<B, in der ps71 Konvention ist B>A.
Ich hätte die Sortierung nach Reihenfolge der Punkte beibehalten.
Eure Meinung?






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.84, vom Themenstarter, eingetragen 2019-06-16


2019-06-15 14:26 - Baeumler16 in Beitrag No. 82 schreibt:
Die Festlegung für die Bänder war mir noch nicht verständlich zB beim Weihnachtsstern ist doch gar keine Reihe/Spalte ausgezeichnet??

1. keine parallel zu den bändern verlaufenden wege an den beiden längskanten der bänder
2. mindestens n schräg oder quer durch die bänder laufende wege

es war einfach die beobachtung das es diese bänder IMMER gibt, analog zu D in #78. und später die erkenntnis dass es sie dann auch in beide hauptrichtungen geben muss

also es gibt lösungen bei denen mehrere bänder nebeneinander durch die graphen laufen könnten, insofern ist meine darstellung von jeweils einem band in#81 nicht eindeutig, es ist derzeit noch mehr ein offenes herumdenken was es bedeuten könnte...

und natürlich die frage ob man nicht durch allerlei permutationsmöglichkeiten der querenden wege in den bänder die computer suche aller möglichkeiten verbessern könnte??? aber noch weiss ich nichtmal wie viele verbinduns möglichkeiten es zwischen zwei mal 5 punkten geben kann wenn man gespiegelte weglassen möchte... evtl. 5!/2  ???

die überlegungen dazu sind also noch alle im suchmodus

haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.85, eingetragen 2019-06-22


Zurück aus dem Vinschgau ;)

Na, ich hatte schon gehofft/befürchtet, inzwischen gäbe es Lösungskataloge für 5x5, 6x6 und 7x7 sowie dramatische Algorithmusverfeinerungen...
Schon irgendwie beruhigend, dass dem nicht (ganz) so ist ;)

Ich selbst habe während entspannter Urlaubsstunden "wenigstens"
die 28 "zweifelsfrei echten" Lösungen (ohne Abbiegepunkte)
laut ps71-Algorithmus sortieren, typisieren und aufbereiten können:



Innerhalb einer topologischen Typengruppe habe ich wieder nach Start
am Vorzugspunkt, Flachheit der ersten (bzw. zweiten, dritten usw.) Linie
und ggf. nach kürzerer erster Linie sortiert/typisiert.

Für mich lehrreich: Keine der 28 Lösungen topologisch doppelt,
gegenüber 4x4 keine einzige symmetrische Lösung und auch keine einzige
singuläre (also ähnlich 4x4 "K7", "K9", "K11", "K12").
Scheint meine Vermutung hinsichtlich grundlegender typentechnischer Unterschiede zwischen geraden und ungeraden n als Rasterbasis zu bekräftigen...
Was die Effektivität des ps71-Algorithmus anbelangt, hege ich leider zarte
Restzweifel, weil meinem Bauch die Anzahl 28 für solcherlei Lösungen nicht abschließend behagen mag. Selber weitere finden konnte ich indessen nicht!

Der erweiterte ps71-Lösungskatalog für solche MIT Abbiegepunkten enthält übrigens nach meiner groben Durchsicht mindestens 27 derer OHNE Abbiegepunkte wiederholt... So lediglich meine Analyse - keinerlei Vorhaltung!

[haribo], erneut finde ich Deine Vorüberlegung von wegen (n-2) Horizontalen und 2 dazwischenliegende "Verbindungssammlerreihen" für Schrägen in mehreren "meiner" Typen bestätigt. À la bonn'heur! Oder wie immer der Westfranke dazu sagt ;)

Bäumler, mein eigener Algorithmus nimmt Gestalt an...

So long - schönes Wochenende!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.86, vom Themenstarter, eingetragen 2019-06-23


2019-06-22 18:37 - cramilu in Beitrag No. 85 schreibt:
Scheint meine Vermutung hinsichtlich grundlegender typentechnischer Unterschiede zwischen geraden und ungeraden n als Rasterbasis zu bekräftigen...


jede 5x5er lösung hat mindestens eine aussen verlaufende kante, nicht immer am ende des weges aber trotzdem immer durchgehend durch 5 punkte, dass könnte eine eigenschaft der ungeraden n sein?
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.87, eingetragen 2019-06-24


Wie fies!

6x6. Zehn Striche. Wunderprächtig. Und dennoch:
"Die Herrschaften, die auf Kartoffeln mit Speck gesetzt hatten, zur Kasse bitte..."



@Bäumler No.61:
Na?! Hat der nicht sogar gleich zwei mehrfache?
Und am Ende ist dem HTML-Skript auch noch knapp die Puste ausgegangen ;)

Bäumler, hast Du schon überlegt, (D)einen Algorithmus ggf. derart zu "pimpen", dass man ihn beim 6x6 "etappenweise" laufen lassen kann, also mit einer Art "Marker" für die bereits begonnene Wege-Analyse (bis wohin war ich zuvor gekommen; da mache ich beim nächsten Mal weiter...)? Bei abgefragtem Programm-Abbruch eine Position beim Abarbeiten der Analyse merken, geregelt ausgeben und beim nächsten Programm-Start als Eingabe zwecks Fortsetzung abfragen?

@[haribo] No.86:
Scheint zu stimmen. Für meine Begriffe wären im Hinblick auf Algorithmus-Effizienz "Negativ-Beweise" erforderlich. So nach der Art "Liniensteigungen von (n-2):(n-1) kann es bei echten Lösungen nicht geben, weil...".

Ich sehe tatsächlich in der wohlüberlegten "Ausdünnung" des "Liniengitters" momentan den erfolgversprechendsten Ansatz zur Steigerung der Laufzeit-Effizienz.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.88, vom Themenstarter, eingetragen 2019-06-24


wie durchfährst du deinen graphen, welcher in den aussenecken 4 ungerade knoten hat in einer linie?
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Baeumler16
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2019
Mitteilungen: 49
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.89, eingetragen 2019-06-24


@cramilu 87. Der Stern ist zwar schön, aber keine Lösung. Mit 4 Ecken a 3 Linien kann man ihn nicht durchfahren, da an einem 3er Eck der Linienzug beginnen oder enden muss.

Das Programm könnte man so modifizieren, aber fürchte, dass es für große N (>4) sehr ineffizient wird auch wenn man das erste Stück vorgibt.

Zu SPON Beitrag 344. von ps71: Ich habe ein Programm, dass für einen Linienzug folgende Daten berechnet: Linksabbieger, Abknickpunkte, mehrfach berührte Punkte, reduzierte (erster und letzter Punkt jeder Linie) und vollständige Punkteliste.

Es wäre also ein Leichtes die ps71 2823 Lösungen zu kategorisieren.

Noch nicht funktionierend, aber schon angefangen ist die Kategorisierung: Hier habe ich mir überlegt die Linie auf die äußeren Punkte des Rasters zu schieben und dann nach Punkten zu sortieren. Also die Liste der möglichen Linien wäre A1 A4, A1 B3, A1 B4, A1 C2, A1 C4, A1 D1, A1 D2, A1 D3, A1 D4, A2 B1, ...
Die Kopie/Originalerkennung (ist ein gespiegelte rückwärts gedrehte Abkömmling sortiert vor der angebenden Lösung) ist auch angefangen.

Einlesen kann das Programm hex und Schachnotation.
Bei bestimmten Eingabesequenzen ist noch ein Bug (parallele Fortsetzung (zB A1 A2 B4 B1)




[Die Antwort wurde vor Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.90, eingetragen 2019-06-24


Vorab:
Wer an meinen hiesigen Foren-Alias einen Klammeraffen, die inselkeltische Bezeichnung fürs Netz, ein Satzendezeichen und die inländische TopLevel-Domain anhängt, kann mir gerne auch eine längere bzw. persönliche Nachricht zukommen lassen.

[haribo] No.88:
Daher ja das "Lucky-Luke"-Zitat! Wenn man sich vorher zwei Bierchen gönnt, hernach beidhändig(!) mit je einem Rasteraußenpunkt der Hauptdiagonalen beginnt und sich nach jeweils 5 Strichen die Hände treffen, hat man dann wirklich gegen die Regeln verstoßen? ;)

Zwischenbilanz zum eigenen Algorithmus:
+ kleinstes gemeinsames Vielfaches für 2 bis (n-1) wird automatisch berechnet
+ damit wird im folgenden das Koordinatensystem "aufgeblasen", um nur noch Abbiegepunkte mit ganzzahligen Koordinaten zu erhalten
+ Rasterpunkte mit x-y-Koordinaten sowie je einem booleschen Flag für "ist bereits Durchgangspunkt" und "ist bereits Abbiegepunkt" werden in einer zweidimensionalen Feldvariablen abgelegt
+ Startpunkte (unteres linkes "Achtel" unmittelbar oberhalb der ersten Winkelhalbierenden) werden automatisch berechnet und mit ihren Koordinaten etc. in einer Listenvariablen abgelegt
+ je Startpunkt wird eine eigene Liste möglicher Startvektoren automatisch berechnet (aus den mittlerweile "aufgeblasenen" Rasterpunktkoordinaten)
+- "Geradengitter" wird automatisch ermittelt... (aktuell in Arbeit)

Bäumler und SpOn-[ps71]:
Nach meiner Abschätzung kommen im 6x6 gegenüber 5x5 KEINE zusätzlichen Startpunkte hinzu, und bei 36 = 25 * 1,44 Punkten sollten sich zudem der Umfang möglicher Startvektoren sowie der des "Geradengitters" höchstens gut verdoppeln (1,44 * 1,44 = 2,0736).
Das ist, klar, immer noch ein "feister Knochen", sollte doch aber mal ein Stündchen Testlauf für 6x6 lohnen... Ggf. würden wenigstens ERSTE Resultate vom Tisch fallen?!

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.91, eingetragen 2019-06-25


[haribo], Du hattest Dich ab no.44 als figurentechnischer "Lepidopterologe" betätigt und eindrucksvoll gezeigt, dass es stets eine Lösung à la "Verbinde (n-2) Horizontalen über zwei mittig liegende Punktezeilen derart, dass dabei n Schrägen jeweils 2 neue Punkte aus diesen Verknüpfungszeilen mitnehmen" geben sollte.
Hier wird die mittlere Punktezahl pro Linie erreicht mit (n*(n-2)+2*n)/(2*n-2), also knapp überzählig mit jeweils 2 und knapp unterzählig mit n Punkten je Linie.

Allgemein lautet die Abschätzung(!) für große n:
(n*n - 1) / (2*(n-1)) = (n+1)/2
Also etwa für n = 11 im Mittel 6 Punkte pro Linie (tatsächlich 6,05),
und für n = 99 im Mittel 50 Punkte pro Linie (tatsächlich 50,0051).
Der Abschätzungstrick ist die Reduktion des Zählers um 1, was bei "großen" n kaum noch einen Unterschied macht, aber eine "saubere" Division nach der dritten binomischen Formel erlaubt.

Bei "Schneckenlösungen" sinkt die "Neupunktezahl" je Linie verhältnismäßig kontinuierlich, während sie bei "Schmetterlings[/Amboss]lösungen" kontinuierlich zwischen n und 2 hin- und herhüpft.
Auch zu den "Schnecken" hattest Du hier schon überzeugende Beweisansätze gezeigt.

Angesichts der mittlerweile etwa vierzig 5x5-Lösungen mit Abknickpunkten, die [SpOn-ps71] zur Verfügung gestellt hat, und die ich bislang durchtypisieren konnte, kommen bei mir inzwischen zwei Verdachtsmomente auf:

1. Lösungsformel für echte Lösungen OHNE Abbiegepunkte
(n-1)*(n+2) für UNGERADE n UND (n-1)*(n+2)/2 für GERADE n

2. stetig geringerer Zunahme der Anzahl echter Lösungen OHNE Abbiegepunkte mit wachsendem n
Bereits die Anfänge der Typenübersicht zum 5x5 zeigen einen abnehmenden "Typenreichtum" gegenüber 4x4. Das mag hier noch am gegenüber 4x4 "ungeraden" Raster liegen, jedoch drängt mich etwa auch der schon im 6x6 nicht mehr praktikable Stern (siehe no.87) zu solcher Vermutung. Mit wachsendem n scheint mir momentan die Anforderung, andere als "Schnecken-" oder "Schmetterlingslösungen" zu finden, immer unerfüllbarer...

Bäumler, ich möchte in meinen Algorithmus auch eine nachträgliche Wege-Selbstanalyse einbauen, die jedem Weg etwa seine effektive Weglänge, ggf. "UPS links/rechts", Summe der Abbiegewinkel, Anzahl der [exotischen] Schrägen, "Flachheitskennzahl" des Linienzuges uvm. zuschreibt. Auf diese Weise könnte sich die Ergebnisliste vorab quasi auch selbst typisieren ;)

Für mich noch wichtiger:
Die Wege-Analyse beginnt mit einer äußeren Rahmenschleife über alle ermittelten gefilterten möglichen Startpunkte (4x4: 3, 5x5 und 6x6: 6, 7x7 und 8x8: 10 usw.), sortiert(!) nach Entfernung zu "A1" (stets bevorzugtester Startpunkt). Zuvor wird dem Benutzer eine Auswahl angeboten, an welchem Startpunkt der Hierarchie er die Analyse beginnen [lassen] möchte. Dann gibt es vom Startpunkt abhängende innere Rahmenschleifen über alle zum Punkt ermittelten Startvektoren. Auch die möchte ich geordnet sortieren, suche aber hierfür noch nach dem Kriterium. Wiederum kann dann der Benutzer auswählen, mit welchem Vektor der Unterhierarchie die Suche nach neuen Wegen [diesmal] begonnen werden soll.
So werden "etappenweise" Laufzeitmessungen möglich und damit ggf. Nach-Und-Nach-Abschätzungen zur Effizienzsteigerung...

Überlegung zu Abbruchkriterium "unterwegs":
Die rechte Lösung in meinem Beitrag no.35 zeigt, dass man z.B. im 6x6 schon auf der dritten Linie abbiegen kann, ohne dort alle Punkte "abgegrast" zu haben, und dennoch eine "echte" Lösung erhalten kann.
Mindestens zwei neue Punkte pro neu "befahrener" Gittergeraden halte ich für die Minimalanforderung. Auch als allgemein gültig denkbar sind: Mindestens die Hälfte der möglichen neuen Linienpunkte ; mindestens einen mehr als die Hälfte... ; höchstens zwei NICHT "mitnehmen"...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3030
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.92, vom Themenstarter, eingetragen 2019-06-25


cramilu, zwischen #50 und #68 sind ja auch einige grosse lösungen gezeigt, damit kannst du evtl einen teil deiner verdächtigungen überprüfen?
obirah



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1015
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.93, eingetragen 2019-06-26


@[haribo] no.92:
Auf Deine schönen Lösungsvorstellungen etc. ab no.46 hatte ich mich ja zuvor bezogen (wenn auch knapp in der Beitragsnummer verlesen). Bin schon am Eruieren ;)
Wenn ich Deine Beiträge no.75 und no.81 richtig verstehe, ließen sich mittels der "Bänder" (?rosa: "Sammelbereich" für Schrägen ; gelb "Häufungsbereich" für Linienkreuzungen?) Typen anders klassifizieren bzw. innerhalb einer Typengruppe neuartig unterordnen. In einer Art "LTXUHFE", wobei die Lage der "Bänder" zueinander grob eine Buchstabenform ergibt.
??? "T1\1" aus meinem Beitrag no.85 wäre dann ein "dicker L-Typ" mit einem verdickten rosa Band zwischen der mittleren und der untersten Punktezeile sowie einem verdickten gelben Band zwischen der äußerst linken und der mittleren Punktespalte ???
Finde ich zur Klärung von Typenverwandtschaften sowie zum Auffinden "exotischer" Untertypen-Ausreißer sehr eingängig!
Allerdings werde ich mich wohl in den nächsten Tagen zusammenreißen müssen, um interessemäßig nicht zu sehr hin und her zu springen zwischen "Welche Figurentypen kann es bei großen n geben?" und "Welche möglichst vollständigen Eichkataloge für 3 < n < 7 bringen mich analytisch beim Programmieren weiter?". Ein möglichst effizienter eigener Algorithmus samt "Zwischeneinstiegsmöglichkeit" hat erst mal Vorrang ;)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 2Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6  
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-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]