создание и заполнение массива в java

Можно считать, без ограничения общности, что мы работаем со строкой и ее кодом.

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

Четвертый алгоритм.

Для каждой строки и каждого столбца строятся всевозможные непротиворечивые (по отношению к уже известным клеткам) расположения блоков и клетки, которые при всех расположениях остаются закрашенными(незакрашенными), отмечаются на поле соответствующей цифрой. Если ни одного расположения не существует- значит кроссворд имеет противоречие.

Третий алгоритм я нашел на следующем . Исходники на паскале так же можно найти на этом же .

Третий алгоритм.

Следующие алгоритмы уже не являются алгоритмами перебора, но существуют кроссворды которые невозможно решить не используя перебор и кроссворды с огромным количеством решений (например кроссворд NxN, каждая строка и каждый столбец которого состоит из 1 блока единичной длины, имеет N! решений). В конце концов для каждого из таких кроссвордов приходится запускать перебор.

Один из худших вариантов- когда все коды строк равны «1, 0» (тоесть 1 блок из 1 клетки). Количество вариантов размещения таких блоков равно M^N.

Второй алгоритм представляет из себя более умный, но все же, перебор. Теперь поле заполняется не отдельными единицами, а целыми блоками. Берутся строки и заполняются блоками, длины и порядок которых берутся из соответствующих кодов. Затем для каждого столбца проверяется соответствие своему коду.

Второй алгоритм.

Работает достаточно быстро лишь на маленьких кроссвордах (Для кроссворда 14х11 время решения составляет уже 1 минуту)

Несложно посчитать количество вариантов такого заполнения. Их ровно 2^(N*M).

Первым, что я написал, был алгоритм перебора. Поле NxM заполняется 1 и 0. И для каждой строки и каждого столбца проверяется соответствие коду.

Первый алгоритм.

Вторая хранит N кодов строк и M кодов столбцов, заканчивающихся нулем.

Японский кроссворд представляется в памяти в виде двух матриц. Первая размера NxM хранит поле. Закрашенная клетка обозначается 1(один), незакрашенная 0(ноль), неизвестная -1(минус один).

Для тех кто не знает что такое японский кроссворд- .

Недавно мне выпала следующая задача: написать программу, находящую все решения или их отсутствие для данного японского кроссворда размера NxM. Далее представлены 4 алгоритма решения японских кроссвордов.

Японские кроссворды и алгоритмы их решения

Японские кроссворды и алгоритмы их решения / Хабрахабр