Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » ** Kropki
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich ** Kropki
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2008-07-29


Hallo zusammen!

Hier ein kleines Logikrätsel für die Sommerpause:

Tragen Sie Ziffern von 1 bis 8 so in das Diagramm ein, dass jede Ziffer in jeder Zeile und jeder Spalte genau einmal vorkommt. Befindet sich zwischen zwei Ziffern ein schwarzer Kreis, so muss eine der beiden Ziffern exakt das Doppelte der anderen sein. Ein weißer Kreis hingegen bedeutet, dass eine der beiden Ziffern um eins größer sein muss als die andere. Befindet sich kein Kreis zwischen zwei Ziffern, so darf auch keine der beiden Eigenschaften zutreffen.


(Kropki ist übrigens der Name des Rätseltyps.)

Gruß, Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Bitte poste Lösungen zu dieser Aufgabe nur dann im Forum, wenn der Themensteller das verbal in seinem Aufgabentext erwähnt hat. Sonst antworte ihm in einer privaten Nachricht. (Hinweis: Diese Knobelaufgabe wurde gestellt, bevor es die explizite Einstellung 'Antworten nur mit privater Nachricht' gab.)
Luke
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.10.2006
Mitteilungen: 5501
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2008-07-30


hallo,
nichts mit dem raetsel zu tun, aber zusatzinfo: kropki bedeutet uebrigens "punkte" (im sinne von flecken).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2008-07-30


Erster mit der richtigen Lösung ist Yggdrasil um 00:19.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2008-07-30


Zweiter ist Bilbo um 01:03.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2008-07-30


Und hier ist noch ein zweites Rätsel, das noch einen Zacken schärfer ist. Es müssen Zahlen von 1 bis 9 eingetragen werden:


Gruß, Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2008-07-30


Beim 8er-Rätsel ist GrafZahl Dritter (13:48).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2008-07-30


Vitali reichte 16:46 für beide Rätsel die richtige Lösung ein.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bernhard
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2005
Mitteilungen: 6424
Herkunft: Merzhausen, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2008-07-30


@ Philipp:
Kurze Zwischenfrage:

Ich höre von dieser Art Rätsel hier das erste Mal.
Kann man angeben, wie viele solcher vorgegebenen "kropki" (laut luke "Punkte") es bedarf, um das Ding eindeutig lösen zu können?

Viele Grüße, Bernhard



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2008-07-30


Zunächst zum Namen: Kropki ist einfach der Name des Rätseltyps (Wie "Sudoku" oder "Hashiwokakero" oder andere Rätsel ;-)) und kommt aus dem Polnischen. Laut eines online-Wörterbuches bedeutet das Wort "kropka" Punkt, davon leitet es sich wohl ab.

Die schwarzen und weißen Punkte kann man ruhig Punkte nennen. ;-)
Wenn man die Lösung eines Rätsels kennt, sind die Punkte beinahe eindeutig bestimmt, d.h. man hat keine Wahl, welche Punkte man vorgibt: Zwischen einer 1 und 2 darf man zwischen schwarz und weiß wählen, und sonst müssen alle Punkte gegeben werden (im Gegensatz dazu muss man sich bei Sudokus (vermutlich) mindestens 17 Zahlen aussuchen). Um eine andere Zahl von Punkten zu erhalten, kann man nicht wie beim Sudoku einfach ein paar Zahlen dazuschreiben, sondern wird ein völlig neues Rätsel erhalten. Jetzt kann man nach dem Rätsel mit der minimalen Anzahl von Punkten fragen, aber das kenne ich nicht und habe auch noch nie drüber nachgedacht.

Da es für Kropki keine Standardgrößen gibt (wie bei Sudoku 9x9), muss man noch eine Fallunterscheidung nach Größe machen. Ich behaupte, dass es bei 3x3 8 Punkte sind, für größere Zahlen müsste man mal ein Programm schreiben, die Komplexität ist nicht ganz so hoch wie bei Sudokus.

