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

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$

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,\ldots,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$

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).

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.