Minimalna liczba wskazówek, aby w pełni określić jakieś sudoku?

Wiemy z tego artykułu , że nie istnieje układanka, którą można rozwiązać, zaczynając od 16 lub mniej wskazówek, ale sugeruje, że istnieje układanka, którą można rozwiązać na podstawie 17 wskazówek. Czy wszystkie prawidłowe łamigłówki sudoku można podać w 17 wskazówkach? Jeśli nie, jaka jest minimalna liczba wskazówek, które mogą całkowicie określić każdą prawidłową łamigłówkę? Mówiąc bardziej formalnie, czy istnieje ważna łamigłówka sudoku (lub, jak sądzę, byłaby to seria puzzli), której nie da się jednoznacznie rozwiązać tylko z 17 wskazówek? Jeśli tak, to jaka jest minimalna liczba wskazówek, , tak że każda ważna łamigłówka sudoku może być jednoznacznie określona w C lub mniejszej ilości wskazówek?$C$$C$

Ponieważ permutowanie dwóch wierszy w jednym bloku prawidłowego, ukończonego sudoku powoduje powstanie kolejnego ważnego, ukończonego sudoku, możesz wziąć dowolną ukończoną planszę (81 wskazówek) i usunąć pierwsze dwa rzędy (81-18 = 63 wskazówek), co da ci niepełne sudoku z dwoma rozwiązaniami. Zauważ, że nawet jeśli usuniesz wszystkie oprócz jednej z 18 liczb, rozwiązanie zostanie natychmiast określone w sposób jednoznaczny (ponieważ w tej samej kolumnie nie może się powtarzać żadna liczba).

Inną operacją, która powoduje kolejne ukończone sudoku, jest zastosowanie permutacji . Jeśli weźmiesz permutację, która jest transpozycją (przenosi dwa elementy, utrzymując drugi na stałym poziomie), ponownie, tak jak poprzednio, możesz usunąć wszystkie wyglądy tych dwóch elementów i masz niepełne sudoku z dwoma możliwymi rozwiązaniami i 63 wskazówkami. Ponownie, jeśli nie usuniesz wszystkich 18 liczb, rozwiązanie będzie unikalne.$\{1,\ldots,9\}$

Z sześciu operacji elementarnych, które tworzą ukończone sudoku (patrz tutaj ), te dwie mogą obejmować najmniejszą liczbę elementów, więc powiedziałbym, że jest górną granicą tego, czego szukasz. Wiem, że to nie odpowiada dokładnie na twoje pytanie, ale ogólny pomysł na usunięcie zbiorów pozycji, które dają dwa różne rozwiązania, może być dobrym punktem wyjścia.$C=63$

Do Najmniej wskazówki niezbędne dla prawidłowego Sudoku jest 17, ale nie wszyscy ukończyli ruszty można zredukować do odpowiedniego 17 clue Sudoku. Znaleziono około 49 000 unikalnych (nieekwiwalentnych) Sudokusów z 17 wskazówkami. (Właściwe Sudoku ma tylko jedno rozwiązanie).

Uważa się, że najwięcej wskazówek w minimalnym Sudoku to 40 (wiadomo, że istnieją dwa), ale nie udowodniono, czy jest to maksimum. (minimalna oznacza, że ​​jeśli jakakolwiek wskazówka zostanie usunięta, Sudoku będzie miało więcej niż jedno rozwiązanie, a zatem nie będzie właściwym Sudoku)

(Ta informacja pochodzi z Wikipedii, do której te odniesienia są dobrze przywołane).

To Sudoku ma 77 wskazówek, a jednak ma wiele rozwiązań (2). Możesz użyć 7-4 w górnym rzędzie i 4-7 w drugim lub używając 4-7 na górze i 7-4 na dole. Ta konkretna łamigłówka Sudoku potrzebuje 78 wskazówek, aby mieć unikalne rozwiązanie.