EDIT: 4x4 geht auch noch per Hand, da ist 12 das Minimum.

Gruß, Philipp

[ Nachricht wurde editiert von philippw am 30.07.2008 23:36:06 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2008-08-03


Hi Philipp,

Du hast ja vor einiger Zeit auch einen Artikel über dieses Spiel geschrieben :-)

Ich habe mal ein Java-Programm erstellt, das für verschiedene n die minimale Anzahl an Punkten (heuristisch) bestimmt. Ergebnis:

n12345678910111213141516
#Punkte0481481212141618202224262830


Ab n = 7 scheint sich die Formel #Punkte = 2(n-1) einzustellen. Bei n = 4 gibt mir das Programm 14 als Minimum an, abweichend von deiner Berechnung (hast du vielleicht ein Beispiel?).

Hier noch zwei solcher Minimalisten für 8x8- und 9x9-Kropki als Kostprobe:

Bild  und  Bild

Interessanterweise gibt es nur schwarze Punkte. Die Lösungen poste ich später.

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2008-08-17


Hi Kay,

Ich komm grad aus dem Urlaub zurück. Das Programm interessiert mich, wie arbeitet es denn?
Hier mal ein Beispiel für n=4 mit 12 Punkten:


Deine Rätsel mach ich, wenn ich ausgeschlafen hab. Ich kann grad nicht glauben, dass sie eindeutig lösbar sind, die Punkte sehen so wenig aus  wink

Gruß,
Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2008-08-17


2008-08-17 01:45 - philippw in Beitrag No. 10 schreibt:
Ich komm grad aus dem Urlaub zurück. Das Programm interessiert mich, wie arbeitet es denn?

Eigentlich ganz einfach. Es geht von einer Startkonfiguration aus und führt zufällig Reihen- und Spaltenpermutationen durch, um ein zufälliges Rätsel zu erzeugen. Das wird mehrere tausend Male durchgeführt und das Rätsel mit dem Minimum an Punkten als Lösung ausgegeben.

Es kann aber durchaus sein, dass nicht alle Rätsel durch eine solche Permutation erzeugt werden können. Vermutlich ist es auch so, da das Minimum i. d. R. ziemlich schnell gefunden wird (meist genügen einige hundert Durchgänge).

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2008-08-17


Hallo zusammen!

Ich frage mich gerade, ob bei der minimalen Punktezahl nur diejenigen Gitter berücksichtigt werden, die eindeutig lösbar sind, oder auch mehrdeutige.

Bei n=2 erfüllen beide lateinischen Quadrate dieser Größe genau dieselben Gitter, welche alle 4 Punkte haben, die wahlweise schwarz oder weiß sind. Es gibt hier also keine überhaupt eindeutig lösbaren Gitter.

Bei n=6 (und vermutlich allen größeren Gittern) gibt es lateinische Quadrate mit 0 Punkten, aber die sind nicht eindeutig.

Gruß,
SirJective




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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2008-08-17


2008-08-17 13:32 - SirJective in Beitrag No. 12 schreibt:
Hallo zusammen!

Ich frage mich gerade, ob bei der minimalen Punktezahl nur diejenigen Gitter berücksichtigt werden, die eindeutig lösbar sind, oder auch mehrdeutige.

Bei n=2 erfüllen beide lateinischen Quadrate dieser Größe genau dieselben Gitter, welche alle 4 Punkte haben, die wahlweise schwarz oder weiß sind. Es gibt hier also keine überhaupt eindeutig lösbaren Gitter.

Bei n=6 (und vermutlich allen größeren Gittern) gibt es lateinische Quadrate mit 0 Punkten, aber die sind nicht eindeutig.

Gruß,
SirJective
[Die Antwort wurde nach Beitrag No.10 begonnen.]

