Решение Нонограмм (Picross)

Question

сегодня пятница, давайте разберемся с забавной головоломкой / алгоритмом.

Одна из моих любимых игр для Nintendo DS - Picross DS . Игра довольно простая, она включает в себя решение головоломок под названием Nonograms . Вы можете попробовать простой онлайн-клон Picross здесь: TylerK's Picross .

Nonograms - это сетка с последовательностями чисел, определенными для каждой строки и столбца сетки. Числа определяют блоки «заполненных» квадратов для этой строки / столбца, но незаполненные области с обеих сторон блоков не определены. Например, если у вас есть строка, которая выглядит следующим образом:

_{(источник: steam-punk.net )}

Возможные решения для этой строки:

<sub>(источник: steam-punk.net )

(источник: steam-punk.net )</sub>

и т.д.

«4 5» просто говорит вам, что где-то в строке есть 4 заполненных последовательных блока, за которыми следуют 5 заполненных последовательных блоков. Это будут единственные заполненные блоки и количество места до / после них не определены.

Загадка завершается, когда все строки и столбцы соответствуют определению, без каких-либо противоречий.

Чрезвычайно простая в концепции игра, но некоторые из них могут занять некоторое время, чтобы решить некоторые из них вручную. Головоломки Picross DS постепенно увеличиваются в размере до 25x20 сеток, что обычно занимает около получаса.

Однако мне всегда приходит в голову, что было бы довольно легко написать программу для решения. Я никогда не удосужился об этом, но, возможно, некоторые люди здесь будут наслаждаться вызовом. Если будет опубликовано приличное количество решений, я сравню их по большой головоломке друг против друга, подобно тому, что Паоло Бергантино сделал здесь со своим вопросом о Боггле . На странице Nonogram Wikipedia содержится довольно много информации о методах атаки на головоломку, если вы хотите сослаться на это.

Вот простое для анализа определение Puzzle # 1 от TylerK's Picross, так что у вас есть что написать для программы. Строка 1 - это размеры головоломки (вероятно, ненужные), строка 2 - определения строк, строка 3 - определения столбцов. Это только первое, что пришло в голову, поэтому, если кто-то может придумать лучший формат ввода, не стесняйтесь комментировать или редактировать этот пост, чтобы включить его.

15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10

Answer 1

Да, проблема в NP-полноте, но это только означает, что вы (в значительной степени) застряли с экспоненциально растущим временем выполнения по мере роста размера головоломки. Но в реальной жизни размеры головоломки не растут. Вряд ли кто-либо потрудится создавать пазлы размером более 100х100, а подавляющее большинство - меньше 50х50. Создание решателя, который за доли секунды решит 95% головоломок, опубликованных в книгах и журналах, на самом деле не представляет особой сложности. Это сделает довольно прямолинейная поисковая система глубины.

Что менее очевидно, так это то, что есть небольшая часть головоломок, которые являются довольно неприятными и приведут к взрыву времени выполнения для большинства простых решателей. Большинство из них - плохо продуманные головоломки, которые также трудно или невозможно решить людям, но некоторые являются особенно умными головоломками, которые опытные люди могут решить, используя более глубокое понимание, чем большинство программ ИИ.

Я написал собственный решатель, который очень быстро решит большинство головоломок, и я провел опрос многих других решателей с результатами тестов, сравнивающими их производительность. У меня также есть обсуждение интересного класса сложных головоломок (головоломки Domino), которые демонстрируют, как некоторые головоломки, которые не сложны для умного человека, оказываются очень сложными для большинства программ. Ссылки на мой решатель и Domino Puzzle будут найдены в обзоре.

Я думаю, что есть еще много возможностей для совершенствования, и я бы посоветовал людям с новыми идеями попробовать их. Но стоит отметить, что очевидные вещи уже сделаны, и в их повторном использовании нет особого смысла.

Answer 2

Определение того, существует ли решение Nonogram / является уникальным, является NP-трудным. Смотри http://en.wikipedia.org/wiki/Nonogram#cite_note-0

Answer 3

Вместо того, чтобы пытаться разместить «первую» строку, она существенно сократит ваш поиск, если вы попытаетесь получить информацию из «наиболее ограниченной» строки или столбца, который может иметь несколько принудительных значений. Быстрое указание - сложить все значения в строке / столбце и добавить #_of_values ​​- 1, а затем найти строку / столбец с наибольшим таким значением (или наименьшей разницей между этим значением и количеством строк или столбцов, если строки и столбцы различаются). Таким образом, если у вас есть головоломка 25x25, и одна из строк «5 1 1 6 1 1 3», эта строка имеет значение 24, что означает, что она очень ограничена - относительная позиция всех, кроме одного из пустых квадратов в этом ряду известно, и последний пустой квадрат может находиться в любом из 8 различных относительных положений. Таким образом, для каждой группы заполненных квадратов есть только две возможности: дополнительный пустой квадрат слева от этой группы или дополнительный пустой квадрат справа от этой группы. Так, например, пять из заполненных квадратов в этой группе из 6 уже известны.

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

