VII Международная студенческая научная конференция Студенческий научный форум - 2015

Наука дает нам мощные инструменты, в виде различных технологий и методик, для решения тех или иных задач. Общество находится в постоянном развитии, и ему требуются всё новые решения для новых задач. Прогресс также не стоит на месте – старые методы подвергаются улучшениям, либо полностью заменяются новыми, более эффективными. Эти изменения можно хорошо проследить в головоломках. Основные математические методы решения всех головоломок являются методы комбинаторного анализа. В данной работе, приводится методика решения головоломки с определением состояния клеточного поля, а именно – японский кроссворд.

Правила игры

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

Например, набор чисел 4, 1, и 3 в сетке японского кроссворда (рисунок 1) означает, что в этом ряду есть три группы: первая – из четырех, вторая – из одной, третья – из трех черных клеток.

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

.

Рисунок 1 - Японский кроссворд.

Существующие на настоящее время методы решения задачи

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

Рассмотрим один из подходов к математическому решению задачи.

Оценим стоимость полного перебора всех возможных размещений зарисованных клеточек с дальнейшей проверкой соответствия заданному на входе описанию. Например, для простенького кроссворда из 80 клеточек, из них 49 закрашенные, количество размещений C₈₀⁴⁹ = 1.5* 10²³, что для современных ПЭВМ означает время выполнения, приблизительно равное геологическому возрасту Земли. (http://www.thalion.kiev.ua/idx.php/128/665/article/)

Безусловно, значительную пользу может принести использование принципа «отбрасывать не отдельные размещения, а большие совокупности размещений». В частности, можно строить картинку последовательно по строкам: пробуя разместить зарисованные клеточки в первой строке, сразу проверять их на соответствие описанию первой строки, и переходить к попыткам размещение клеточек второй строки лишь тогда, когда найден один из удовлетворительных способов размещения в первой и т.д. Удовлетворительных размещений зарисованных клеточек в отдельной строке может быть много, и (как правило) лишь одно из них приводит к правильно разгаданному кроссворду. То есть, найдя допустимое размещение клеточек во всех строчках, нужно возвратиться к первой строке, попробовать найти другое допустимое размещение клеточек и снова рассмотреть все возможные размещения в следующих строках. То есть, получается алгоритм с возвращениями.

Для каждого из этих вариантов нужно проверить, не противоречит ли он уже известным окончательным состояниям клеточек. Говоря, что вариант размещения противоречит известным окончательным состояниям, мы имеем в виду примерно следующее: если из предшествующего анализа мы знаем, что 5-ая клеточка линии имеет окончательное состояние «не зарисована», то размещать блок длиной 4 в клеточках с 3-ей по 6-ую нельзя, так как это будет противоречить ранее найденному состоянию 5-ой клеточки. То есть, противоречивость варианта размещения блоков с окончательными состояниями появляется или когда пробуем разместить блок поверх гарантированно не зарисованной клеточки, или «симметричным» образом, когда какая-то клеточка имеет окончательное состояние «зарисованная» и оказывается в промежутке между блоками.

Реализация рекурсионной функции на языке Pascal (ссылка на статью выше):

function TryBlock(theblock,thestart:shortint):boolean;

var i,startnext:shortint;

res:boolean;

Begin

for i:=thestart to thestart+bl_len[theblock]-1 do

if cells[i]=0 then begin TryBlock:=false; exit end;

if theblock

res:=false;

for startnext:=thestart+bl_len[theblock]+1 to

L-bl_len[theblock+1]+1 do begin

if cells[startnext-1]=1 then break;

if TryBlock(theblock+1,startnext) then begin

res:=true;

(*какое-то непротиворечивое размещение дальнейших блоков существует*)

end;

end;

TryBlock:=res

end else begin (* theblock = N *)

for i:=thestart+bl_len[theblock] to L do

if cells[i]=1 then begin TryBlock:=false; exit end;

(*данное размещение последнего блока непротиворечиво*)

TryBlock:=true

end

End;

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

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

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

Поэтому, мной разработан более простой алгоритм, основанный на переборе групп закрашенных клеток каждой строки.

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

К примеру, возьмем одну строку, ключ которой (здесь и далее, ключ – подсказки для данной строки (или столбца)) равен: 132. Количество столбцов равно девяти.

132 □□□□□□□□□

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

1: ■□

3: ■■■□

2: ■■

Общая сумма клеток, занимаемая всеми тремя группами, в соответствии с ключом равна: 2+4+2=8

А так как столбцов девять, то остается одна не заполненная клетка. Исходя из всего этого, можно понять, что всего комбинируемых групп 4 (3 группы известных клеток, и одна неизвестная), но при этом, первые три группы должны всегда оставаться в одинаковом положении относительно другу друга, чтобы не противоречить ключу.

Общее число перестановок 4 по 4 (т.е. полный перебор) равен 4! = 24.

Сразу откинем все, что противоречат взаимному расположению известных групп, и количество возможных расположений групп клеток, в соответствии с ключом, будет равно 4 (1320,1032,0132,1302).

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

Далее, когда клетки расставлены по местам в соответствии с их левыми ключами, начинаем проверять их на соответствие верхним ключам.

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

Код для цитирования: Скопировать