Libraries

Inhaltsverzeichnis

Bibliothek für Regression-Tests

Testen auf Regressionen ist immer schwierig und aufwendig, wenn die Tests nicht vollständig automatisiert werden können. Ein Problem beim Testen vieler verschiedener Techniken besteht darin, eine große Auswahl an Testfällen zu finden, die automatisch behandelt werden können.

In der Vergangenheit wurde einiges an Arbeit investiert um Bibliotheken von Testfällen (bzw. Bibliotheken von Sudokus, die als Testfälle verwendet werden können) zusammenzustellen, z.B. Ruuds Benchmark Sudoku List, Mike Barkers zoo, RWs The Effortless Extremes thread oder tareks A Pure Jellyfish Collection (und diese Liste ist natürlich unvollständig).

Die meisten dieser Zusammenstellungen kann jedoch nicht für automatisierte Tests verwendet werden, weil sie von der verwendeten Solver-Strategie abhängen oder in verschiedenen Formaten vorliegen. Ich habe daher eine eigene Sammlung von Testfällen zusammengestellt und ein Format entwickelt, das einfaches Testen ermöglicht. Die meisten Testfälle wurden mit HoDoKu erzeugt, aber viele sind auch aus Foren und Sammlungen aus dem Internet. Aufgrund der großen Anzahl an Testfällen (mehr als 1000 in Version 1.0 der Bibliothek) wurden bei den einzelnen Sudokus keine Referenzen angegeben.

Der Zweck dieser Bibliothek ist es, so viele Testfälle wie möglich für so viele verschiedene Lösungstechniken wie möglich zu sammeln. Jeder Test belegt genau eine Zeile und testet eine bestimmte Technik für eine bestimmte Menge an Kandidaten. Die einzige Anforderung an einen gültigen Testfall besteht darin, dass es keine andere Instanz der getesteten Technik für die angegebenen Kandidaten gibt, die zu einer anderen Platzierung oder zu anderen Eliminierungen führt.

Das Bibliotheksformat hat den zusätzlichen Vorteil, dass es ein komplettes PM-Grid enthält und den Unterschied zwischen Angabe und vom Anwender gesetzten Zellen bewahrt (und dabei trotzdem nur eine Zeile benötigt).

Ein besonderer Dank gilt dem MaNik-e Team für ihre Hilfe beim Kodieren der eigentlichen Testroutine.

HoDoKu Bibliotheksformat

Ein Test besteht aus einer Zeile mit sieben Feldern, die mit ":" getrennt werden. Format:

:<Technik>:<Kandidat(en)>:<Angabe>:<gelöschte Kandidaten>:<Eliminierungen>:<gesetzte Zellen>:<Extra>

<Technik>
Eine alphanumerische Zeichenkette, die die Technik bestimmt (für Werte siehe die Bibliotheksdatei). Für einige Techniken existieren Varianten. Eine Variante beginnt mit einem Trennstrich nach dem Code für die Technik, gefolgt von einer Nummer. Varianten können natürlich bei Bedarf ignoriert werden. Besteht die Variante aus einem einfachen 'x', ist der Test ein Fail-Case: Es darf keine Instanz der Technik gefunden werden.
<Kandidat(en)>
Der Kandidat (die Kandidaten), für den die Technik angewendet wird (siehe unten)
<Angabe>
Die gesetzten Zellen des Sudokus; ein '+' vor einer Ziffer bedeutet, dass der Wert nicht zur Angabe gehört, sondern dass die Zelle vom Anwender gesetzt wurde (optional)
<gelöschte Kandidaten>
Kandidaten, die gelöscht werden müssen, nachdem die Zellen der Angabe gesetzt wurden. <givens> und <deleted candidates> gemeinsam entsprechen einem PM-Grid, allerdings mit dem Vorteil, dass der Unterschied zwischen Angabe und vom Anwender gesetzten Zellen erhalten bleiben kann (Format siehe unten)
<Eliminierungen>
Kandidaten, die von der <Technik> im PM-Grid eliminiert werden können, falls vorhanden (Format siehe unten)
<gesetzte Zellen>
Zellen, die von der <Technik> im PM-Grid gesetzt werden können, falls vorhanden (Format siehe unten)
<Extra>
Kann zusätzliche Informationen für einzelne Techniken enthalten. Derzeit sind folgende Werte definiert:
  • Chains/Loops: Die Länge der chain/loop in Anzahl Inferences