Answer 4

Реальная проблема в том, может ли кто-нибудь придумать алгоритм, который решает указанную головоломку быстрее, чем человек? Это легко для относительно простых головоломок, таких как контрольная, но если головоломка будет расти, большинство алгоритмов здесь быстро замедлятся. Вот загадка, которую я пытался решить. Проблема в том, что в 4-м ряду, например, 2220075 возможных комбинаций, я полагаю. Если алгоритм Чарли временно принимает неправильную строку для строки 3, он будет проходить все эти комбинации для строки 4. И это не говоря уже о случае, когда алгоритм противоречит самому себе в строке 35 из-за ошибки, которую он допустил в строке 2.

Мой алгоритм был похож на алгоритм Джона. Не удалось запустить в режиме x86 на моем 64-битном рабочем столе. Когда я переключил его в 64-битный режим и дал ему поработать всю ночь, мой компьютер был совершенно неработоспособен по утрам. В процессе было зарезервировано 8 гигабайт памяти (8 гигабайт физической на рабочем столе), и компьютер не отвечал из-за неистового обмена. И это даже не решило все возможные ряды. Не говоря уже о том, что он даже не затрагивал возможные комбинации столбцов.

List<List<int>> rows =
                new List<List<int>>()
                {
                    new List<int> { 8,29,4 },
                    new List<int> { 6,4,25,4,3 },
                    new List<int> { 5,3,2,3,9,4,2,1,3 },
                    new List<int> { 4,2,2,2,2,1,2,2 },
                    new List<int> { 4,1,1,9,10,2,2,1 },
                    new List<int> { 3,2,6,5,5,1,1 },
                    new List<int> { 3,1,5,5,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,3,3,1,1 },
                    new List<int> { 3,1,3,6,2 },
                    new List<int> { 3,1,2,3,2,4,2 },
                    new List<int> { 4,3,1,8,7,1,2,3 },
                    new List<int> { 4,2,1,12,11,1,2,4 },
                    new List<int> { 5,1,2,7,2,2,6,1,1,4 },
                    new List<int> { 4,1,1,1,6,2,2,6,1,2,1,3 },
                    new List<int> { 4,1,1,2,4,3,4,3,1,1,1,1,3 },
                    new List<int> { 4,1,1,2,1,4,1,2,3,2,1,2,2 },
                    new List<int> { 3,1,1,1,2,5,6,1,1,1,3,2 },
                    new List<int> { 3,2,1,1,2,1,5,4,4,2,1,2,1,2 },
                    new List<int> { 3,2,2,1,1,4,2,2,3,1,1,2,1,1,2 },
                    new List<int> { 3,1,3,2,1,1,4,1,5,3,2,1,3,1,2 },
                    new List<int> { 3,1,2,1,2,1,3,7,4,1,4,2,2 },
                    new List<int> { 2,1,4,1,1,1,2,6,2,2,2,3,2,1 },
                    new List<int> { 2,2,4,1,2,1,2,5,2,1,1,3,2,1 },
                    new List<int> { 2,2,1,4,1,1,3,3,2,1,4,4,1 },
                    new List<int> { 2,3,3,2,1,3,3,7,4,1 },
                    new List<int> { 2,3,2,4,5,8,1,2,1 },
                    new List<int> { 1,1,3,11,6,7,1,3,1 },
                    new List<int> { 1,1,2,2,13,10,2,3,2 },
                    new List<int> { 1,2,3,1,6,1,1,7,1,5,2 },
                    new List<int> { 1,1,3,2,6,1,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,6,7,2,4,2,5,6,1 },
                    new List<int> { 1,1,2,3,1,4,2,2,11,2,1 },
                    new List<int> { 1,1,1,1,2,1,5,10,1,1,1 },
                    new List<int> { 1,1,1,1,4,7,4,10,1,1,1 },
                    new List<int> { 1,2,1,1,28,1,1,3 },
                    new List<int> { 1,2,1,2,27,2,1,3 },
                    new List<int> { 1,1,1,1,26,1,1,1,1 },
                    new List<int> { 2,3,1,28,2,1,2,1 }
                };
            List<List<int>> cols =
                new List<List<int>>()
                {
                    new List<int> { 40 },
                    new List<int> { 28,1 },
                    new List<int> { 23,8 },
                    new List<int> { 5,6,7,4 },
                    new List<int> { 3,6,1,9,3,1 },
                    new List<int> { 2,3,2,5,4,2,2 },
                    new List<int> { 1,2,4,1,2,5,2 },
                    new List<int> { 1,1,4,9,2,3,2 },
                    new List<int> { 2,4,2,6,1,4,3 },
                    new List<int> { 1,4,1,3,4,1,6 },
                    new List<int> { 1,4,3,2,3,5,5 },
                    new List<int> { 2,4,1,2,3,4,1,3 },
                    new List<int> { 1,2,3,4,2,2,4,4,1 },
                    new List<int> { 1,1,2,3,2,1,4,2,4 },
                    new List<int> { 2,3,5,3,3,5,4 },
                    new List<int> { 3,1,6,1,2,5,5 },
                    new List<int> { 3,2,6,2,15 },
                    new List<int> { 3,1,8,2,13 },
                    new List<int> { 2,2,4,5,15 },
                    new List<int> { 2,2,2,2,22 },
                    new List<int> { 2,1,1,1,12,6 },
                    new List<int> { 2,1,10,4,5 },
                    new List<int> { 3,1,3,1,2,4 },
                    new List<int> { 3,1,1,4,3,1,4 },
                    new List<int> { 3,2,2,3,2,2,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,2,5,2,1,1,4 },
                    new List<int> { 3,1,1,3,2,2,4 },
                    new List<int> { 3,1,6,4,5 },
                    new List<int> { 2,2,12,2,6 },
                    new List<int> { 2,2,1,1,22 },
                    new List<int> { 2,1,2,2,5,15 },
                    new List<int> { 3,1,4,3,2,14 },
                    new List<int> { 3,1,7,2,1,13 },
                    new List<int> { 3,2,6,1,1,6,8 },
                    new List<int> { 3,2,5,2,2,4,7 },
                    new List<int> { 2,1,2,4,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,4,4,3,1,4,5,1 },
                    new List<int> { 1,1,5,1,1,2,1,2,2,3,2 },
                    new List<int> { 1,5,2,2,1,5,5,3 },
                    new List<int> { 1,6,2,1,4,2,6,1 },
                    new List<int> { 1,6,2,6,5,2 },
                    new List<int> { 1,5,3,1,9,2 },
                    new List<int> { 2,2,4,2,6,3 },
                    new List<int> { 1,2,2,2,9,2,1 },
                    new List<int> { 3,5,5,8,4 },
                    new List<int> { 4,13,9 },
                    new List<int> { 27,2 }
                };

