info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Lineare Abhängigkeit?
47 views
Skip to first unread message
Christian Gollwitzer
Dec 14, 2017, 1:32:43 AM12/14/17
to
Am 13.12.17 um 23:20 schrieb Hans-Peter Diettrich:
> Dabei stellt sich mir die Frage,
> wie solche Teilmengen möglichst effizient bestimmt werden können. Im
> ersten Durchgang könnte man alle leeren Mengen entfernen, und die
> ein-elementigen sind fertige Lösungen. Für weitere Lösungen müssen
> mehrere Mengen kombiniert (vereinigt) werden - nach welcher Strategie?
> Effizienz bedeutet hier doch, die Anzahl bzw. Größe der zu
> untersuchenden Teilmengen einzuschränken, so daß der volle Aufwand (n!?)
> nur notwendig wird, wenn sonst keine Lösung gefunden wird.
Falls Deine eigentlich Frage immer noch ist "wie löst man Sudoku?"
(sorry, bin jetzt zu denkfaul um zu überprüfen, ob das was Du hier
schreibst, äquivalent ist) - dann guck doch einfach, wie Andere das machen.
Alle Sudokus, die Du in Zeitschriften und Rätselheften findest, können
ohne Backtracking durch iteratives Anwenden der "Singles"- und "Hidden
Singles"-Regeln gelöst werden. Einfach deshalb, weil Backtracking für
Menschen keinen Spaß bedeutet.
Hier ist z.B. mein Sudoku-Solver: http://auriocus.de/Sudoku/
Start mit "wish sudoku2.tcl", das File "sneu.board" mit dem Rätsel wird
eingelesen. Durch mehrfaches drücken auf "Weiter" und "Durchmarsch"
kannst Du normalerweise auch die "schwierigen" Rätsel aus den
Zeitschriften komplett lösen. Das Einzige, was er dabei macht, ist eine
Zelle zu suchen, auf die die Singles- oder Hidden-Singles-Regel zutrifft
und die dann zu füllen.
Im Allgemeinen geht es aber nicht so, und insbesondere nicht für
"minimal Sudoku": es gibt eindeutig lösbare Sudokus, für die man nicht
mit den zwei simplen Strategien auskommt. Auf Wikipedia steht dazu auch
schon eine Menge. https://en.wikipedia.org/wiki/Sudoku_solving_algorithms
Christian
> Dabei stellt sich mir die Frage,
> wie solche Teilmengen möglichst effizient bestimmt werden können. Im
> ersten Durchgang könnte man alle leeren Mengen entfernen, und die
> ein-elementigen sind fertige Lösungen. Für weitere Lösungen müssen
> mehrere Mengen kombiniert (vereinigt) werden - nach welcher Strategie?
> Effizienz bedeutet hier doch, die Anzahl bzw. Größe der zu
> untersuchenden Teilmengen einzuschränken, so daß der volle Aufwand (n!?)
> nur notwendig wird, wenn sonst keine Lösung gefunden wird.
Falls Deine eigentlich Frage immer noch ist "wie löst man Sudoku?"
(sorry, bin jetzt zu denkfaul um zu überprüfen, ob das was Du hier
schreibst, äquivalent ist) - dann guck doch einfach, wie Andere das machen.
Alle Sudokus, die Du in Zeitschriften und Rätselheften findest, können
ohne Backtracking durch iteratives Anwenden der "Singles"- und "Hidden
Singles"-Regeln gelöst werden. Einfach deshalb, weil Backtracking für
Menschen keinen Spaß bedeutet.
Hier ist z.B. mein Sudoku-Solver: http://auriocus.de/Sudoku/
Start mit "wish sudoku2.tcl", das File "sneu.board" mit dem Rätsel wird
eingelesen. Durch mehrfaches drücken auf "Weiter" und "Durchmarsch"
kannst Du normalerweise auch die "schwierigen" Rätsel aus den
Zeitschriften komplett lösen. Das Einzige, was er dabei macht, ist eine
Zelle zu suchen, auf die die Singles- oder Hidden-Singles-Regel zutrifft
und die dann zu füllen.
Im Allgemeinen geht es aber nicht so, und insbesondere nicht für
"minimal Sudoku": es gibt eindeutig lösbare Sudokus, für die man nicht
mit den zwei simplen Strategien auskommt. Auf Wikipedia steht dazu auch
schon eine Menge. https://en.wikipedia.org/wiki/Sudoku_solving_algorithms
Christian
Andreas Leitgeb
Dec 17, 2017, 12:21:31 PM12/17/17
to
Christian Gollwitzer <auri...@gmx.de> wrote:
> ...
I guess that was meant for de.sci.mathematik, not for comp.lang.tcl
> ...
I guess that was meant for de.sci.mathematik, not for comp.lang.tcl
0 new messages