Sonstiges: Rätsel
Heute hat mir ein Arbeitskollege ein ziemlich fieses Rätsel gezeigt. Gegeben eine 6x6 Matrix, in der vier verschiedene Symbole/Zahlen je vier mal vorkommen. Die restlichen Felder sind leer. Nun soll die Matrix in vier Segmente aufgeteilt werden, so dass die Segmente die gleiche Form und Größe haben und jedes Symbol in jedem Segment genau einmal vorkommt.
| 1 | 2 | ||||
| 3 | 2 | 4 | |||
| 4 | 1 | 4 | |||
| 3 | 3 | ||||
| 2 | 1 | 2 | |||
| 3 | 1 | 4 |
Das Rätsel fand ich schon ziemlich schwer (mit Probieren kann man die Lösung jedoch nach einiger Zeit finden). Doch noch schwieriger ist die Verallgemeinerung. Ein Lösungsalgorithmus müsste alle möglichen Aufteilungen einer axb-Matrix in n gleiche Segmente errechnen (der abschließende Filter nach der richtigen Aufteilung der Symbole ist dann leicht).
Welche Programmiersprache eignet sich für Probleme dieser Art am besten? Der intuitivste Ansatz ist wahrscheinlich ein Backtracking-Algorithmus, das würde für logische oder funktionale Sprachen sprechen. Der Backtracking-Algorithmus müsste allerdings Felder an beliebiger Stelle an das bereits bestehende Segment anfügen können - nur verlängern eines Pfades dürfte wegen der Möglichkeit der Verzweigung nicht reichen. Effiziente Array-Operationen sollten also verfügbar sein. Weiteres nicht unwesentliches Problem ist die Wahl der Startkonstellation (bei n=4 noch ziemlich leicht: die vier Ecken). An die Komplexitätsfrage wage ich noch nicht mal zu denken...
Ideen oder Links sind herzlich willkommen. Aber jetzt erst einmal viel Spaß beim Lösen des Beispiels.
Tags: rätsel matrix segmentierung algorithmus backtracking problem komplexität
1 Comments:
Oh, heute hat mich ja ein Kumpel von den Socken gehauen. Ich habe ihm das Problem erklärt und er hatte sofort eine Idee, auf die ich die ganze Zeit nicht gekommen bin, obwohl sie bestechend einfach ist. Beim draufrumdenken fahren die Denkmuster eben doch irgendwann einmal fest.
Ich hatte ja die ganze Zeit überlegt, wie man rekursiv von den Ecken aus eine Form suchen könnte. Sein Gegenentwurf war der Mittelpunkt (geht nur bei gleichseitigen Figuren). Wenn man vom Mittelpunkt ausgehend einen beliebigen, sich selbst nicht schneidenden Weg zum Rand einzeichnet und den entsprechend rotiert hat man eben die gesuchten Flächen. Tip: Auch unsere Lösung lässt sich auf diese Weise konstruieren!
Es gibt allerdings einen Haken, es lassen sich einige wenige zusätzliche Segmentierungen, z.B. senkrechte Balken, finden, die mit dem geschilderten Algorithmus nicht gefunden werden.
Lessons learned: Probleme mit Anderen diskutieren ist fast immer sinnvoll!
Post a Comment
<< Home