Авторские права принадлежат Гильдии информационных технологий Тампере / Kaisapais / Финская пивоварня.

Answer 5

Это кажется довольно очевидным случаем для поиска в глубину с обратным отслеживанием, как в случае проблемы «n queens». Хорошая деталь в том, что вы можете не только размещать строки / столбцы, но и сдвигать блоки.

Хорошо, вот схема.

1. Начните с пустой доски, поместите первый ряд

2. Теперь на этой доске поместите вторую строку и проверьте ее на соответствие столбцовым ограничениям. Если это проходит, рекурсивно попробуйте следующий ряд против этого состояния; если это не пройдет, попробуйте следующее возможное размещение этой строки.

3. Если в любое время у вас закончатся возможные размещения строки, которые удовлетворяют ограничениям, то у головоломки нет решения. В противном случае, когда у вас закончатся ряды, вы решите проблему.

Удобно, что эти строки можно рассматривать как двоичные числа, поэтому существует естественный порядок возможностей.

Answer 6

Несколько месяцев назад я написал решатель для нонограмм на C ++. Он просто ищет все допустимые позиции для затененных и пустых ячеек. И на каждом шаге решения это выглядит, если каждая позиция в порядке. Итак, вот результат для нонограммы Чеда Бёрча со временем: http://i.stack.imgur.com/aW95s.png.

И я попробовал свой решатель на нонграмму Микко Рантанена: http://i.stack.imgur.com/o1J6I.png.

Answer 7

У меня сейчас недостаточно времени, чтобы конкретизировать решение, но я бы так и решил его.

"function1" определяет возможные комбинации для строки или столбца с учетом ограничений чисел сверху или сбоку, а также квадратов, которые уже заполнены, и тех, которые были очищены.

"function2" берет выходные данные из function1 и логически, а также все результаты вместе - места с единицами могут быть заполнены.

