Къртици

[Хахо]

В градината си имате 16 дупки от къртици наредени в квадрат 4х4.
От някои се подават къртици, а от други - не.
Вашата задача е да прогоните всички къртици удряйки ги с тояга.
То лесно, ама като ударите една от тях и тя изчезне, в съседните пълни дупки също изчезват мискините, но в съседните празни дупки се появявят нови твари.
За съседни дупки се смятат тези отдолу, отгоре, отляво и отдясно. Но не и тези по диагонал.
Пример:
Началната ситуация е показана на картинката.
Праскаме по каската животината в дупка 10:

0.png

Получава се това. Опухваме симпатягата от дупка 2:

1.png

Става това:

2.png

Ясно е сега, че праскайки 4-та дупка, ще изпълним задачата.
Измислете най-кратък алгоритъм за решаване на произволна начална ситуация.

[jonson64]

Удряш по къртицата с най-много пълни съседни дупки.

[Bibi]

Здравейте,
Правят ми впечатление две неща.
Примерната задача може да се реши и в обратен ред: 4, 2, 10. Сигурно важи за всяка конфигурация.
Освен това е добре да боядисаме каските бели или черни - шахматно. Удрянето по бяла се отразява на черни.
Не мога да намеря решение примерно на случая само с една показана къртица в някоя от 4-те централни дупки.

P.S.
Допълнение към първото наблюдение: важи не само в обратен ред, а в какъвто и да е ред, стига да ударим 2, 4, 10.
Това значи, че изборът на позиции е много по-важен от избора на последователността им.

[Хахо]

Е, щом Биби захапа задачата, няма спасение за горките животинки. Чакам и Митето, Кръстева, Мъдреца...
(Хахо = dedis. Не можех да вляза тук сума време по непонятни причини и отворих нов акаунт. Ако някой админ съдейства, може да върна старото си никче)

[Bibi]

Най-после се разбра защо те няма
Ще опитам да помогна да ти се придвижи въпроса с основния акаунт.
Мен ме отпишете, освен ако случайно не сънувам решението. Нямам свободни минутки.

---
Ти опита ли ресетване на паролата оттук:
https://forum.setcombg.com/login.php?do=lostpw

[Хахо]

Опитвах много пъти, но не ми разпознава мейла.
Невъ майнд...

[kod]

Потребител dedis е регистриран с мейл: fadrom@mail.bg
Ако мейлът вече не се използва мога да го сменя с друг.

[dedis]

Благодаря!
Бях забравил за този мейл.
Оправих се, но сега имам две регистрации и Хахо е излишна.

- - - - - - - - - -

От името на Хахо:
Ето формализирано представяне на този тип задачи (от японци):
http://www.ueda.info.waseda.ac.jp/~n-kato/lightsout/
с голям избор на опции и редактиране на начално подреждане.
Даден е и алгоритъм на решението (за математици).

[kod]

Ще затворя Хахо, ползвай старата.

[dedis]

Благодаря!