Mathe-Rätsel #001: Matrizen-Sudoku

Question

Ich starte einfach mal eine kleine Mathe-Rätsel-Reihe :-) Diese Aufgabe war ursprünglich für meine Tutanden gedacht (als Versuch, die Prüfungsvorbereitung etwas „spannender“ zu gestalten).

Die Aufgabe:

Gegeben sei das folgende Sudoku-Rätsel:

Für dieses gelten die „Standard-Regeln“ eines \(9\times 9-\)Sudokus. D.h. konkret:

1.) Es dürfen nur die Ziffern \(1\) bis \(9\) verwendet werden.

2.) In jeder Zeile dürfen die Ziffern von \(1\) bis \(9\) nur einmal vorkommen.

3.) In jeder Spalte dürfen die Ziffern von \(1\) bis \(9\) nur einmal vorkommen.

4.) In jedem schwarz umrandeten \(3\times 3-\)Block dürfen die Ziffern von \(1\) bis \(9\) nur einmal vorkommen.

Neu ist folgende Regel: 

5.) Jede gestrichelt umrandete (farbige) \(2\times 2-\)Matrix ist nicht invertierbar. 

Welche Implikationen Regel \(5\) hat ist Teil des Rätsels (demnach würde ein vorzeitiger Blick auf die „Inspirationsquelle“ den Lerneffekt schmälern). 

Frohes Puzzeln!

Inspiriert wurde dieses Rätsel durch: 

[spoiler]

https://puzzling.stackexchange.com/questions/52327/the-determinant-sudoku

[/spoiler]

Comments

Wer sich das Rätsel gerne ausdrucken möchte, kann sich das dazugehörige PDF-File hier (0,1 MB) oder hier herunterladen.

Wer generell Spaß an Sudoku-Rätseln hat und gerne Japanisch lernen möchte, kann sich die ersten Kanji für \(1\) bis \(9\) mit meinem kleinen Rätselheft beibringen: https://github.com/cyber-security-online/JapaneseSudoku/blob/master/Examples/sudoku_example_german.pdf

Wer mit den Rätseln durch ist und weitere braucht, kann sich gerne mein Programm herunterladen, mit dem man Rätselhefte beliebiger Größe erzeugen kann. Nach dem Starten fällt ein TeX-Dokument heraus, das dann nur noch kompiliert werden muss. Den Code gibt es ebenfalls in diesem Repository: https://github.com/cyber-security-online/JapaneseSudoku

---

Hi André,

hat das schon einer Deiner Studenten gelöst? :P

Als Einstieg finde ich da viel zu viele Möglichkeiten. Das Quadrat rechts oben hielt ich für einen guten Anfang, aber da gibt es ja schon ziiig Möglichkeiten. Matrizen mit der Diagonalsumme 8/12/18/24 kommen in Frage, wenn ich es recht sehe und die Diagonalen können recht wild getauscht werden. Würde man da mal aber anfangen ist schon das Quadrat darunter ein Killer :P. In die Verschachtelung links hab ich mich schon gar nicht getraut, auch wenn sich da wahrscheinlich viel auflösen würde :P. Sind aber immer noch viel zu viele Möglichkeiten?! Mehr Fleiß als Rätseln.

Oder hast Du da einen Tipp für eine sinnvolle Herangehensweise?

---

Also die Zahlen 7 und 5 können in den nicht invertierbaren Matrizen nicht vorkommen.

Und es gilt $$ i^i e^{ \frac{\pi}{2} } \cdot \big| -2 \sqrt{10} +3i \big| = 7 $$

Und für die Matrizen muss gelten $$ \det(M) = 0 $$

---

Hallo André,

auf Deinen Tipp war ich auch schon gekommen aber nach dem ersten Dutzend Zahlen komme ich (noch) nicht weiter.

Bleibt noch die Frage, ob es überhaupt möglich ist, dieses Sudoku ohne Probieren, also rein nach logischen Überlegungen mit eindeutigen Schlüssen für jedes Feld, zu lösen? Ist das möglich?

Danke für den Link auf Dein Java-Programm, dann hänge ich meine Variante in C++ doch gleich dazu.

---

ullim schrieb: "Also die Zahlen 7 und 5 können in den nicht invertierbaren Matrizen nicht vorkommen." Antwort: Jein!

---

Zumindest nicht in den Matrizen die komplett in einem 3 x 3 Kästchen liegen. Da hast Du Recht.

---

@ullim

Also die Zahlen 7 und 5 können in den nicht invertierbaren Matrizen nicht vorkommen.

Richtig \(\surd\)

Zumindest nicht in den Matrizen die komplett in einem \(3\times 3\) Kästchen liegen.

Und auch nicht bei den anderen. Das ergibt sich aus der Konstellation, wie die Matrizen überlappt sind und die Position der vorgegebenen Zahlen.

