частный случай - если сумма чисел нечётна, решений нет

А можно по подробнее? Я не въезжаю почему.

От конца иди

Потому что нельзя разбить на пары равных или дающих в сумме 10.

Пары равных в общую сумму добавляют всегда четное число. Пара дающих 10 в общую сумму добавляют всегда четное число. Значит, если результат нечетный - где-то была «плохая» пара.

Семечки. Есть реализация этой игры для андроеда.

Непосредственно на твой вопрос ответа не знаю, но задача сводится к задаче о максимальном паросочетании, которая вполне разрешима.

http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings

Дык решается рекурсивным поиском в глубину с бектрекингом же. По очереди пробуешь удалять все подходящие пары чисел и для каждой образовавшейся задачи снова запускаешь тот же алгоритм. Если на каком-то этапе поиск скажет, что решений нет, возвращаешься на уровень выше и продолжаешь дальше.

Если ходы закончились - то все незачеркнутые числа дублируются.

Вот это странное какое-то условие, в стандартной такой задаче его нет для неё svu правильно условие написал. Только надо не четность, а деление на 10 сразу проверять.

Формализуй, что значит дублируются.

Если ходы закончились - то все незачеркнутые числа дублируются.

Упустил это правило. Если такая ерунда, то не знаю, есть ли полиномиальный алгоритм.

да он абсолютно криво описал условия, нужно взять и посмотреть задачу. Т.е. если у нас кончаются ходы, то мы выписываем все числа под нашшами подряд, т.е. было

1 2 *
3 * 4

стало:

1 2 *
3 * 4
1 2 3
4

Реализация по ссылке не пашет. Числа по краям не убираются. Т.е. там игра на плоскости, а не на развертке тора.

после всех удалений получилась такая лажа:

   4##
   5#1
   0##

   4##
   5#1
   0##
   451
   0

Вариант для андроида с туториалом https://play.google.com/store/apps/details?id=ru.redspell.doodlenumbers&h...

(1,0,9) (1,8,17) (2,0,0) (1,10,11) (1,7,12) (1,20,29) (1,19,21) (1,24,33) (1,15,42) (1,23,25) (1,27,36) (1,31,40) (1,34,35) (1,26,44) (1,22,28) (1,13,49) (1,6,14) (1,5,16) (1,4,18) (1,37,46) (1,32,38) (1,39,48) (1,30,41) (1,3,43) (1,2,45) (1,1,47) в 26 ходов. 1 — вычеркивание, 2 — копирование цифр.

Программы не сохранилось.

Это алгоритм поиска самого решения. Он очень сложен т.к. дерево растет очень сильно. Меня интересует можно ли написать алгоритм проверки на существование решения за более короткое время.

частный случай - если сумма чисел нечётна, решений нет

так числа же потом по условию дублируются. Следовательно потом уже будет четная.

единственное чего я не понимаю, что делать например с

888
888
888

Какое совпадение, буквально вчера в новом выпуске Pragmatic Perl была опубликована эта задачка:
http://pragmaticperl.com/issues/08/pragmaticperl-08-perl-golf.html

А когда у них ответы публикуются?

В следующем выпуске, т.е. в ноябре.

Но можно отслеживать появление решений здесь: https://github.com/PragmaticPerl/golf-08/tree/master/script

буду учить перл

Алгоритм

1. создаем массив и случайный генератор, заполняем поле
2. определяем функцию соседний(клетка1,клетка2):1/0 — return true, если индексы массива отличаются на 1, на ряд или между числами ***
3. определяем функцию можно_удалить():1/0 — return соседний() и (равны или сумма=10)
4. определяем функцию удалить(клетка1,клетка2) — если можно_удалить(), добавить пару (ход) в список, обновить массив
5. определяем функцию решение() - вызов в цикле удалить() пока это возможно, затем подсчет оставшихся чисел
6. определяем функцию откат() - если решение не найдено, откатить последнее удаление и попробовать другую соседнюю пару чисел
7. перебрать так все пары.

Если в процессе перебора чисел не останется, решение найдено, вывести список удаляемых соседей. Иначе решения нет.

Я же говорил, что такое решение очень трудоемкое, по причине наличия функции дублирования. Тред почитай.

Дублирование добавляет новую ветку: если ходы закончились, сдублировать вниз оставшиеся числа. При этом может появиться максимум 1 новая горизонтальная удаляемая пара (первая и последняя цифры встают рядом) и несколько вертикальных удаляемых пар (т.к добавляется новый ряд). Дублирование не дает новых горизонтальных пар, т.к причиной дублирования было отсутствие соседей. Предполагаю, что дублирование почти всегда ведет к проигрышу, т.к. количество добавленных чисел больше, чем полученных новых пар (исключение - когда размер массива оставшихся чисел длиной ровно в 1 ряд, тогда дублирование создаст копию по всей длине и взаимно уничтожит ряд). За этим исключением, дублирование не влияет на результат — то есть на ответ на вопрос «есть ли решение у данного поля?»

https://github.com/PragmaticPerl/golf-08/blob/master/script/technix.pl