Format für Kandidaten/Eliminierungen/gesetzte Zellen

<Kandidat><Zeile><Spalte>

<Zeile> und <Spalte> gehen von 1 bis 9; enthält ein Eintrag mehrere Instanzen, werden sie mit Leerzeichen getrennt.

Beispiel: ":436 257:" bedeutet "r3c6<>4, r5c7<>2"

<Eliminierungen> und <gesetzte Zellen> können nicht gleichzeitig vorkommen.

Der Inhalt von <Kandidaten> hängt von der Technik ab:

Beispiel 1:

:0003:8:6...+53+4.7....4+2+56.+254867+3+9+1.+4..+9+6.1.162+38+5749.3..+1+4.+5....42193..1.+57...+44+2.6+3.+1+75:::829:

Bedeutung:

Erzeuge ein Sudoku aus der Zeichenkette

"6....3..7....4..6..54867..........1.162.8.749.3..........42193..1..7....4..6....5"

(alles von <Angabe>, das kein '+' davor stehen hat - die 'echte' Angabe). Nun platziere die Zellen, die durch den folgenden String gegeben sind:

"....5.4.......25..2.....391.4..96......3.5.......14.5.............5....4.2..3.17."

(alles von <Angabe> mit einem '+' davor); man kann auch alle '+' ignorieren und den folgenden String setzen:

"6...534.7....4256.254867391.4..96.1.162385749.3..14.5....42193..1.57...442.63.175"

es gibt keine Kandidaten, die gelöscht werden müssen;

suche ein Naked Single für Kandidat 8 im durch <Angabe> und <gelöschte Kandidaten> bestimmten PM-Grid; es sollte eins gefunden werden, das 8 in r2c9 setzt.

Beispiel 2 (die Zeichenkette muss auf einer Zeile stehen)

:0603:3:14+8..+9+72+5.+3...89.697+6....38.+61......3+2.8.56...9......2.5+9+186....+8+3....61+6+1...35+89:224 524 225 525 135 455 755 458 758 165 168 771 284 484 784 285 485 785:364 365::

Bedeutung:

Setze alle Zellen von <Angabe> wie oben beschrieben; danach eliminiere:
r2c4<>25, r2c5 <>25, r3c5<>1, r5c5<>47, r5c8<>47, r6c5<>1, r6c8<>1, r7c1<>7, r4c8<>247, r5c8<>247;

suche ein Uniqueness Test Type 4 im PM, das Kandidaten für Ziffer 3 eliminieren kann; es sollte eines existieren, das 3 aus r6c4 und r6c5 entfernt.

Die komplette Bibliothek:

reglib-1.3.txt

Exemplar-Bibliothek

HoDoKus Exemplar-Bibliothek ist eine lose Sammlung von Sudokus, die bestimmte Techniken verdeutlichen. Die meisten dieser Sudokus wurden mit HoDoKus Batch-Erzeugungs-Modus (siehe Sudokus im Batchbetrieb erzeugen im Benutzer-Handbuch) gefunden.

Einige Beispiel funktionieren nur, wenn Solver-Optionen oder die Solver-Hierarchie geändert werden, einige wenige Beispiele sind überhaupt falsch.

Die Bibliothek:

exemplars-1.0.txt

Copyright © 2008-12 by Bernhard Hobiger
Alles Material auf dieser Site unterliegt der GNU FDLv1.3.