Wyskoki bis
Pozwalam sobie powrócić do „wyskoków” sprzed miesiąca ze względu na pewne osobliwe i niełatwe zadanie. Zacznę od przypomnienia.
Łamigłówkowy „wyskok” to bicie podobne do warcabowego, ale wykonywane nie dia-, lecz ortogonalnie. Polega więc na przeskoczeniu w rzędzie lub kolumnie jednym pionkiem przez drugi, stojący obok, na pole tuż za nim i usunięciu przeskoczonego pionka:
Wyskok jest jednym ruchem, ale jeden ruch może także stanowić seria, czyli dwa lub więcej kolejnych wyskoków wykonanych tym samym pionkiem:
Wyskok jest podstawą wyskakanki – zadania, polegającego na wykonaniu najmniejszej liczby „wyskokowych” ruchów niektórymi pionkami, tworzącymi grupę, po których na planszy pozostanie tylko jeden pionek. Oto przykład wyskakanki w sześciu ruchach układu 10 pionków:
Osobliwe zadanie, o którym wspomniałem na wstępie, jest jakby zaprzeczeniem wyskakanki, polega bowiem na wykonaniu minimalnej liczby „wyskokowych” ruchów tak, aby na planszy powstał układ bez możliwości wykonania wyskoku, czyli taki, w którym żadne dwa pionki nie będą umieszczone na sąsiednich polach.
Kwadratowe układy startowe 2×2 i 3×3 są niemal trywialne.
Pierwszy zostaje „zablokowany” po dwóch ruchach, drugi – po trzech. Co ciekawe, w pierwszym przypadku każdy ruch jest, a w drugim może być jednym wyskokiem.
A ile ruchów wystarczy, aby zablokować wyskoki w kwadracie 4×4?
Można udowodnić, że jeśli wykluczymy ruchy złożone z serii wyskoków, to zablokowanie wyskoków dla układu n×n nie będzie możliwe po mniej niż (n^2)/3 ruchach. Ruchy seryjne są jednak dozwolone, więc zagadnienie pozostaje otwarte.
Zadanie z kwadratem 4×4 było w tegorocznym styczniowym Świecie Nauki. Prawie wszyscy z blisko stu czytelników, którzy nadesłali rozwiązania, uporali się z układem w co najmniej pięciu ruchach, na przykład tak (na planszy pozostaje sześć pionków bez szansy na wyskoki):
Tylko dwu osobom wystarczyły cztery ruchy. Jakie?
Czy zadanie jest rzeczywiście takie trudne i czy równie trudno jest zaprząc do pracy komputer?
Komentarze
1. 15 – 3
2. 28 – 30
3. 17 – 15 – 13
4. 26 – 14 – 2 – 4 – 16 – 28 – 26
Zadanie nie było trudne, bo wiedziałam że mają być cztery ruchy. Tylko nie bardzo rozumiem drugie pytanie „czy równie trudno jest zaprząc do pracy komputer?”. Czy jest jakaś dostępna aplikacja do użycia, czy też sama mam napisać program?
Chodzi o napisanie programu.
mp
22-24; 20-22-34; 9-7; 11-9-21-33-35-23-11;
Ostatni wieloskok można wykonać też w drugą stronę: 11-23 itd.
1. 21-33
2. 17-5
3. 9-21-19
4. 29-27-25-13-15-17-29
Znalezienie rozwiązania „na piechotę” okazało się zaskakująco łatwe.
Dla mnie, jak teraz zauważyłem, zadanie okazało się trudne ponieważ podałem błędną odpowiedź.
Gdybym wiedział, że istnieje rozwiązanie w czterech ruchach, to znalazłbym się na podium:
1) c4-a4
2) e4-c4-c6
3) d2-f2
4) b2-d2-d4-d6-b6-b4-b2
Moja powyższa ocena trudności jest niemiarodajna:
oceniłem zadanie jako zaskakująco łatwe, ale rozwiązywałem INNE zadanie niż to w „Świecie Nauki” – miałem przecież dodatkową informację o istnieniu rozwiązania w czterech ruchach.
Dzięki temu skupiłem się na przygotowaniu w trzech ruchach dogodnej pozycji dla ostatniego, czwartego ruchu.
Mój komentarz-pytanie do tego wpisu ma podobny sens.
http://penszko.blog.polityka.pl/2017/01/23/marszalek-i-kardynal/
Teraz- po tym czasie – sądzę, że była to podpowiedź, ale nie potrafiłbym tego „dowieść”.