Die Schwierigkeit war für mich, so viele Zahlen an den richtigen Positionen vorzugeben, dass das Rätsel trotzdem eindeutig lösbar ist. Meine Studies haben lediglich einen Tipp bekommen und es ist trotzdem eindeutig lösbar (ob das jemand herausbekommen hat, erfahre ich morgen). Man muss also nicht raten.

Das ist wirklich eine harte Nuss, doch gerade das macht es so unterhaltsam!

@Werner-Salomon

Klasse Solver. Zu diesem Zeitpunkt war ich noch in der Schule :-D Jetzt haben wir einen für Java und C++. Hat vlt. jemand Lust einen für Python, Haskell, ... zu schreiben?

Wie steht ihr eigentlich generell zu Sudokus? Ich habe, nachdem ich mir in der Schule einen Solver geschrieben hatte, irgendwie die Lust daran verloren ... im Prinzip spult man ja auch nur einen Algorithmus ab. Bei interessanten Variationen steige ich aber immer wieder gerne ein!

---

André: "... es ist trotzdem eindeutig lösbar (ob das jemand herausbekommen hat, erfahre ich morgen). Man muss also nicht raten." Zwischen eindeutig lösbar und nicht raten müssen besteht kein kausaler Zusammenhang. Schau meinen Lösungsversuch unten an - geht das ohne Raten weiter?

Gruß Werner

---

@Werner-Salomon

Das stimmt. Ein kausaler Zusammenhang muss hier nicht bestehen. Die computergenerierte Lösung erhalte ich auch! So wie Dein aktueller Stand sah es bei mir auch nach ca. einer halben Stunde auch aus.

Notierst Du Dir (gedanklich oder bei Bedarf auch auf Papier), welche Zahlen in den einzelnen Feldern möglich sind? Mir hilft das meistens sehr.

geht das ohne Raten weiter?

In- oder exklusive Deiner Annahmen? In beiden Fällen lautet die Antwort Ja. Im zweiten Fall dürfen die Annahmen keine Annahmen bleiben.

Booh - das kann ja jeder (der programmieren kann)

Stimmt schon. Da meine Tutanden allerdings parallel Vorlesungen zur Softwareentwicklung besuchen, ist das in meinen Augen legitim. Lernziele sind in meinen Augen:

- Umgang mit komplexen Zahlen

- Verstehen des Zusammenhangs zwischen Invertierbarkeit, Rang, Determinante, ...

- Verständnisentwicklung für klassische Problemlösungsstrategien eines Informatikers, ...

Ich werde nächsten Monat eine Komplettlösung entwerfen ... momentan habe ich sehr viele Projekte (Prüfungen, Abschlussarbeit, Apps, ...).

---

Ich befürchte, dass wohl in absehbarer Zeit keine Lösungen mehr gepostet werden ... meine Studies haben das leider auch nicht hinbekommen :-( Am Sonntag 23:59:59 vergebe ich den Stern ;-)

---

ich schrieb: "'Also die Zahlen 7 und 5 können in den nicht invertierbaren Matrizen nicht vorkommen.' Antwort: Jein!" Falsch! - die Antwort ist Ja! und auch ohne die Einschränkung die André genannt hat.

Sollte eine 5 oder 7 in einer Matrix stehen, so müsste ja auch in dem Produkt der jeweils anderen Diagonale der Matrix der Teiler 5 bzw. 7 enthalten sein. Das wäre aber nur mir einer weiteren Zahl 5 bzw. 7 möglich, da wir ja auf die Zahlen 1 bis 9 beschränkt sind. Die würde sich dann aber in der gleichen Zeile oder Spalte befinden, und wären daher nach den üblichen Regeln im Sudoko dort nicht zulässig.

André schrieb: "Wie steht ihr eigentlich generell zu Sudokus? Ich habe, nachdem ich mir in der Schule einen Solver geschrieben hatte, irgendwie die Lust daran verloren ... im Prinzip spult man ja auch nur einen Algorithmus ab. Bei interessanten Variationen steige ich aber immer wieder gerne ein!" Das geht mir ganz genauso. Meinen Solver habe ich übrigens in 2005 für Project-Euler geschrieben - da warst Du schon geboren ;-). (Original-)Sudoko finde ich inzwischen langweilig. Ich beschäftige mich wenn überhaupt inzwischen mehr mit Str8ts.

André schrieb: "Notierst Du Dir (gedanklich oder bei Bedarf auch auf Papier), welche Zahlen in den einzelnen Feldern möglich sind? Mir hilft das meistens sehr." Ja klar; ich mache Striche in ein freies Kästchen, so angeordnet wie auf einer Telefontastatur; und zwar genau dann, wenn eine Zahl nur noch an zwei Stellen innerhalb eines Blocks auftauchen kann.

---

@Werner-Salomon

Meinen Solver habe ich übrigens in 2005 für Project-Euler geschrieben - da warst Du schon geboren ;-)

