Benutzer:Peter Buch/Sudoku und Exact cover
aus Wikipedia, der freien Enzyklopädie
Die Weise, wie im Artikel ein Sudoku als Exact-cover-Problem beschrieben wird, halte ich für unüblich. Die üblichere Darstellung könnte – in möglichst allgemeinverständlicher Formulierung – so aussehen:
Die Sudoku-Regeln besagen, dass ein korrekt ausgefülltes Sudoku folgenden Bedingungen entspricht: * In jedem Feld steht genau eine Ziffer (Feld-Bedingungen). * Jede Kombination einer bestimmten Ziffer mit einer bestimmten Zeile kommt genau einmal vor (Ziffer-Zeile-Bedingungen). * Jede Kombination einer bestimmten Ziffer mit einer bestimmten Spalte kommt genau einmal vor (Ziffer-Spalte-Bedingungen). * Jede Kombination einer bestimmten Ziffer mit einem bestimmten Block kommt genau einmal vor (Ziffer-Block-Bedingungen). Die erste Bedingung wird wegen ihrer vermeintlichen Trivialität oft nicht explizit genannt. Im Einzelnen hat man 81 Feld-Bedingungen, 81 Ziffer-Zeile-Bedingungen, 81 Ziffer-Spalte-Bedingungen und 81 Ziffer-Block-Bedingungen. Jede dieser 324 Bedingungen muss exakt einmal erfüllt sein. Erfüllt werden diese Bedingungen durch Eintragungen von Ziffern in die Felder, also durch Ziffer-Feld-Kombinationen. Eine bestimmte Ziffer-Feld-Kombination deckt 4 Bedingungen ab: * die Feld-Bedingung ihres Feldes, * die Ziffer-Zeile-Bedingung ihrer Ziffer mit der Zeile, in der ihr Feld liegt, * die Ziffer-Spalte-Bedingung ihrer Ziffer mit der Spalte, in der ihr Feld liegt, * und die Ziffer-Block-Bedingung ihrer Ziffer mit dem Block, in dem ihr Feld liegt. Es gibt 729 Ziffer-Feld-Kombinationen (81 Felder à 9 Ziffern). Das sind die Kandidaten, von denen im vollständig ausgefüllten Sudoku 81 ausgewählt sind, so dass sie zusammengenommen sämtliche 324 Bedingungen erfüllen, aber jede Bedingung nur einmal. Die Feld-Bedingungen sorgen dafür, dass für ein Feld nicht mehrere Ziffern gewählt sind. In einem zu lösenden Sudoku sind einige Kandidaten vorgegeben, die auf 81 fehlenden sind zu finden. Damit stellt ein Sudoku ein Problem der exakten Überdeckung ("Exact cover") dar. Algorithmen zur Lösung von Exact-cover-Problemen können als Sudoku-Löser verwendet werden, wenn man die Sudoku-Struktur vorgibt: die Menge der Bedingungen, die Menge der Kandidaten und die Verknüpfung dazwischen, also welche Kandidaten welche Bedingungen abdecken. Die in einem konkreten Rätsel vorgegebenen Ziffern reduzieren dabei die zur Verfügung stehenden Kandidaten und die noch abzudeckenden Bedingungen.
Das sollte IMHO schon eine ausreichende Behandlung von Exact cover in Sudoku sein. Für weitere Infos kann man dem Link dorthin folgen.
