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

Эй, это в пятницу днем, пусть будет решать головоломку/алгоритм проблемы.

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

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

http://steam-punk.net/images/picross1.jpg

Возможные решения для этой строки будут включать:

http://steam-punk.net/images/picross2.jpg http://steam-punk.net/images/picross3.jpg

и др.

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

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

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

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

Здесь легко разобрать определение головоломки №1 от TylerK 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

Ответы

Ответ 1

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

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

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

Ответ 3

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

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

Ответ 4

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

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

  • Начните с пустой доски, поместите первую строку

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

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

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

Ответ 5

Реальная проблема заключается в том, может ли кто-нибудь придумать алгоритм, который решает головоломку быстрее, чем человек? Это легко для относительно простых головоломок, таких как эталонный, но если головоломка растет, большинство алгоритмов здесь быстро замедлятся. Вот головоломка, которую я пытался решить. Проблема в том, что, например, у 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/Финский пивоваренный завод.

Ответ 6

Мне не хватает времени на то, чтобы сформулировать решение, но именно так я бы справился с этим.

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

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

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

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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

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

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

Ответ 10

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

Все NP Все проблемы имеют одинаковое чувство. Всегда легко решить следующие 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 quens - отличный, быстрый рекурсивный алгоритм с быстрым отказом, эффективным использованием памяти и работает только на одном процессоре.

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

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

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