Witam, ostatnio wolne chwile umilam sobie rozwiązywaniem diagramów sudoku i wymyśliłem taki problem:
Mamy dany Rozwiązany diagram sudoku (wszystkie pola są wypełnione).
Pytanie: ile maksymalnie ( i jakie) cyfr z diagramu możemy usunąc, aby diagram wciąż był możliwy do rozwiązania jedynie za pomocą logicznego wnioskowania (bez zgadywania żadnego kroku).
Możliwe, że gdzieś, ktoś już się nad tym zastanawiał, ale nie wiem nawet jak ten problem mógłby się nazywać, więc nawet nie szukałem ;) Jeśli ktoś się z tym spotkał to byłbym wdzięczny za info.
No i pytania, które się od razu nasuwają (cały czas biorę pod uwagę tylko diagramy, które można rozwiązać bez ani jednego 'strzału'):
- Załóżmy, że najmniejszy (czyli taki z najmniejszą il. cyfr na początku), isntiejący diagram ma x cyfr. Czy każdy diagram można 'zredukować' tak, aby miał x cyfr? Czy może ten 'poziom redukcji' jest specyficzny dla każdego diagramu.
- Czy istnieje algorytm, który znajdzie ten 'maksymalny poziom redukcji' inaczej niż sprawdzając wszystkie możliwości? Intuicja podpowiada, że to może być problem NP-zupełny :>
Do tych przemyśleń skłoniła mnie dość ciekawa właściwość diagramów: po usunięciu znacznej ilości informacji jesteśmy ją w stanie odtworzyć. Problem bliski moim zdaniem kompresji, a nawet podobny do sieci neuronowcyh (odtwarzanie niepełnych, zniekształconych informacji).
Pozdrawiam