"function3" берет вывод из функции1 и логически или все результаты вместе - пятна с нулями могут быть очищены.

продолжайте применять function2 и function3 ко всем строкам и столбцам до тех пор, пока больше не будет пустых или заполненных полей. Если загадка решена, то все готово.

Если загадка не решена, то возьмите строку или столбец с наименьшим количеством возможностей и примените первую возможность. Затем примените функции 2 и 3 к новой плате. Если это приводит к противоречию (0 возможностей для строки или столбца), отмените возможность и попробуйте другую. Продолжайте повторять, пока это не будет найдено решение.

Answer 8

Вот что я нашел:

Все задачи NP Complete имеют одинаковое чувство. Всегда легко решить следующие 80% оставшихся случаев. Например, нанограммы разлагаются на одну строку. Можно написать подпрограмму, solve_one_line(old_state, line_definition, new_state), чтобы обновить то, что известно об одной строке, а затем продолжать перебирать строки и столбцы. В некоторых случаях это не помогает, поэтому вы пишете что-то, чтобы решить 80% этих случаев. Затем вы добавляете случайные числа и решаете все случаи, которые вы когда-либо находили, но возможно построить оптимально плохое.

Другие игры по этой схеме: MineSweeper и Soduku .

Мышление в параллель трудно . Например, вы можете выяснить, что приведенная выше подпрограмма solve_one_line не повлияет на другую строку, если она выполняется в строке, или на другой столбец, если она выполняется в столбце.

Теперь вы получите:

  all_until_completion(rows):
      solve_one_line(...)
  all_until_completion(cols):
      solve_one_line(...)

Это позволяет вам работать с 20 ядрами (20x20) без блокировки данных или чего-либо еще. Затем вы думаете о запуске на видеокарте с каждой ячейкой процессора. Затем вы замечаете, сколько времени прошло.

Однажды я почувствовал себя старым, когда смотрел на современный учебник по информатике, где запись O (n) была заменена на запись O (n, p) , потому что никто не хотел оценивать алгоритм для одного процессора. Решение 8 queens - это отличный, быстрый рекурсивный алгоритм с быстрым отказом, эффективным использованием памяти, который работает только на одном процессоре.

Проблемы - хорошие оправдания для игры . Растирание же становится скучным. Просмотрите список технологий, с которыми вам может потребоваться больше опыта: тестирование на основе поведения; внедрение зависимости; чисто функциональное программирование; нейронные сети; генетические алгоритмы; быстрый, неаккуратный и неуправляемый; GPGPU; OCR; обучение на основе примеров; краудсорсинг; и т.д. Выберите один и попробуйте использовать его как-нибудь, чтобы решить проблему. Иногда целью является не решение проблемы, а странствие по неизвестной территории.

Внесите что-нибудь. * Это может быть просто как рецензия. Лучше может быть хранилище сотен нанограмм, чтобы другие могли играть. [Дайте мне знать, если существует хранилище, в противном случае я сделаю его]. Начните вносить свой вклад, как только у вас будет что-то, что вы находите аккуратным. Обратите внимание на слова клингона: Возможно, сегодня - это хороший день для смерти; Я говорю, что мы отправляем его.

Так что пишите причудливые, параллельные решения проблем NP и делитесь ими. И хорошего дня!

Answer 9

Позвольте мне указать на 2 интересных поворота на классических головоломках без грамматики:

• Когда головоломка делает больше, чем просто список длин занятых ячеек. Этот публичный вызов заранее ограничил некоторые ячейки как занятые: http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

• Когда неграмма содержит больше, чем просто пустые / занятые ячейки, но использует пятна разных цветов, чтобы занять ячейки. Например, см. http://onlinenonograms.com; Решая их вручную, я чувствую, что на самом деле их легче решить, чем обычные нонограммы.

Особая проблема для разработчиков алгоритмов заключается в том, что цветные неограммы значительно выигрывают от совместного рассмотрения горизонтальных / вертикальных ограничений. Обычные решатели строки за строкой находятся здесь в явном недостатке.

Answer 10

Стивен Симпсон написал решатель неграмм, который свободно доступен в различных версиях, включая скрипт JavaScript. Он обсуждает детали алгоритмов на этом веб-сайте (например, здесь - в основном он использует серию линейных вычислителей, которые соотносятся со скоростью и полнотой, в сочетании с делением и завоеванием, угадывая, когда все линейные преобразователи достигнут мертвых конец. У него также есть ссылки на другие подходы, которые охватывают больше вопросов, чем мы имеем здесь.