Wie auch bei Sudokus sollten die Kropkis eindeutig sein, denn die Frage nach mehrdeutigen Kropki lässt sich schnell beantworten, wie du gezeigt hast.
Ich habe jetzt ein Programm geschrieben, dass zu einem Kropki per Backtracking alle Lösungen bestimmt. Das 8x8-Kropki ohne Punkte besitzt 68770 Lösungen, das 8x8-Kropki von Kay_S immer noch 22. Hier zwei der Lösungen:
Bild
Bild

@Kay_S: Du müsstest jetzt in dein Programm noch einbauen, dass nur eindeutig lösbare Kropkis gezählt werden. Allerdings verlangsamt das das Programm deutlich, denn schon für das Leere 8x8-Kropki braucht mein Programm eine halbe Minute (bei mehr Punkten geht es schneller, aber wir wollen ja möglichst wenig Punkte).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2008-08-17


Mir war gar nicht klar, dass es Gitter mit 0 Punkten gibt. Interessanterweise werden diese von meinem Programm nicht gefunden.
Die Eindeutigkeit gibt die Heuristik halt nicht her. Dazu ist ebenfalls ein exaktes (= langsames) Programm vonnöten.

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2008-08-17


Für einige (sehr) kleine Werte von n habe ich die Mindestzahl k von Punkten bestimmt, bei der das Gitter noch eindeutig lösbar ist, sowie die Anzahl a der Gitter mit dieser Punktezahl (ohne Herausfiltern von Spiegelung und Rotation).

n=2: kein eindeutiges Gitter
n=3: k=8, a=180
n=4: k=12, a=32
n=5: k=11, a=80
n=6: k=6, a=32
n=7: k=2, a=80

Gruß,
SirJective

PS: Kay, ich hab gerade gelesen, dass dudurch reine Zeilen- und Spaltenvertauschungen nicht alle lateinischen Quadrate bekommen kannst: Wie man auf en.wikipedia.org/wiki/Latin_square nachlesen kann, gibt es ab n=4 mehr als eine sogenannte "Isotopieklasse" von lateinischen Quadraten.


