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

9

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?CC

Kevin
źródło

Odpowiedzi:

2

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,,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

Janoma
źródło
1

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

tomoka kazuki
źródło
Interesuje mnie, czy 41 jest sprawdzoną górną granicą (jako ). N2
rus9384
Nie widziałem tego w żadnym artykule. Co ciekawe, prawie wszystkie prace nad znalezieniem Sudokusa o minimalnej „h” wysokiej jakości wydają się być prowadzone przez poszukiwanie znanego Sudokusa i modyfikowanie go w celu iteracyjnego zwiększania „h”. Prace nad znalezieniem minimalnych 40 zagadek doprowadziły do ​​stworzenia bazy danych zawierającej ponad 6 500 000 000 innych minimalnych zagadek o wysokiej wskazówce. Poza trywialnymi problemami, nie widziałem prawie żadnego rygorystycznego dochodzenia jakimkolwiek sposobem innym niż „przeszukiwanie”. Ale twoja propozycja jest interesująca.
tomoka kazuki
Czy mógłbyś tutaj dodać cytaty? Lub przynajmniej link do odpowiedniej strony w Wikipedii.
David Richerby
Ta informacja pochodzi z artykułu Wikipedii „Matematyka Sudoku” „Maksymalna liczba dawców”. Cytowane odniesienie (do odkrycia Sudoku z 1. 40 wskazówek minimalnych) to: forum.enjoysudoku.com/high-clue-tamagotchis-t30020-135.html Kluczowe informacje to arkusz 10, ale powiązane informacje znajdują się zarówno przed, jak i po arkuszu 10.
tomoka kazuki
0

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.wprowadź opis zdjęcia tutaj

Nicomal
źródło
To dobra uwaga, ale myślę, że nie jest to zadawane pytanie, które dotyczy minimalnej liczby wskazówek pozwalających określić zagadkę, jeśli strategicznie wybierzesz wskazówki
6005
Myślę, że to dobra odpowiedź, ale fajnie byłoby dodać do tej odpowiedzi (1) notatkę, dlaczego jest ona nieco inna niż zadane pytanie, (2) przekonwertować zamazany obraz na tabelę w tekście i / lub wyjaśnienie
6005