Archive for Januar, 2006

Sudokus generieren – Teil 2

Samstag, Januar 28th, 2006

SudokuVor kurzem berichtete ich über eine Methode Sudokus zu generieren. Leider war der vorgestellte Algorithmus sehr zeitkomplex. Durch einen Benutzer von Mobile Sudoku wurde ich auf eine alternative schnelle und interessante Generierungsmethode aufmerksam gemacht.

Man geht von einer großen aber überschaubaren Menge von Sudokus aus, die man mit einem aufwändigeren Verfahren erzeugt hat. Diese „Ausgangspopulation“ von sagen wir 100 Rätsel kann man zu einer sehr großen Menge verschiedener Rätsel ausweiten indem man eine beliebige Anzahl folgender Mutationsschritte auf einem Rätsel durchführt:

  • Vertauschen der Bockspalten: Im Beispiel vertauscht man den blau markierten Bereich mit dem grünen Bereich. Man erhält wiederum ein gültiges Sudoku.
  • Vertauschen von Blockzeilen: Was oben für Blockspalten funktioniert, gilt ebenso zur Blockzeilen. Drei verschiedene Vertauschungen sind möglich.
  • Vertauschen von Einzelspalten: Innerhalb einer Blockspalte kann man jeweils zwei Spalten vertauschen und alle Sudokuconstraints bleiben erhalten. Im Beispiel sind dies die rote und die gelbe Spalte.
  • Vertauschen von Einzelzeilen: Keine große Ãœberraschung. Die Sudokueigenschaften bleiben auch hier erhalten!

Auf diese Weise erhält man aus jedem Rätsel der Ausgangsmenge 3^10 neue Rätsel! Jippie!

Was machen Roboterfische im Dunkeln?

Mittwoch, Januar 25th, 2006

RoboterfischDie Frage ist so alt wie es Kühlschränke gibt. Bleibt das Licht wirklich aus wenn die Kühlschranktür zu ist.. oder was machen Roboterfische wenn sie sich alleingelassen glauben? Dank der Webcam von Alexander Hörnlein kann man zumindest letzteres jetzt feststellen. Die Webcam zeigt Tag und Nacht den Blick auf das High-Tech Aquarium!

Weitere Links:

  • Roboterfische in London
  • Sudokus lösen

    Samstag, Januar 21st, 2006

    SudokuVor einiger Zeit habe ich an dieser Stelle über das Problem des Sudoku Generierens berichtet. Heute möchte ich einen Algorithmus zum Lösen vorstellen, wie er so ähnlich in Mobile Sudoku implementiert ist:

    • Einfaches Einschränken – Man trage alle 9 Zahlen in jedes freie Feld ein und streicht all die, die in der Zeile, Spalte oder dem Teilbereich vorkommen.
    • Zahl setzen – Wenn in einem Feld nur eine einzelne Möglichkeit verbleibt, trägt man diese als sicher ein und beginnt von vorne.
    • Weiteres Einschränken – Kommen zwei Zahlen in einer Zeile (Spalte/Teilbereich) in zwei Feldern jeweils beide exclusiv vor kann man diese Zahlen aus allen anderen Feldern dieser Zeile (Spalte, Teilbereich) streichen.
      Analog geht dies für 3 Zahlen in 3 Feldern und 4 Zahlen in 4 Feldern…
    • Einschränken Stufe Zwei – Kommen zwei Zahlen nur in zwei Feldern vor und in keinem anderen, so kann man alle anderen Zahlen aus den zwei Feldern streichen.
      Wiederum funktioniert dies analog für drei, vier und fünf Zahlen.
    • Einschränken Stufe Drei – Kommt eine Zahl z in einer Spalte s (bzw. Zeile) eines Teilbereiches vor und ist aber für jede anderen Zeile des Teilbereiches ausgeschlossen, so kann man die Zahl aus allen Feldern der Zeile s außerhalb des Teilbereiches streichen.

    Mit diesen Einschränkungsregeln solltet Ihr euer Sudoku in die Knie zwingen. Ansonsten ist es mit großer Wahrscheinlichkeit nicht eindeutig lösbar.

    Kontakte knüpfen!

    Freitag, Januar 13th, 2006

    Der Bruder von der Schulkameradin meiner Freundin hat mal in der Band mit jemanden gespielt, der kennt Bruce Springsteen. Ich glücklicher Pilz, vielleicht krieg ich deswegen ja mal ne Autogrammkarte. Das Besondere ist weniger, dass der Link besteht sondern vielmehr dass er aufgedeckt wurde (und außerdem ist er erfunden)

    Die Theorie besagt ja, dass man über sechs Links jeden auf der ganzen Welt kennt. Man weiss es nur nicht! Ich weiss zwar nicht genau wie die Theorie überprüft worden ist, aber die neuen Bussinesskontakt- oder Relationships-plattformen geben schon eine kleine Ahnung davon.

    In den letzten Tagen habe ich eine Einladung zu openBC bekommen.. Etwas voreingenommen probierte ich es aus. Ca. ein Jahr zuvor hatte ich LinkedIn getestet und war nicht so überzeugt. Damals fehlte noch die kritische Masse… Aber nun scheint die Zeit reif für solche Dienste. Jedenfalls hatte ich schon kurz nach der Anmeldung und ohne dass ich selbst großartig Einladungen verschickt habe, ca 20 Kollegen, Freunde und Familienmitglieder gefunden.

    Picke ich mir einen beliebigen Friseur aus Berlin (ich wohne selbst im Süden) kenne ich ihn mit ziemlicher Sicherheit über 5 oder 6 Ecken. Nun ich bleibe aus praktsichen Gründen dennoch bei meinem Friseur mit einer Ecke, aber man weiss ja nie wozu es mal gut ist. Es gibt ja noch andere Recherchemöglichkeiten: Wo sind ehemalige Kommilitonen gelandet ? Wohnt mein Jugendgruppenleiter immer noch in München?

    Faszinierend…! Aber auch ein bischen beängstigend. Wer kennt wen.. wer hat wo wann gearbeitet,… Mann stelle sich vor, man wüsste all das über Politiker (also die Leute mit den Geldkoffern NICHT eintragen!). Vielleicht interessierts auch den Konkurrenten..nur nicht die Beziehung zu Kunden angeben, sonst schnappt er ihn weg.

    Tja jetzt fällt mir gar kein Fazit ein… gut oder schlecht…sagen wir einfach mal „interessant“ 🙂

    News: Neuer Cocktail-Assistent

    Samstag, Januar 7th, 2006

    Flaschen

    Seit heute ist „Mobile Cocktails“ – ein interaktives Rezept-Handbuch und Barverwaltungsprogramm – auf dem Markt. Ich werde es nicht reviewen, weil ich nicht objektiv sein kann. Aber ein bischen die Busch- bzw. Werbetrommel rühren ist nicht verkehrt 🙂 Vielleicht kennt Ihr das große Problem, wenn man zuhause vor den Flaschen steht. Man weiss einfach nicht, was man alles mixen kann … und wenn man ins Cocktailbuch blickt, sieht man lauter leckere Rezepte, für die man die entsprechenden Zutaten nicht hat.

    Jetzt kommt Hilfe mit dem PDA! Flugs alles eingegeben was man in seiner Bar hat und der elektronische Helfer ermittelt gleich, welche Rezepte überhaupt in Frage kommen. Noch besser ist, dass man auf jeder Party sein Rezeptbuch zücken kann, weil man ja das Smartphone oder den PDA auch meist dabeihat..und wer trägt schon die dicke Cocktailbibel als Paperback durch die Gegend. (mehr …)