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.