Saperska pomyłka
Podobno błędy bywają pożyteczne, bo czegoś się na nich uczymy. Oczywiście nie każdy i nie zawsze. W przypadku sapera, który się pomyli, o pożytku nie może być mowy, raczej wręcz przeciwnie. Chyba że błąd będzie dotyczył zadania zwanego saperem. Taka „eksplozja” zdarzyła się w ósmym Omnibusie, na co zwrócili uwagę czytelnicy.
Na stronie 49 jest zestaw sześciu zadań pod tytułem „Mały saper”. Mały, ponieważ diagramy są nieduże (7×7), a ostatni wygląda tak:
Z żółtego pola wypadła trójka, więc rozwiązania się rozmnożyły. A pożytek z ubytku taki, że stał się on przyczynkiem do tworzenia innych łamigłówek, jakby wariacji na temat błędu. Z dyskusji z jednym z czytelników wynikły poniższe dwa zadania. Zacznę jednak od przypomnienia zasad „Małego sapera”.
Każda cyfra oznacza, w ilu sąsiednich kratkach – stykających się z polem z cyfrą bokiem lub rogiem – jest mina. Należy oznaczyć wszystkie zaminowane pola, których – to dodatkowy warunek – jest dziesięć.
W pierwszym zadaniu zakładamy, że powyższy diagram (bez trójki) jest poprawny. Natomiast zmieniamy dodatkowy warunek: liczba zaminowanych pól jest najmniejszą możliwą. Jaka jest ta liczba i w których polach są miny?
W drugim, znacznie trudniejszym zadaniu w diagramie cyfry brakuje – ale nie trójki, lecz jedynki. Na którym polu należy umieścić tę jedynkę, aby rozwiązanie było jedno? Wystarczy wskazać jedno takie pole, choć być może ktoś się pokusi o wskazanie wszystkich – jeśli jest ich więcej. Dodatkowy warunek (dziesięć min) pozostaje bez zmian.
Komentarze
Zadanie pierwsze, robione ręcznie, wychodzi mi minimalnie 7 bomb:
9 – bomba
0 – puste pole
1929100
0000000
1000101
9000090
2010202
0900090
0920101
Pierwszy problem nie ma jednego rozwiązania przy dowolnej zadanej liczbie min. Dla siedmiu min są dwa rozwiązania (i jest to najmniejsza ilość dla której rozwiązania istnieją). Największa ilość min to 12, dla której jest 5 rozwiązań.
Dwa rozwiązania dla 7 min: (o-mina x-pusta kratka)
1o2o1xx
xxxxxxx
1xxx1x1
oxxxxox
2x1x2x2
xoxxxox
xo2x1x1
1x2o1xx
xoxxxxx
1xxx1x1
xxxxxox
2x1x2x2
ooxxxox
xo2x1x1
Drugi problem ma dwa różne rozwiązania. Dodatkowe liczby (1) są umieszczone w kratkach sąsiadujących bokiem z lewą dolną narożną kratką.
1o2x1ox
xxoxxxo
1xxx1x1
oxxxoxx
2x1x2o2
1oxxxxo
xx2o1x1
1o2x1ox
xxoxxxo
1xxx1x1
oxxxoxx
2x1x2o2
xoxxxxo
x12o1x1
Ad 1: 7
Co do drugiego pytania: nie ma takiego pola.
Niech (a, b) oznacza pole w rzędzie a-tym od góry, w b-tej kolumnie od lewej.
Wtedy zadanie nie ma rozwiązań, jeśli umieścimy jedynkę na jednym z pól: (1,2), (4,1), (4,5), (5,1), (5,2)…
Zadanie ma 3 rozwiązania, gdy umieścimy jedynkę na jednym z pól: (5,0), (6,1)
Zadanie ma 5 rozwiązań gdy umieścimy jedynkę na polu (6,0).
Dla pozostałych pól liczba rozwiązań to co najmniej 15, a rekordzistą jest pole (1,0), dla którego jest aż 200 różnych rozwiązań.
Oczywiście wszystko, przy założeniu, że na planszy znajduje się dokładnie 10 min.
zad 1: najmniej może być: 9 min,
poniżej: mina to *, puste pole to 0
1*2*100
0000000
10001*1
*000000
20102*2
0*00*0*
0*20101
Minimum wychodzi mi 7.
http://postimg.org/image/achoknhu3/
Chmmm… Mój komentarz został uwolniony, wnioskuję zatem, że rozwiązanie jest błędne.
(Komentarz został cofnięty po krótkiej wymianie zdań, bowiem okazał się poprawny)
Sprawdzałem kilkakrotnie mój program, który wyszukiwał rozwiązania i nie znalazłem błędu. Nawet napisałem program od nowa, otrzymując takie same wyniki. Albo robię bardzo subtelny błąd, albo mam rację i nie ma rozwiązań spełniających wszystkie warunki.
Może pochwali się Pan rozwiązaniem, które Pan zna. Chciałbym zweryfikować, że rzeczywiście spełnia ono warunki.
Może tak: wśród podanych przez Pana pozycji (w w nawiasach) są dwie, które dają jedno rozwiązanie. Szybko rozwiązuje się je „na piechotę”.
mp
Nie pozostaje mi nic innego, jak umieścić swoje wyniki.
W przykładach, które nie generują rozwiązań, rozwiązań na pewno brak, co można szybko ręcznie sprawdzić (w 4 przypadkach dokładamy jedynkę, która obejmuje większy obszar niż istniejąca już w diagramie dwójka, w ostatnim przypadku też szybko dochodzimy do sprzeczności).
Pozostałe trzy pola generują minimum 3 rozwiązania. Oto one:
(podobnie jak poprzednio: 9 – bomba, 0 – pole puste)
(5, 0)
1929109
0000009
1000101
9000900
2010292
1900009
0029101
1929100
0000009
1090101
9000900
2010292
1900009
0029101
1920190
0090009
1000101
9000900
2010292
1900009
0029101
(6, 0)
1929109
0000009
1000101
9000900
2010292
0900009
1029101
1929100
0000009
1090101
9000900
2010292
0900009
1029101
1929100
0000009
1000101
9000900
2910292
0000009
1929101
1929100
0000009
1000101
9000900
2010292
9090009
1029101
1920190
0090009
1000101
9000900
2010292
0900009
1029101
(6, 1)
1929109
0000009
1000101
9000900
2010292
0900009
0129101
1929100
0000009
1090101
9000900
2010292
0900009
0129101
1920190
0090009
1000101
9000900
2010292
0900009
0129101
Co racja, to racja. Przydałby się (przynajmniej w tym przypadku) warunek:
Wszystkie miny powinny być na polach wskazanych cyframi (chyba, że nie jest to możliwe).
mp
Spytko,
skoncentruj się na dwójkach.
Jak się lepiej przyjrzeć to starczy 7 min 🙂
1*2*100
0000000
1000101
*0000*0
2010202
0*000*0
0*20101
tego już się chyba poprawić nie da ???