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

Category:

нонограммы II

О нонограммах мы говорили здесь почти 6 лет назад. Но, раз в нашем распоряжении теперь квантовый компьютер, здесь и сейчас ;-), то самое время к ним вернуться.

С тех пор по нонограммам появилось множество хороших ресурсов. Мне, например, больше всего понравился этот, но в Google можно найти и еще. Jan Wolter, в прошлом профессор Computer Science at Texas A&M University*, написал свой замечательный обзор различных автоматических решалок нонограмм. На этом поле моя старая программа на J может соревноваться разве что в лаконичности кода. Но теперь то, раз у нас "здесь и сейчас" квантовый компьютер -- возможно очень многое. Например, мы можем в два... Нет, в три счета, написать простую бесхитростную решалку нонограмм. Вычислив, на счет раз, композиции целого числа; на счет два, соответствующие этим композициям все возможные варианты столбцов/строк нонограммы; и, на счет три, просто перемножив логически bdd, соответствующие логическим суммам вариантов каждого столбца/строки (или, как это еще называется -- коньюктивную нормальную форму) при том, что все квадратики на поле мы зададим q-битами (тоесть переменными bdd), которые принимают как бы сразу оба значения и "истина" и "ложь". Результирующая bdd будет содержать все решения нонограммы (см. последнюю программу).

Эта программа оказывается вполне конкурентоспособной. Например, на известном, сложном для всех остальных решалок примере n-Dom, который обсуждается Wolter-ом в отдельной статье она ведет себя лучше всех других:
где ей соответствует синяя кривая "bdd" (после поправки, рассчитанной по разнице SpecINT между процессорами AMD X4 810 и моим Intel Q9300), а все остальные точки взяты из цитированной выше статье Wolter-а.

Все эти мои файлы (вместе с Makefile) можно скачать также и одним архивом, который в добавок содержит программу nonogrambdd5.cpp для решения n-Dom различных размеров, использованную для построения графика выше; и программу nonogrambdd5.cpp, иллюстрирующую сложный (но не невозможный) для данной решалки случай, который наверняка можно улучшить добавив немного эвристики.

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

*Jan Wolter знаменит, кроме всего прочего, еще и цитатой: "It's important to remember that just because there are crooks, zealots and morons supporting a position, it does not automatically follow that the position is wrong." ;-)
Tags: popul
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.
  • 9 comments