Ja, das war gerade so der Übergang aufs Gymi und meine ersten Programmier-Gehversuche :-D An den Aufgaben von Project-Euler habe ich schon lange nicht mehr getüftelt. Str8ts habe ich auch eine Zeit lang gerne gemacht. Jetzt habe ich die Motivation, dafür auch einen Solver zu schreiben. Ich gehe mal davon aus, dass Du das schon gemacht hast, oder? :-)

Tredoku ist eine tolle Sudoku-Variation. Kakuro würde Dir bestimmt auch gefallen!

---

@Werner-Salomon

Ich plane in regelmäßigen Abständen weitere solche „Kopfnüsse“ hier auf der Mathelounge/auf meinem Blog zu veröffentlichen. Wäre es in Ordnung für Dich, wenn ich den/die „Gewinner“, mit den kreativsten Lösungen auf meiner Seite verlinke?

---

Am Montag poste ich hier eine etwas leichtere Version von dem obigen Rätsel (also mehr Hinweise an den „richtigen“ Stellen).

---

André schrieb: "Wäre es in Ordnung für Dich, wenn ich den/die „Gewinner“, mit den kreativsten Lösungen auf meiner Seite verlinke?" Da habe ich nichts dagegen. Was hier geschrieben steht, ist eh' alles öffentlich.

---

Wie versprochen: Die „Einsteiger“-Variante :-)

---

Nun war das Rätsel gut lösbar :D.

Danke ;).

---

Gerne doch;-) Freut euch auf das nächste!

---

Das rätsel ist aber leichter als das aus dem Tutorium XD

---

Das rätsel ist aber leichter als das aus dem Tutorium XD

Stimmt :-) Du kannst es ja jetzt noch einmal in der obigen Form versuchen. Da Du die Prüfung bereits erfolgreich bestanden hast, ist das kein Muss :-D

---

Haha, ja :-) Kannst Du auch für Diskrete Mathe so ein Rätsel machen?

---

Kannst Du auch für Diskrete Mathe so ein Rätsel machen?

Kann ich schon :-) Ihr müsstet mir aber vorher rückmelden, was ihr gerne üben wollt. Einfach nur etwas

für Diskrete Mathe

ist doch etwas weit gegriffen ;-)

Answer 1

Hallo André,

Du schriebst: "Es ist nicht verboten, sich ein Programm zum Lösen des Sudokus zu schreiben" Booh - das kann ja jeder (der programmieren kann) Dann kommt dies dabei heraus:

[spoiler]

485 769 213
796 123 845
132 485 967

514 876 329
328 951 674
967 342 158

649 237 581
851 694 732
273 518 496

[/spoiler]

Ohne Kollege Computer bin ich lange nicht so weit gekommen.

[spoiler]

 

Die schwarzen Zahlen kann man direkt ableiten. Die beiden 4'en in der gelben Matrix habe ich vermutet. Dort könnte auch noch eine 4-9-Kombination stehen. Aus diesen beiden 4'en folgen dann alle grauen Zahlen.

[/spoiler]

Aber dann war ich mit meinem Latein am Ende .. Vielleicht sieht jemand noch irgendetwas, wie man rein logisch Zahl für Zahl weiter kommt.

Gruß Werner

Edit: Feld b3 (Schachbrettkoordinaten) ist korrigiert (war vorher 9)

Comments

81      ≠       36

---

Stimmt!              .. da kommt rechts unten eine 4 hin. Falsch abgeschrieben!

---

Hallo André,

Ja - Dein Sudoku lässt sich auch ohne Kollege Computer lösen. Mein Fehler mit der 4, auf den mich erst Gast_hj2166 aufmerksam gemacht hat, hatte mich zunächst behindert.

[spoiler]

Mit der 4 lassen sich nämlich alle Zahlen in der Matrix im Block links oben eintragen, da dann die Zahl unten rechts in der Matrix keine 8 sondern nur eine 2 sein kann. Dadurch löst sich auch die obere Matrix im mittleren Block oben - hier war nur noch offen, wo die 6 und wo die 3 hinkommt. So sieht das dann mit meinem Sudoku-Analyser aus:

Die kleinen grauem Ziffern geben an, welche Zahlen in dem noch nicht belegtem Feld noch möglich sind. Und dann leuchtet auch schon eine 6 rot auf, dort ist ist die einzige Stelle in dieser Zeile, die noch eine 6 aufnehmen kann.

Mit der 6 lässt sich dann auch die Matrix an Position g7 füllen. Und da in der Matrix darüber keine 6 mehr vorkommt, ist auch klar, dass im Feld ganz oben rechts nur noch eine 3 hinkommen kann. Und die Belegung der Matrix darüber ist dann auch eindeutig.

 

nach den üblichen Sudokoregeln können weitere Felder sicher gesetzt werden (s.o.).

Und die Ausführung vom Rest spare ich mir jetzt einfach. Es ist machbar.

[/spoiler]

Gruß Werner

---

Herzlichen Glückwunsch Werner-Salomon zu Deiner hervorragenden Lösung! Du bist verlinkt ;-)

und weiterhin viel Spaß beim Rätseln!