Die richtige Datenstruktur zu repräsentieren, ein Sudoku-Rätsel?

Eigentlich, baute ich wie ein Tier, das sowohl einen solver und einen generator, und ich habe ein 2D-array. Es hat gut funktioniert.

Sie musste einfach verstehen, die Indizes und wo Sie waren, und das war nicht allzu schwer zu meistern.

Die relativen Beziehungen zwischen den Zellen in einer Zeile nicht ändern, abhängig von der Spalte, das gleiche gilt für Zellen in einer Spalte, oder sogar Zellen in einem mini-Quadrat.

Manchmal einen weniger "elegante" Lösung ist, einfach gut. In der Tat, manchmal, es ist besser 🙂

Für was es Wert ist, können Sie daran interessiert, die algorithmen, die ich für die solver/generator.

Zuerst schrieb ich den solver Teil würde ersten Satz alle Zellen als in der Lage zu sein, einen beliebigen Wert, dann gelten alle Regeln in der Reihenfolge, um zu sehen, wenn eine einzelne Zelle gelöst werden könnten oder anderweitig beschränkt sind, Dinge wie:

• wenn die Zelle einen bestimmten Wert in die Hinweise, setze Sie auf den Wert.
• ob es nur eine Zelle nach Links in eine Zeile (oder Spalte oder mini-Quadrat), können Sie stellen Sie den verbleibenden Wert.
• wenn eine Zelle markiert ist, als möglicherweise N und N existiert in der Zeile/Spalte/mini-Quadrat anderswo, entfernen Sie diese Möglichkeit.
• wenn es zwei Zellen in der Zeile/Spalte/mini-square, und Sie haben die gleichen zwei Möglichkeiten (und keine anderen Möglichkeiten), alle anderen Zellen in dieser Zeile/Spalte/mini-Quadrat haben sollte, die Möglichkeit entfernt werden.

Und so weiter, indem jede Regel, die ich in die Lösung der wirklichen Rätsel.

Für den generator, begann ich mit:

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

und dann in einer Schleife von unterschiedlicher Größe (mindestens 500), ging vertauschen von Zeilen und Spalten in einer solchen Weise, dass es würde nie produzieren eine ungültige puzzle. In anderen Worten, tauschen Sie Zeilen oder Spalten mit der Gruppe, in der Sie sich befinden (zum Beispiel Zeilen 1, 2 und 3 sind eine Gruppe, so sind die Spalten 4, 5 und 6).

Diese gemischt, bis die Zellen gut genug, um ein anständiges Rätsel.

Dann begann ich die Auswahl " zufällige Zellen und setzen Sie als unbekannte. Einmal in der Zelle war unbekannt festgelegt ist, würde ich pass das ganze Rätsel in den solver. Wenn es lösbar ist, würde ich fortfahren, sonst würde ich das Wiedereinsetzen der Zelle und tragen auf.

Dieser verhindert mir immer ein Rätsel, dass war logisch unlösbar.

Einmal eine große Anzahl von zufälligen Zelle Umzug geschehen war, würde ich versuchen zu entfernen Sie alle verbleibenden Zellen, um mit der gleichen Methode. Was übrig war, dann wurde die minimale Menge an Informationen notwendig, um das Rätsel zu lösen.

Und, also es war nicht ein Schmerz zu Sudoku-Anfänger, ich würde es Ihnen ermöglichen, geben Sie einen niedrigeren Schwierigkeitsgrad, mit denen eine bestimmte Anzahl von unnötigen Zellen zurück.

Nicht schlecht-Schema, es gibt vielleicht bessere, aber das funktionierte gut für mich.

Nun, wenn ich konnte nur herausfinden, das Kakuro Zeug, ich könnte glücklich sterben 🙂

Andere haben vernünftigerweise vorgeschlagen, einfach mit einem 2D-array.

Ich den Hinweis, dass ein 2D-array in den meisten Implementierungen von Programmiersprachen (etwas in die implementiert ist als "array of array of X" leidet, der zusätzliche Zugriffs-Zeit-overhead (Zugang zu den top-level-array, eine zweite für die subarray).

Schlage ich vor, implementieren Sie die Datenstruktur Abstrakt als ein 2D-array (vielleicht sogar weiterhin benutzen, 2 Indizes), aber implementieren Sie das array als einzigen block aus 81 Zellen, indiziert klassisch von i*9+j. Dies gibt Ihnen konzeptionelle Klarheit, und etwas mehr effizienten Umsetzung, durch die Vermeidung, dass der zweite Speicher zugreifen.

Sollten Sie in der Lage sich zu verstecken 1D-array hinter setter und Getter, die nehmen 2D-Indizes. Wenn Ihre Sprache hat die Fähigkeit (weiß nicht, ob dies wahr ist für Python), wie kleine Methoden werden inline für zusätzliche Geschwindigkeit.