Dr. K. L. Metlov (dr_klm) wrote,
Dr. K. L. Metlov
dr_klm

Categories:

нонограммы

Осенью прошлого года я был в Крыму, и познакомился там с двумя девушками, решавшими (новые для меня) "японские кроссворды". Еще тогда мне захотелось эти кроссворды порешать на КПК, но, поскольку в тот раз я не совсем отдыхал там -- времени у меня не нашлось. Потом забыл. Сейчас вспомнил.

Так вот выглядит типичная нонограмма. Задача состоит в том, чтобы расставить на игровом поле черные квадратики в соответствии с заданным набором цифр (слева и сверху). Потому головоломка эта имеет еще одно английское название -- "Paint by numbers" (рисование при помощи чисел).

Как именно "в соответствии" ? Расставлять квадратики нужно так, чтобы по строкам (столбцам) они образовывали цепочки заданной (числами в данной строке/столбце) длины, разделенные, как минимум, одним белым квадратиком. Тоесть, если, например, напротив строки (или столбца) написано "7 1 3" то значит в конечной картинке эта строка (столбец) содержит 10 черных квадратиков, разделенных (как минимум одним белым квадратом) на три цепочки (длиной 7, 1 и 3). Если, например, общая длина строки (столбца) 15, то числа 7 1 3 около него говорят, что выглядеть в конечной картинке он может так
 1 2 3 4 5 6 7 8 9 A B C D E F
[][][][][][][]  []  [][][]          , или так
  [][][][][][][]  []  [][][]        , или так
[][][][][][][]      []  [][][]      , и т.д.
Как именно -- зависит от чисел в других строках и столбцах. В решенной нонограмме все строки и столбцы должны соответствовать числам, тогда получится некоторая картинка...

Ну что ? Вы уже можете разгадать приведенную выше нонограмму ?

Решать нонограммы мы тут, конечно будем при помощи программы на языке J. Ну а на каком Вы думали ? ;-)

Но для начала, немного истории и математики. Придумала эти головоломки госпожа Нон Ишида (Non Ishida, известная еще своим рисованием включенными/выключенными окнами на небоскребах) из Японии и опубликовала первые три из них в 1988-м. С 1990-го нонограммы регулярно публикуются в The Sunday Telegraph, после чего они и стали именоваться нонограммы по имени создательницы. Кроме того, что сейчас они публикуются в несчетном количестве газет, есть не одна дюжина книг, посвященных исключительно им. Пишут о нонограммах и научные работы, важнейшей из которых является доказательство NP полноты задачи о решении нонограммы[1]. Продается несколько коммерческих программ для решения нонограмм (в т.ч. и для КПК, и для Playstation). Еще больше информации можно почерпнуть здесь (на английском).

Всего этого я не знал, когда решил написать программу для решения нонограмм на J. А когда узнал, то было уже поздно. :-) Ну, раз уж не суждено мне быть первым, решившим эту головоломку на компьютере, то могу я хотя-бы попретендовать на авторство самого короткого и простого кода для ее решения ? :-)))

