Mindestanzahl von Hinweisen, um ein Sudoku vollständig zu spezifizieren?

9

Wir wissen aus diesem Artikel, dass es kein Rätsel gibt, das mit 16 oder weniger Hinweisen gelöst werden kann, aber es impliziert, dass es ein Rätsel gibt, das aus 17 Hinweisen gelöst werden kann. Können alle gültigen Sudoku-Rätsel in 17 Hinweisen angegeben werden? Wenn nicht, wie viele Hinweise können mindestens jedes gültige Puzzle vollständig spezifizieren? Gibt es formal ein gültiges Sudoku-Puzzle (oder, ich denke, es wäre eine Reihe von Puzzles), das nicht mit nur 17 Hinweisen eindeutig gelöst werden kann? Wenn ja, was ist dann die minimale Anzahl von Hinweisen, , so dass jedes gültiges Sudoku - Rätsel eindeutig in angegeben werden C oder weniger Hinweisen?C.C.

Kevin
quelle

Antworten:

2

Da das Permutieren von zwei Zeilen innerhalb eines einzelnen Blocks eines gültigen, abgeschlossenen Sudoku ein weiteres gültiges, abgeschlossenes Sudoku erzeugt, können Sie jede abgeschlossene Tafel (81 Hinweise) nehmen und die ersten beiden Zeilen (81-18 = 63 Hinweise) entfernen, die Ihnen geben ein unvollständiges Sudoku mit zwei Lösungen. Beachten Sie, dass die Lösung sofort eindeutig bestimmt wird, selbst wenn Sie alle bis auf eine der 18 Zahlen dort entfernen (da in derselben Spalte keine Zahl wiederholt werden kann).

Eine andere Operation, die ein weiteres abgeschlossenes Sudoku erzeugt, ist das Anwenden einer Permutation von . Wenn Sie eine Permutation nehmen, die eine Transposition ist (permutiert zwei Elemente, wobei das andere fest bleibt), können Sie wie zuvor alle Erscheinungen dieser beiden Elemente entfernen und haben ein unvollständiges Sudoku mit zwei möglichen Lösungen und 63 Hinweisen. Wenn Sie nicht alle 18 Zahlen entfernen, ist die Lösung eindeutig.{1,,9}}

Von den sechs Elementoperationen, die ein fertiges Sudoku erzeugen (siehe hier ), können diese beiden die geringste Anzahl von Elementen umfassen. Ich würde also sagen, dass eine Obergrenze für das ist, wonach Sie suchen. Ich weiß, dass dies Ihre Frage nicht genau beantwortet, aber die allgemeine Idee, Positionssätze zu entfernen, die zwei verschiedene Lösungen ergeben, könnte ein guter Ausgangspunkt sein.C.=63

Janoma
quelle
1

Die wenigsten Hinweise, die für ein richtiges Sudoku erforderlich sind, sind 17, aber nicht alle abgeschlossenen Gitter können auf ein richtiges Sudoku mit 17 Hinweisen reduziert werden. Es wurden ungefähr 49.000 einzigartige (nicht äquivalente) Sudokus mit 17 Hinweisen gefunden. (Ein richtiger Sudoku hat nur eine Lösung).

Es wird angenommen, dass die meisten Hinweise in einem minimalen Sudoku 40 sind (zwei sind bekannt), aber es wurde nicht bewiesen, ob dies das Maximum ist. (Minimal bedeutet, dass das Sudoku mehr als eine Lösung hat, wenn ein Hinweis entfernt wird, und daher kein richtiges Sudoku ist.)

(Diese Informationen stammen aus Wikipedia, auf die in diesen Aussagen gut verwiesen wird).

Tomoka Kazuki
quelle
N.2
Ich habe das in keinem Papier bewiesen gesehen. Interessanterweise scheinen fast alle Arbeiten zur Suche nach "h" -minimalem Sudokus mit hohem Hinweis durch eine Suche nach bekannten Sudokus und deren Modifikation durchgeführt zu werden, um "h" iterativ zu erhöhen. Die Arbeit, die minimalen 40 Hinweisrätsel zu finden, ergab eine Datenbank mit mehr als 6.500.000.000 anderen minimalen Hochrätselrätseln. Abgesehen von trivialen Problemen habe ich fast keine strengen Untersuchungen mit anderen Mitteln als "Suchen" gesehen. Aber Ihr Vorschlag ist interessant.
Tomoka Kazuki
Könnten Sie bitte die Zitate hier hinzufügen? Oder zumindest einen Link zur entsprechenden Wikipedia-Seite.
David Richerby
Diese Informationen stammen aus dem Wikipedia-Artikel "Mathematik des Sudoku" im Abschnitt "Maximale Anzahl von Gegebenheiten". Die zitierte Referenz (für die Entdeckung des ersten 40-Hinweis- Minimums von Sudoku) lautet: forum.enjoysudoku.com/high-clue-tamagotchis-t30020-135.html Wichtige Informationen sind Blatt 10, verwandte Informationen sind jedoch sowohl vor als auch nach Blatt 10.
Tomoka Kazuki
0

Dieses Sudoku hat 77 Hinweise und dennoch mehrere Lösungen (2). Sie können 7-4 in der oberen Reihe und 4-7 in der anderen oder 4-7 in der oberen und 7-4 in der unteren Reihe verwenden. Dieses spezielle Sudoku-Puzzle benötigt 78 Hinweise, um eine einzigartige Lösung zu erhalten.Geben Sie hier die Bildbeschreibung ein

Nicomal
quelle
Dies ist ein guter Punkt, aber ich denke, es ist nicht genau die Frage, die gestellt wird. Es geht um eine minimale Anzahl von Hinweisen, um das Rätsel zu spezifizieren, wenn Sie die Hinweise strategisch auswählen können
6005
Ich denke, es ist eine gute Antwort, aber es wäre schön, dieser Antwort (1) einen Hinweis hinzuzufügen, warum dies etwas anders ist als die gestellte Frage, (2) das unscharfe Bild in eine Tabelle in Text und / oder eine Erklärung umzuwandeln
6005