The Net Wizard HauptseiteISP SetupNetzwerkeVelotourenSoftwareKryptografieVaria

Nsudoku

  1. Aufgabenstellung
  2. Es geht darum, die Zahlen 1 bis 9 so in einem 9x9 Quadrat zu verteilen, dass jede Zahl in jeder Zeile und Spalte genau einmal vorkommt. Zudem muss dasselbe für jedes der dunkel umrandeten 3x3 Quadrate erfüllt sein. Ein Beispiel sagt mehr, als tausend Worte. Darum zeige ich hier einmal eine mögliche Lösung für das Problem. Man beachte die Symmetrien in den Diagonalen.

    198
    627
    543
    765
    384
    219
    432
    951
    876
    765
    384
    219
    432
    951
    876
    198
    627
    543
    432
    951
    876
    198
    627
    543
    765
    384
    219
  3. Der Algorithmus
  4. Ursrünglich wollte ich sätliche müglichen Lösungen berechnen. Davon musste ich dann nach circa zwei bis drei Tagen Laufzeit auf einem 3GHz Prozessor Abstand nehmen. Es gibt schlicht zu viele Lösungen. Aber das ist der Grund, aus dem ich mich für diesen Algorithmus entschieden habe. Er lässt sich in einfache Schritte unterteilen.
    Man durchquert das Feld von links oben nach rechts unten.
    links oben setzt man eine 1, bei jedem neuen Feld erhöht man um diese Laufvariable um 1, falls man bei 9 angelangt ist, setzt man die Laufvariable wieder auf eins.
    Nachdem man jeweils ein Feld neu besetzt hat, schaut man ob mit dieser Konstelation eine Lösung möglich ist. Falls dies nicht der Fall ist, geht man ein Feld zurück und erhöt dort die Laufvariable um eins.
    Sobald man eine Lösung gefunden hat (also beim letzten Feld angekommen ist, , schreibt man sie in eine Datei, und erhöht das letzte Feld.

    Wenn man so vorgeht, fängt man mit den Zahlen eins bis neun in der ersten Spalte an. Danach kommt man zur zweiten Spalte. Dort würde man eine eins einsetzen, das widerspricht aber den Regeln. Also erhöht man auf zwei. Geht wieder nicht, dasselbe gilt für die drei. Folglich macht man mit vier weiter, was funktioniert. Man kann also ein Feld weiter gehen. Dort kommt die fünf rein, was wieder geht.

  5. Der Code
  6. Ein Tarball mit dem Code findet sich hier

Powered by w3.css