Программа выглядит вот так:
NB. ---------- Compositions of an integer, based on APL87 paper ---------------
NB. "Some Uses of { and }" by by Roger Hui. More precisely on article 2 at
NB. http://listserv.unb.ca/bin/wa?A2=ind9402&L=apl-l&F=&S=&P=1840
NB. Which code I (K.L.M.) just converted to functional (tacit) form.
k =: [: i. >:
c =: ([: <: [) ([ ! +) [: |. ]
sublists =: ([: - [ c [: k ]) {. each [: < ([ - 1:) comp ]
klists =: ([ - 1:) {. each ([: k ])
recur =: [: ; ([: k ]) ,. each sublists -"1 each klists
comp01 =: [: i. ([: * [) * [: >: ] , 0:    NB. recursion tail for x.=0 or x.=1
comp =: comp01`recur @. (1: < [)
NB. ---------------------------------------------------------------------------

эта первая часть служит для нахождения всех вариантов разбиения целого числа на заданное количество положительных слагаемых (по анлийски такое разбиение называется integer composition of n into k parts). И тут меня опередили (даже на языке J)... Этот алгоритм, заметив полезное с точки зрения организации рекурсии свойство упорядоченных разбиений, впервые записал Roger Hui, я только перевел его в функциональную (tacit) форму. Ну а вот дальше, собственно, мой код (в котором, следуя пожеланиям читателей, я большему количеству элементарных глаголов дал символические имена):
rl =: [: +/"1 ]
nr =: [: # ]
seq01 =: 2: | [: i. [: +: nr
v =: 1: }."1 ([: ,. (1: + nr comp [: >: [ - nr + rl) ,."1 ]) # seq01
rows =: [: > {:
nrows =: [: # [: > {:
cols =: [: > {.
ncols =: [: # [: > {.
va =: (nrows v each cols) (; ([: < ])) ncols v each rows
def1 =: [: <"1 [: |: [: > [: *./ each cols
def0 =: [: <"1 [: |: [: > [: ([: -. +./) each cols
correct1 =: [: *./"1 each rows (] ~: *:)"1 each def1
correct0 =: [: *./"1&.> rows *:"1 each def0
leaveonly =: ([: cols ]) ; [: < [ # each ([: rows ])
enfdef1 =: correct1 leaveonly ]
enfdef0 =: correct0 leaveonly ]
iter =: [: |. [: enfdef0 [: enfdef1 [: |. [: enfdef0 enfdef1
iterate =: iter^:_
cnt1 =: [: > [: ([: {. $) each >
counts =: ([: cnt1 {.) ; [: < [: cnt1 {:
droplast =: ([: {: ]) ,~ [: < (([: }: each [ { ])`[`]} [: cols ])
show =: [: ,. [: {&(3 2$'??  []') ([: > def0) + [: +: [: > def1
Чуть более полную версию с комментариями и парой примеров, пригодную к непосредственной загрузке (при помощи выражения load 'имя файла') в интерпретатор J можно скачать здесь.

Как все это работает ? Элементарно (но обьясню, если захотите, позднее). Сначала нужно ввести нонограмму в сессию интерпретатора J (имеет смысл набирать нонограммы в отдельном текстовом файле и загружать его в интерпретатор командой load 'имя файла'):
nWikipediaVERT =: 5 5; 3 5 3; 2 9 2; 1 2 1 2 1; 1 11 1; 4 1 4
nWikipediaVERT =: nWikipediaVERT, 4 1 4; 13; 6 6;13; 1 2 2 1
nWikipediaVERT =: nWikipediaVERT, 1 11 1; 2 9 2; 3 5 3; 5 5
nWikipediaHORI =: 5 5; 3 5 3; 2 9 2; 1 11 1; 1 1 6 2 1; 2 1 3 3
nWikipediaHORI =: nWikipediaHORI, 2 1 3 3; 7 1 3; 2 1 3 3; 2 1 3 3
nWikipediaHORI =: nWikipediaHORI, 1 1 6 2 1; 1 11 1; 2 9 2; 3 5 3; 5 5
nWikipedia =: nWikipediaHORI ; <nWikipediaVERT
Здесь вводятся числа сначала по вертикали (группы разделяются символом ';', числа пробелом ), потом по горизонтали, а потом сшиваются вместе под именем nWikipedia. Это существительное является полным описанием решаемой нонограммы. Решается она теперь командой:
show iterate va nWikipedia
где va строит все множество возможных состояний нонограммы, iterate итеративно выбрасывает из него конфликтующие версии строк и столбцов, а show показывает результат. После нажатия <enter> интерпретатор выдаст:
   show iterate va nWikipedia
[][][][][]          [][][][][]
[][][]    [][][][][]    [][][]
[][]  [][][][][][][][][]  [][]
[]  [][]      []      [][]  []
[]  [][][][][][][][][][][]  []
  [][][][]    []    [][][][]
  [][][][]    []    [][][][]
  [][][][][][][][][][][][][]
  [][][][][][]  [][][][][][]
  [][][][][][][][][][][][][]
[]  [][]              [][]  []
[]  [][][][][][][][][][][]  []
[][]  [][][][][][][][][]  [][]
[][][]    [][][][][]    [][][]
[][][][][]          [][][][][]
Можете проверить !

Но все так легко работает только в случае наличия у нонограммы одного единственного решения. Некоторые нонограммы имеют несколько решений (иногда их авторы об этом не догадываются) и тогда итеративный процесс завершается не сходясь к единственному варианту.

Рассмотрим, например, нонограмму Say Cheese !. Она даже меньше только что решенной, и вводится в компьютер так:
SayCheeseVERT =: 6; 2 2; 2 2; 1 2 2 1; 1 1; 1 1 1 1; 1 4 1; 2 2 2; 2 2; 6
nSayCheeseHORI =: 6; 2 2; 2 1 1 2; 1 1 1 1; 1 2 1; 1 2 1; 1 1 1 1; 2 1 1 2; 2 2; 6
nSayCheese =: nSayCheeseHORI ; <nSayCheeseVERT
но если мы попытаемся ее решить -- процесс не сойдется сразу:
   show iterate va nSayCheese
    [][][][][][]
  [][]        [][]
[][]            [][]
[]  [][]    [][]  []
[]                []
[]  ????????????  []
[]  ????[][]????  []
[][]  ????????  [][]
  [][]        [][]
    [][][][][][]
Глагол show здесь показывает неразрешенные квадратики знаками вопроса. Посмотрим теперь -- сколько вариантов осталось для строк и столбцов
counts iterate va nSayCheese
+-------------------+--------------------+
|1 1 2 3 2 2 3 2 1 1|1 1 1 1 1 10 3 3 1 1|
+-------------------+--------------------+
как видим -- больше одного варианта, тоесть итерация не сошлась к единственному решению. Для "подталкивания" ее я определил глагол droplast, который просто выбрасывает последний вариант из заданного столбца:
counts 2&droplast iterate va nSayCheese
+-------------------+--------------------+
|1 1 1 3 2 2 3 2 1 1|1 1 1 1 1 10 3 3 1 1|
+-------------------+--------------------+
   show iterate 2&droplast iterate va nSayCheese
    [][][][][][]
  [][]        [][]
[][]            [][]
[]  [][]    [][]  []
[]                []
[]  []    ??  ??  []
[]    ??[][][]??  []
[][]  ??[]??    [][]
  [][]        [][]
    [][][][][][]
Здесь был выброшен вариант из столбца 2(нумерация с нуля), и сделана повторная попытка разрешить конфликты глаголом iterate. Но все равно сходимости нет... Выбросим-ка, теперь симметричный вариант из столбца 7 !
show iterate 7&droplast iterate 2&droplast iterate va nSayCheese
    [][][][][][]
  [][]        [][]
[][]            [][]
[]  [][]    [][]  []
[]                []
[]  []        []  []
[]    [][][][]    []
[][]    [][]    [][]
  [][]        [][]
    [][][][][][]
И вот ! Нонограмма решена !! Действительно, казалось бы улыбка (вспомним, что называется она "Say Cheese !", да и файл в котором она представлена называется "smile.html"). Но что будет, если бы мы выбросили другие варианты ? Оказывается, эта нонограмма имеет и другие решения. Например, если вместо варианта в 7-м столбце выбросить вариант из 5-го получим:
   show iterate 5&droplast iterate 2&droplast iterate va nSayCheese
    [][][][][][]
  [][]        [][]
[][]            [][]
[]  [][]    [][]  []
[]                []
[]  []    []      []
[]      [][][][]  []
[][]  [][]      [][]
  [][]        [][]
    [][][][][][]
Вот так улыбочка ! Гуинплена... А по цифрам сходится. Проверьте ! И автору этой нонограммы тоже не помешало бы проверить...

[1] N. Ueda and T. Nagao, "NP-completeness Results for Nonogram via Parsimonious Reductions".

fine print: программа, приведенная здесь хранит все возможные варианты головоломки в памяти (это удобно для организации интерфейса). Но, поскольку задача NP полная, число вариантов быстро растет. Поэтому, в данном случае ограничивающим фактором для размера нонограммы, которую этой программой можно рассмотреть, является размер оперативной памяти компьютера. Если бы программа была написана так, что вместо сохранения всех вариантов она перегенерировала бы их каждый раз заново -- то на типичной персоналке (поскольку в ней "больше" процессора, чем памяти) можно было бы решать и бОльшие нонограммы (за счет того, что время ожидания пользователя не так жестко ограничего как память компьютера). Такую программу тоже можно написать на J, и она будет не намного длиннее.
Tags: j
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments