[sudoku] minimalny diagram

0

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'):

  1. 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.
  2. 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

0

Myślę, że z sieciami neuronowymi nie ma to wiele, a nawet nic wspólnego :P... ale zawsze mozna odejmowac po cyferce i sprawdzać czy da sie rozwiązać...Trochę by to trwało, ale jeśli nie ma innego wyjścia termin zlecani pojutrze... ;)

0
Xeo napisał(a)

z sieciami neuronowymi nie ma to wiele, a nawet nic wspólnego
Myślę, że jednak trochę ma: sieci neuronowe mają to do siebie, że potrafią odtworzyć informację, nawet jeśli jest zniekształcona. Diagram złożony z cyfr i pozbawiony kilku jest informacją zniekształconą- ale to luźne skojarzenia i nie jest sednem mojego pytania :|

ale zawsze mozna odejmowac po cyferce i sprawdzać czy da sie rozwiązać...
W taki sposób to nawet problem komiwojażera można rozwiązać, a nie o to mi chodziło. Przy Twoim sposobie algorytm miałby złożoność chyba wykładniczą. A mi chodziło o sposób inny niż sprawdzenie wszystkich możliwości.
No i pozostaje jeszcze pytanie nr 1.

0

Heh, chyba nie dostrzegles ironii...;)

//i sry za offtop :)

0
id02009 napisał(a)

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

RTFW :-P

The maximum number of givens provided while still not rendering the solution unique is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy form the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be assigned. Since this applies to Latin squares in general, most variants of Sudoku have the same maximum. The inverse problem—the fewest givens that render a solution unique—is unsolved, although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts,[25] [26] and 18 with the givens in rotationally symmetric cells.

za http://en.wikipedia.org/wiki/Sudoku

<font size="1">--
ps. dzięki adminom za forum na którym nie trzeba się rejestrować
</span>

1 użytkowników online, w tym zalogowanych: 0, gości: 1