[ Nachricht wurde editiert von SirJective am 17.08.2008 23:12:49 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2008-08-17


Laut meinem Programm ist folgendes 6-Kropki und 7-Kropki eindeutig lösbar:

ein minimales 6-Kropki
ein minimales 7-Kropki

Können wir diese Bilder einigermaßen geschickt durch FedGeo ausdrücken? Dann könnte ich mein Programm so anpassen, dass es direkt FedGeo-Quelltext produziert. Bisher drücke ich nämlich z.B. das obere Bild so aus:
Kropki
[  ,  , b,ww,  ,  ]   "xy" = x nach unten, y nach rechts
[  ,  ,  ,  ,  ,  ]   "b" = schwarzer Punkt
[b ,  ,  ,  ,  ,  ]   "w" = weißer Punkt
[ww,  ,  ,  ,  ,  ]
[  ,  ,  ,  ,  ,  ]
[  ,  ,  ,  ,  ,  ]


Gruß,
SirJective

[ Nachricht wurde editiert von SirJective am 17.08.2008 23:54:03 ]

[ Nachricht wurde editiert von SirJective am 18.08.2008 00:01:12 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2008-08-18


2008-08-17 20:04 - SirJective in Beitrag No. 15 schreibt:
PS: Kay, ich hab gerade gelesen, dass dudurch reine Zeilen- und Spaltenvertauschungen nicht alle lateinischen Quadrate bekommen kannst: Wie man auf en.wikipedia.org/wiki/Latin_square nachlesen kann, gibt es ab n=4 mehr als eine sogenannte "Isotopieklasse" von lateinischen Quadraten.

So etwas ähnliches habe ich mir schon gedacht, dass aber bereits bei n=10 unvorstellbar viele Äquivalenzklassen existieren ist wirklich überraschend. Und so richtig viel scheint man über die Theorie dahinter auch nicht zu wissen.


Laut meinem Programm ist folgendes 6-Kropki und 7-Kropki eindeutig lösbar:

Kropkis mit wenig Punkten sind irgendwie schwieriger zu lösen :-) Insbesondere die schwarzen Punkte helfen einem ja bei der Lösung.

Beim fedgeo müsste man mal etwas experimentieren.

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2008-08-18


So könnte ein Kropki-Rätsel in fedgeo aussehen:

fed-Code einblenden

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, vom Themenstarter, eingetragen 2008-08-18


Ich hab mich noch nicht viel mit fedgeo beschäftigt, aber gibts da keine for-Schleifen? Ich werds später mal probieren, erstmal noch eine gif für ein eindeutiges 8x8er mit 2 Punkten:
Bild

Ich bin erstaunt, wie wenig Punkte man tatsächlich benötigt - per Hand lassen sich diese Rätsel wohl kaum noch lösen.

2 ist das Minimum für 8, es gibt kein eindeutiges Kropki mit nur einem Punkt.

[ Nachricht wurde editiert von philippw am 18.08.2008 01:43:08 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
fru
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 03.01.2005
Mitteilungen: 21456
Herkunft: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2008-08-18


Hallo Philipp und Kay!

2008-08-18 01:29 - philippw in Beitrag No. 19 schreibt:
Ich hab mich noch nicht viel mit fedgeo beschäftigt, aber gibts da keine for-Schleifen?

Doch, das gibt es, siehe hier und die Folgebeiträge.

Liebe Grüße, Franz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, vom Themenstarter, eingetragen 2008-08-18


Danke, hier mal mein erster Versuch:
fed-Code einblenden



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2008-08-19


So, hab mein Programm um eine fedgeo-Ausgabe ergänzt. Hier ein weiteres minimales 6-Kropki.

fed-Code einblenden

Die Enumeration aller eindeutigen 8x8-Kropki mit 2 Punkten läuft noch...

Eines meiner Hauptprobleme besteht darin, schnell genug zu erkennen, ob ein generiertes Kropki eindeutig lösbar ist: Das Programm braucht etwa eine Sekunde für diese Entscheidung.

Gruß,
SirJective




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
fru
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 03.01.2005
Mitteilungen: 21456
Herkunft: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2008-08-19


Hallo Christian!

Durch Einfügen des Befehls noaxis() ergibt sich noch eine kleine kosmetische Verbesserung, wie Du hier sehen kannst:

fed-Code einblenden

Liebe Grüße, Franz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2008-08-20


Wenn man es jetzt noch irgendwie hinbekäme, den weißen Punkten die Transparenz zu nehmen, so wären die Rätsel perfekt...  smile

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
fru
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 03.01.2005
Mitteilungen: 21456
Herkunft: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2008-08-20


fed-Code einblenden

So biggrin ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, vom Themenstarter, eingetragen 2008-08-20


Mit Kreisen statt Punkten geht das:  wink
fed-Code einblenden
EDIT: zu langsam ^^
EDIT: Da fällt mir grad was ein. Soll ich die ursprünglichen Rätsel auflösen, oder möchte noch jemand knobeln?

[ Nachricht wurde editiert von philippw am 20.08.2008 01:57:05 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Stefan_K
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.07.2005
Mitteilungen: 4363
Herkunft: Hamburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2008-08-20


Das Kropki-Gitter aus Beitrag 10 einmal mit tikz:
LaTeX
\begin{tikzpicture}[every node/.style={draw,circle,inner sep=2pt}]
\draw (0,0) grid (4,4);
\foreach \i / \j in {0.5/1,1/1.5,1.5/2,2/2.5,2.5/3,3/3.5}
  {\node[fill=black] at (\i,\j) {};
   \node[fill=white] at (\j,\i) {};}
\end{tikzpicture}
\usepackage{tikz} mit Standardklasse genügt.

Viele Grüße,

StefanK




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, vom Themenstarter, eingetragen 2008-08-21


Ich werde dann Sonntag die Lösungen, wenn vorher keiner was sagt.

@SirJective: Schafft dein Programm, ein 9x9 Rätsel mit wenigen Punkten zu finden? Meines findet gar keins in angemessener Zeit.

Gruß, Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2008-08-21


2008-08-20 04:31 - Stefan_K in Beitrag No. 27 schreibt:
Das Kropki-Gitter aus Beitrag 10 einmal mit tikz:
LaTeX
\begin{tikzpicture}[every node/.style={draw,circle,inner sep=2pt}]
\draw (0,0) grid (4,4);
\foreach \i / \j in {0.5/1,1/1.5,1.5/2,2/2.5,2.5/3,3/3.5}
  {\node[fill=black] at (\i,\j) {};
   \node[fill=white] at (\j,\i) {};}
\end{tikzpicture}
\usepackage{tikz} mit Standardklasse genügt.

Viele Grüße,

StefanK

Wenn ich das mit MiKTeX übersetze, bekomme ich folgende Meldung:
! Package tikz Error: I do not know what to do with the option ``every node/.st
yle={draw,circle,inner sep=2pt}''.

Bis auf tikz habe ich aber auch nichts weiter eingebunden.

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2008-08-23


Ich habe mit meinem Programm nach 8x8-Kropki mit 2 Punkten gesucht, und die Suche nach 75 Stunden und 580 gefundenen Kropki abgebrochen (ich musste leider den Rechner neu starten). In der Zeit wurden 15150 Kropki auf eindeutige Lösbarkeit untersucht.


Es gibt 41184 9x9-Kropki mit 2 Punkten, aber anscheinend braucht mein Programm mehrere Minuten, um eines von denen zu lösen. Vielleicht sollte ich doch von naivem Backtracking auf Knuths Algorithmus X zur Lösung dieses exakten Überdeckungsproblems umsteigen (vielleicht sogar implementiert mit Dancing Links). :-)

Gruß,
SirJective




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, vom Themenstarter, eingetragen 2008-08-23


2008-08-23 11:36 - SirJective in Beitrag No. 30 schreibt:
... anscheinend braucht mein Programm mehrere Minuten, um eines von denen zu lösen. Vielleicht sollte ich doch von naivem Backtracking auf Knuths Algorithmus X zur Lösung dieses exakten Überdeckungsproblems umsteigen (vielleicht sogar implementiert mit Dancing Links). :-)

Im Moment geht es mir auch so mit den mehreren Minuten, allerdings hat mein Programm bei den 9x9, die es bis jetzt untersucht hat, immer in ein paar Sekunden mehrere Lösungen gefunden (wenn auch nicht alle). Wahrscheinlich liegt das Minimum bei 9 höher als 2, da die 9 nur mit der 8 einen Punkt braucht und in vielen Fällen als "Puffer" dienen kann - deswegen gibt es mehr Lösungen bei wenigen Punkten.

Der Algorithmus X war mir bis gerade nicht bekannt, ich habe ihn mir jetzt  hier angeschaut. Für Sudokus mag das gehen, aber da sind die Zahlen nicht untereinander verknüpft, wie durch die Punkte beim Kropki. Mir fällt jetzt jedenfalls keine Möglichkeit ein, Kropki als eine exakte Überdeckung umzuformulieren. Hast du eine?

Gruß,
Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, eingetragen 2008-08-23


2008-08-23 14:14 - philippw in Beitrag No. 31 schreibt:
Mir fällt jetzt jedenfalls keine Möglichkeit ein, Kropki als eine exakte Überdeckung umzuformulieren. Hast du eine?

Hm, schauen wir mal.

Vorneweg: Es gibt eine Erweiterung von Algorithmus X mit "sekundären Spalten", Spalten, bei denen höchstens eine 1 überdeckt sein darf, möglicherweise auch gar keine. Diese Erweiterung wird z.B. beim n-Dame-Problem genutzt, um die Diagonalen zu repräsentieren: Auf jeder Diagonale darf höchstens eine Dame sein.

Betrachten wir als Beispiel folgendes 3x3-Kropki.
fed-Code einblenden

Algorithmus X arbeitet mit einer Datenmatrix, deren Zeilen die Belegungen der Gitterzellen mit Werten beschreiben, und deren Spalten die dadurch erfüllten Bedingungen beschreiben.


Wir haben eine Matrix-Zeile für jede Kombination von Zelle und Zahlenwert, die ich hier mit folgendem Format beschreibe: "Zeile,Spalte=Wert" (das ist jeweils der Name der Zeile). Für ein n-Kropki haben wir n^3 Zeilen, von "1,1=1" bis "n,n=n".

Zum Beispiel geben die folgenden drei Zeilen die möglichen Werte von Zelle 1,1 (links oben) in einem 3x3-Kropki an:
"1,1=1"
"1,1=2"
"1,1=3"


Die Datenmatrix hat primäre Spalten, die die Zeilen- und Spalten-Bedingungen des lateinischen Quadrates beschreiben, z.B. die Spalte "Wert 2 in Zeile 1", die ich in Analogie zum Zeilennamen "1,.=2" nenne (der Punkt repräsentiert die ungenannte Koordinate).

Das sind für ein n-Kropki 3*n^2 Spalten.


In der Matrix sind nun die Felder mit einer 1 belegt, die ausdrücken, dass die Bedingung einer Spalte durch die Belegung in einer Zeile erfüllt wird. So hat die Zeile "1,1=2" eine 1 in den Spalten
"1,1=." (Wert von Zelle 1,1 ist belegt),
"1,.=2" (Wert 2 in Zeile 1 ist belegt) und
".,1=2" (Wert 2 in Spalte 1 ist belegt).


Ob und wie sich die Kropki-Punkte durch Spalten (primäre oder sekundäre) darstellen lassen, überlege ich mir im nächsten Beitrag.

Gruß,
SirJective




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.33, eingetragen 2008-08-23


Wie wäre es hiermit...

Der weiße Punkt zwischen Zellen 1,1 und 1,2 im 3x3-Beispiel erfordert, dass von den folgenden Kombinationen der beiden Zellen mindestens eine zutrifft:
1,1=1 und 1,2=2
1,1=2 und 1,2=1
1,1=2 und 1,2=3
1,1=3 und 1,2=2

Die 2 ausgeschlossenen Kombinationen (von den insgesamt 6 im lateinischen Quadrat möglichen) sind:
1,1=1 und 1,2=3
1,1=3 und 1,2=1

Für jede der unerlaubten Kombinationen gilt, dass von den beiden angegebenen Zell-Belegungen höchstens eine gewählt werden darf. Das legt nahe, für jede diese Kombinationen eine sekundäre Spalte in der Datenmatrix anzulegen:
"1,1=1 und 1,2=3" (mit einer 1 in Zeilen "1,1=1" und "1,2=3")
"1,1=3 und 1,2=1" (mit einer 1 in Zeilen "1,1=3" und "1,2=1")

In der (einzigen) Lösung des 3x3-Beispiels ist die Spalte "1,1=1 und 1,2=3" nicht erfüllt (das ist OK für eine sekundäre Spalte), und die Spalte "1,1=3 und 1,2=1" ist durch Zeile "1,1=3" erfüllt.


Ein weißer oder schwarzer Punkt lässt sich also durch sekundäre Spalten beschreiben, die die Belegungs-Kombinationen ausdrücken, in denen die beiden Zahlen nicht die jeweilige Bedingung erfüllen. Ein fehlender Punkt lässt sich durch sekundäre Spalten beschreiben, die die Belegungskombinationen ausdrücken, in denen die beiden Zahlen eine Weiß- oder Schwarz-Bedingung erfüllen.

Übrigens kann man sekundäre Spalten auch durch primäre Spalten ersetzen, indem man Hilfszeilen einfügt, die nur in dieser einen Spalte eine 1 haben, und selektiert werden, wenn keine "normale" Zeile diese Spalte belegt. Auf diese Weise bekommen wir ein exaktes Überdeckungsproblem im klassischen Sinne.

Gruß,
SirJective


[ Nachricht wurde editiert von SirJective am 23.08.2008 16:37:29 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Stefan_K
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.07.2005
Mitteilungen: 4363
Herkunft: Hamburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.34, eingetragen 2008-08-23


Hallo Kay,

2008-08-21 20:23 - Kay_S in Beitrag No. 29 schreibt:
Wenn ich das mit MiKTeX übersetze, bekomme ich folgende Meldung:
! Package tikz Error: ...

evtl. wird das durch ein Update auf die aktuelle Version von TikZ behoben, wenn Du sie nicht bereits verwendest. Ohne every node geht es auch so:
LaTeX
\begin{tikzpicture}
\draw (0,0) grid (4,4);
\foreach \i / \j in {0.5/1,1/1.5,1.5/2,2/2.5,2.5/3,3/3.5}
  {\node[draw,circle,inner sep=2pt,fill=black] at (\i,\j) {};
   \node[draw,circle,inner sep=2pt,fill=white] at (\j,\i) {};}
\end{tikzpicture}
Ggf. können wir auch gern weiteres im LaTeX Forum besprechen.

Viele Grüße,

StefanK




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.35, vom Themenstarter, eingetragen 2008-08-31


2008-08-21 16:00 - philippw in Beitrag No. 28 schreibt:
Ich werde dann Sonntag die Lösungen, wenn vorher keiner was sagt.

Zum Glück hab ich nach nicht gesagt, welche Woche...
Hier also die Lösungen:



Den Algorithmus hab ich jetzt durchblickt und sobald ich Zeit hab, werde ich mal versuchen, ihn in C zu implementieren. In welcher Sprache schreibst du, SirJective?

Gruß, Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.36, eingetragen 2008-08-31


Ich schreibe in java, habe aber an dem Thema nicht mehr weiter gearbeitet, nachdem meine Dancing Links etwa 4mal so lange brauchen wie das naive Backtracking.

Gruß,
SirJective



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1644
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.37, eingetragen 2008-09-11


Hallo Philipp!

Nach welchem Verfahren ist eigentlich das obige 9x9 Kropki mit 24 weissen und 11 schwarzen Punkten erzeugt worden? Zum Prüfen der Eindeutigkeit eignet sich ja Backtracking.

Viele Grüße
Ronald




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.06.2005
Mitteilungen: 1146
Herkunft: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.38, vom Themenstarter, eingetragen 2008-09-12


2008-09-11 20:26 - Delastelle in Beitrag No. 37 schreibt:
Hallo Philipp!

Nach welchem Verfahren ist eigentlich das obige 9x9 Kropki mit 24 weissen und 11 schwarzen Punkten erzeugt worden? Zum Prüfen der Eindeutigkeit eignet sich ja Backtracking.

Viele Grüße
Ronald

Verfahren? Ich habe mir ein leeres 9x9-Gitter genommen, es Zeile für Zeile so gefüllt, dass die Bedingung "jede Zahl pro Zeile/Spalte einmal" erfüllt ist (da gibts einen Satz der Kombinatorik, dass dies immer geht, wenn man immer auf die ganze Zeile achtet), und dabei am Anfang möglichst wenig Punkte entstehen. Wie man sieht habe ich unten angefangen, oben ließen sich viele Punkte nicht mehr vermeiden. Und als es fertig war, hab ich alle Punkte eingemalt, sie in ein leeres Gitter übertragen, und versucht, das Rätsel zu lösen. Es war eindeutig, folglich war ich fertig. Es ist also vollständig per Hand entstanden. Könnte eigentlich jeder, aber das muss man ja nicht so laut sagen. ;-)

Gruß, Philipp



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
philippw hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Bitte poste Lösungen zu dieser Aufgabe nur dann im Forum, wenn der Themensteller das verbal in seinem Aufgabentext erwähnt hat. Sonst antworte ihm in einer privaten Nachricht. (Hinweis: Diese Knobelaufgabe wurde gestellt, bevor es die explizite Einstellung 'Antworten nur mit privater Nachricht' gab.)
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]