Jaka jest minimalna liczba wskazówek, jakie może mieć Sudoku?
Ostatnia aktualizacja
Poprawne Sudoku - takie, które ma dokładnie jedno rozwiązanie - wymaga co najmniej 17 podanych cyfr. Jest to udowodniony matematycznie wynik. Każda łamigłówka z 16 lub mniejszą liczbą wskazówek ma wiele rozwiązań lub nie ma ich wcale.
Dowód z 2012 roku
W 2012 roku Gary McGuire, Bastian Tugemann i Gilles Civario z University College Dublin opublikowali dowód, że nie istnieje żadne ważne Sudoku z 16 wskazówkami. Ich praca była głównie obliczeniowa: przeszukali całą przestrzeń możliwych siatek z 16 wskazówkami i zweryfikowali, że żadna nie daje unikalnego rozwiązania. Wyszukiwanie wymagało około 7 milionów godzin rdzeniowych obliczeń.
Wcześniej powszechnie uważano, że minimum wynosi 17 i znaleziono eksperymentalnie tysiące łamigłówek z 17 wskazówkami. Zespół McGuire'a dostarczył pierwszy rygorystyczny dowód, że 16 jest niemożliwe.
Jak wyglądają łamigłówki z 17 Clue
Łamigłówki z 17 wskazówkami są niezwykle rzadkie - 17 podanych cyfr w 81 komórkach, pozostawiając 64 puste. Należą do najtrudniejszych łamigłówek do rozwiązania i zazwyczaj wymagają zaawansowanych technik. Znalezienie prawidłowych łamigłówek z 17 wskazówkami samo w sobie wymagało dziesięcioleci obliczeniowego wysiłku. W chwili pisania tego tekstu znanych jest ponad 49 000 zasadniczo różnych łamigłówek Sudoku z 17 wskazówkami.
Co to oznacza dla projektowania łamigłówek
Opublikowane łamigłówki przeznaczone dla ludzkich rozwiązujących rzadko schodzą poniżej 22 wskazówek. Ekspert i poziom Mistrzowski zazwyczaj używają 22-27 podanych cyfr, podczas gdy Łatwe używają 36-45. Minimum 17 wskazówek to teoretyczna granica - W praktyce rozwiązywalność przy dobrej technice i przyjemna ścieżka rozwiązywania mają znacznie większe znaczenie niż sama liczba wskazówek.