Domains schnell und einfach registrieren.

 Registrieren || Einloggen || Hilfe/FAQ || Suche || Memberlist || Home || Statistik || Kalender || Staff Willkommen Gast!

 Sudoku Forum » Sudoku-Programme » backtracking fuer Puenktchen Sudoku » Threadansicht

Autor Thread - Seiten: -1-
000
27.09.2008, 20:24 Uhr
surbier



Hallo,

Ich habe mal eine ganz andere Frage.

Ich habe ein Sudoku Programm gebastelt, das
mittels backtracking die Loesung sucht;
und zwar alle Loesungen, falls es mehr als eine gibt.
Bei klassischen Sudokus komme ich auf eine
Bearbeitungszeit zwischen 0.001 sec und 2 sec, je nachdem
wieviele Zahlen bereits im Ausganssudoku stehen und
wie die Zahlen im Feld verteilt sind.

Das ist eigentlich nichts Neues, das Programm
kann aber noch mehr:

Die Loesungszeiten von Diagonalsudokus sind ebenfalls in diesem Bereich.
Ebenso kann das Programm auch die Loesung von irregulaeren Sudokus
und Farben-Sudokus finden. Da liegen die Zeiten um die 3 Minuten.

Weiterhin kann das Programm auch einige Varianten der Gruppe
der Puenktchen Sudoku verarbeiten wie Kropki, Nachbar Sudoku
(engl. consecutive) und Distanz Sudoku (eng. non-consecutive)
und Vergleichs Sudoku.

Bei den schwersten Kropki, braucht das Programm allerdings Tage.
Da bin ich ja fast schneller mit Papier und Bleistift.
Ich vermute, das haengt zum einen daran, dass die exrem schweren
Kropki keine Zahlen mehr im Ausgangs Sudoku haben, sondern nur
weisse und schwarze Kreise.
Der Suchbaum wird damit wirklich 81 Verschachtelungen tief.
Zum anderen fraegt das Programm fuer einen Kandidaten ja nicht
nur wie fuer klassische Sudokus die Linien-, Zeilen- und
Blockbedingung ab, sondern testet auch, ob es einen weissen oder
schwarzen Kreis zu einem der vier Nachbarfelder gibt.

Fuer einen guten Hinweis waere ich dankbar.

surbier

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
001
16.10.2008, 15:28 Uhr
surbier



Das Problem ist geloest:
Anstatt die leeren Felder so abzutasten:

Quellcode:
for (i=1; i<=9; i++)
    for (j=1; j<=9; j++)
        if (A[i][j]==0)
           {
           ...

verwaltet das Programm eine Liste der leeren Felder L[k], die
abgetasted wird. Die Liste der leeren Felder ist nach strategischen Gesichtpunkte sortiert, z.B. nach der Anzahl der Kandidaten im leeren Feld, oder die Anzahl der Zahlen im Ausgangssudoku, die das leere Feld 'sehen'. Speziell fuer Puenktchensudoku wird auch nach der Anzahl der am leeren Feld anliegenden Puenktchen sortiert. Damit laueft das benchmark Puenktchensudoku unter 2 Minuten, anstatt Tage.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
Seiten: -1-     [ Sudoku-Programme ]  


Kontakt | Impressum | powered by ThWboard 3 Beta 2.84-php5 © by Paul Baecher & Felix Gonschorek