Widzę cię, skarbie

24 listopada 2008
Marek Penszko

W roku 2000 poczciwy saper został „wplątany” w matematykę wyższą, a ściślej w teorię algorytmów. Angielski matematyk Richard Kaye opublikował na łamach kwartalnika Mathematical Intelligencer artykuł „Saper jest NP-zupełny”. Właściwie nic szczególnego, bo publikacji naukowych dowodzących przynależności jakiejś gry lub łamigłówki do określonej klasy problemów matematycznych powstaje niemało. W tym przypadku chodziło jednak o grę powszechnie znaną i popularną, a ponadto natychmiast zwrócono uwagę na związek tego tematu z zagadnieniem P-NP – jednym z siedmiu, za rozwiązanie których hojni Amerykanie z Instytutu Claya ufundowali w tym samym roku (nie przeczuwając kryzysu:)) po milionie dolarów. Później w paru popularnych artykułach padły nawet ryzykowne stwierdzenia, że korzystając z sapera łebski matematyk amator może zgarnąć fortunę.

Mówiąc w skrócie, problem obliczeniowy jest klasy P, jeśli potrafimy go rozwiązać za pomocą komputera. Jeśli natomiast nie umiemy tego zrobić (co nie znaczy, że nie jest to możliwe), bo komputer wcześniej by się rozsypał ze starości niż zakończył pracę, wówczas należy do klasy NP, ale pod jednym warunkiem: jeżeli ktoś poda rozwiązanie, to korzystając z komputera można sprawdzić, czy jest właściwe.

Problem za milion dolarów sprowadza się do rozstrzygnięcia zagadnienia, czy obie klasy, P i NP, są, wbrew pozorom, identyczne, czy też – co bardziej prawdopodobne – nie. Okazuje się, że najwygodniej (co nie znaczy, że łatwo) tego dokonać za pomocą jakiegoś problemu NP-zupełnego, czyli np. saperowego, bowiem jest to taki problem, którego rozwiązanie za pomocą komputera jest równoznaczne z udowodnieniem możliwości uporania się komputerowo z wszystkimi problemami NP. Cała sztuka sprowadza się do znalezienia odpowiedniego algorytmu.
Wypada jeszcze dodać, na czym polega problemowość sapera. Otóż nie wiąże się ona bezpośrednio z rozgrywką, ale z rozkładem elementów na planszy. Konkretnie chodzi o wykazanie niesprzeczności układów min i cyfr.

Zanim zaczną Państwo planować, na co warto roztrwonić nagrodę za rozwiązanie dzięki saperowi problemu P-NP, proponuję pogłowić się nad ostatnią łamigłówką saperową (skarbową) w serii podminowanych („zaskarbionych”) wpisów.

Istnieje sporo mniej lub bardziej zakręconych odmian zadań polegających na odkrywaniu skarbów, których położenie zaszyfrowane jest cyfrowo w saperowy sposób. Do mniej znanych, a bardziej zakręconych, należą skarby obserwowane.

Każda cyfra oznacza w ilu polach, stykających się z polem z cyfrą bokiem, jest skarb.
Ponadto:
– z każdego białego pola bez skarbu widać, patrząc w rzędzie lub kolumnie, przynajmniej jeden skarb;
– żaden skarb nie „widzi” innego skarbu;
– szare kratki (także te z cyframi) ograniczają pole widzenia.   Do widzenia.