@Zuzik

Сразу к делу - для тех кто не знает что такое ЯК - википедия http://ru.wikipedia.org/wiki/%... 1%80%D0%B4 . Далее - появилась идея составить программу для решения ЯК. На бумаге решать их умею, но тем не менее составить алгоритм для программы у меня не получается. Элементарно ничего не приходит в голову. Если ли у кого какие либо идеи? Приветствуются любые ответы.

Добавлено через 3 минуты
П.С. статейку на хабре нашел, почитаю. Все равно жду ваших советов.

0

@wingblack

Для потомков нужно оставлять ссылки
Японские кроссворды и алгоритмы их решения
Решение японских кроссвордов на Haskell

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

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

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

Ну примерно так. Скорее всего, моё изложение алгоритма немного сумбурно. В рамках данного алгоритма мне не удалось вставить следующие используемые рассуждения:
- поиск перекрытия крайних положений описывается возможным "люфтом" блоков.
- перекрытием положений является вычислимым, так если длинна группы больше чем величина люфта, то мы гарантированно знаем какие квадраты можно зачернить. Величина люфта вычисляется из выражения
люфт = (количество не заблокированных клеток) - (сумма длин групп) - (число групп - 1)
Тогда количество закрашиваемых клеток = длинна группы - люфт. Эти клетки находятся в хвосте данной группы в крайнем положении. Учесть что хвост правый или левый, в зависимости от того какое крайнее положение используется.
Вообще-то этот метод однозначно работает для начала кроссворда и для строк без учета внутренних заблокированных (белых) клеток, т.е. учитываются только белые клетки по краям строки.
- область между двумя белыми(заблокированными) клетками можно тоже закрасить белым (заблокировать) если нет групп которые не больше чем эта область или оба крайних положения групп влезающих в такую область находятся дальше такой области
Т.е. в (не важно каком) крайнем положении выполняется неравенство: (люфт) меньше чем (координата начала группы) - (координата начала области)
Замечу что утверждения "в конце группы", "дальше" и "координаты начала" делаются с учетом что виртуальная ось координат для каждого из крайних положений направлена в разные стороны и имеет начало с разных сторон строки.

Воплощать решение в коде мне не приходилось, в противном случае описание алгоритма было бы более структурированным.

1

@m-ch

Реализовывал алгоритм решения ЯК на VBA: https://www.cyberforum.ru/post7385736.html
Код открытый, можно разобраться

0