Schlagwort-Archive: C++

Sudoku

In den Osterferien bin ich endlich dazu gekommen, mein kleines Sudoku-Lösungsprogramm zu schreiben, und es funktioniert schon in der jetzigen Version ausgezeichnet. Bisher tut es nichts weiter, als für jedes Kästchen im Sudoku eine Liste der noch möglichen Zahlen zu verwalten: jedes Mal, wenn eine neue Zahl irgendwo in ein Kästchen eingetragen wird, wird diese Zahl in allen Kästchen derselben Zeile, derselben Spalte und desselben Blocks aus der Liste entfernt. Das ist das Hauptprinzip.

Wie hilft mir diese einfache Listentabelle* die Lösungszahlen zu finden?

Naja: zum Einen kann ich alle Kästchen durchlaufen und mir ihre Listen anschauen. Wenn ich eine Liste finde, die nur noch eine Zahl enthält, dann ist in diesem Kästchen auch nur noch diese eine Zahl möglich, weil alle anderen Lösungen schon in andere Kästchen in Zeile, Spalte oder Block eingetragen worden sind. Diesen Treffer trage ich ins Kästchen ein (und aus den Listen drumherum aus), und dann kann ich schauen, ob ich noch weitere eindeutige Listen finde.
Was mache ich, wenn es irgendwann keine eindeutigen Treffer mehr gibt, weil sämtliche Listen mehrere mögliche Lösungszahlen enthalten? Dann kommt die zweite Methode ins Spiel: ich gehe alle Zeilen, Spalten und Blöcke durch und schaue, ob hier (in Zeile/Spalte/Block) eine Zahl in nur einer Liste vorkommt. Das entsprechende Kästchen ist dann die einzige Möglichkeit, diese Zahl in dieser Zeile ( oder Spalte oder Block) legal unterzubringen. Treffer eintragen, Trefferzahl aus Anliegerlisten streichen, weiterschauen.

Wie gesagt: das funktioniert ausgezeichnet. Bisher habe ich noch kein Sudoku gefunden, was ein Skript mit diesen beiden kleinen Funktionen nicht knacken konnte. Es funktioniert sogar so ausgezeichnet, dass ich hochgradig irritiert bin, weil ich beim Von-Hand-Lösen häufig noch einen weiteren Algorithmus verwenden muss, um Mehrdeutigkeiten aufzulösen. Bedeutet das, dass ich bisher beim Testen nur irgendwelche Popel-Sudokus gefunden habe und seither einfach keine richtig kniffligen mehr in der Zeitung stehen, oder bedeutet das, dass ich beim Von-Hand-Lösen dauernd Sachen übersehe und Flüchtigkeitsfehler mache?

Grmpf.
Ich gehe bis auf Weiteres erstmal davon aus, dass Sudokus seit den Osterferien einfacher geworden sind.
;-)

Advertisements

Darling, why don’t you just look at the std::map?

Ich hasse es, STL-Container debuggen zu müssen.

In Microsofts Visual Studio kann man sich ja im Debugger recht schön Element für Element den Inhalt einer std::map, eines std::sets oder eines std::vectors anzeigen lassen. Dummerweise kenne ich keine einfache Möglichkeit, sich die Speicherstelle anzeigen zu lassen, an der ein Element oder die size dieses Containers liegt, um auf diese Speicherstelle einen Breakpoint zu setzen, der mich alarmiert, wenn sich da was ändert.

Beispiel: ich habe eine std::map von Daten-Varianten, die ihrerseits eine std::map verschiedenen Ressourcen enthalten, die ihrerseits eine std::map von Kapazitätsobjekten dieser Ressourcen enhalten, die ihrerseits eine std::map von den eigentlichen Kapazitätswerten enthalten. Irgendwo, irgendwie, irgendwann gehen mir manche dieser std::maps mit Kapazitätswerten kaputt. Jetzt würde ich gerne herausfinden, an welcher Stelle im Programm das passiert, und dazu einen Daten-Haltepunkt auf der size dieser std::map anlegen. Das wäre schön praktisch: ich lasse das Programm laufen, und irgendwann, *blink*, meldet sich der Debugger, weil die Größe meiner std::map plötzlich bei drölfzig Milliarden liegt statt bei, sagen wir, 42.
Guter Plan.

Um sich den Speicherort ausgeben zu lassen, an dem man diesen Breakpoint setzen kann, muss man aber solche Verrenkungen unternehmen wie

&(m_pGanttViewCtrl->m_varMan
->m_variants._Myhead->_Left->_Myval.second
->m_pRessourcen->m_resMap._Myhead->_Right->_Myval.second
->m_pResKapazitaeten->m_capacities._Mysize)

womit der Debugger das erste Element der m_variants-map nimmt, dort dem Ressourcenpointer in seine m_resMap folgt, dort (in diesem Beispiel) das letzte Ressourcen-Element rausgreift, von dem er sich den Kapazitätenpointer und dessen m_capacities-map geben lässt, in der er dann _Mysize findet, wovon er sich schlussendlich die Speicherstelle ausgeben lässt.

Heute nacht habe ich mich in verschachtelten STL-Containern verlaufen, und alle waren knallbunt und riesengroß und enthielten jeweils noch ein ganzes Containerschiff voller Container, und die waren auch alle knallbunt und riesengroß und enthielten jeweils noch ein ganzes Containerschiff voller Container, und so weiter, und alle sollten sofort entladen werden, und ich musste doch noch was finden, aber ich wusste nicht mehr, was, und die Zeit drängte so und ich konnte es nicht finden, ich wusste ja nicht, wo es war, und dann — dann klingelte der Wecker.

Obfuscated C++

Manchmal kriege ich einen Knoten im Kopf, wenn ich mich durch fremden Code wühle. Preisfrage:

Wenn

int a = 17, b = 42;

wie sind dann nach

a ^= b ^= a ^= b;

die Werte für a und b?

Kann ja sein, dass solche Spielereien altbekannt sind; ich kannte sie noch nicht. Und übersichtlicher wird der Code dadurch auch nicht, oder?

Code-Kommentare

Dinge, die man in Programmcode eigentlich lieber nicht lesen möchte: Weiterlesen