Re: Тетрис, японские кроссворды.

From

akrivosheev@utc.ru ()

To

Sergey Turikov

Date

2002-07-25T07:59:21Z

Area

RU.ALGORITHMS

From: akrivosheev@utc.ru

>  А в алгоритме решения японских кроссвордов, я так понимаю, плотно используются
> понятия дискретной математики. Сам я что то пока не догоняю(нахожусь в
> отношении "чайник" с дис.мат.), поэтому интересуют изыскания и достижения более
> продвинутых в данной области людей.

Я видел два пути решения японских кроссвордов:

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

2. Перебор.
Очень долго, но все варианты находятся, если есть ошибка при составлении то может
найти, и по крайней выдаст почти решеный кроссворд даже при наличии ошибки.
  1. Подсчитываются количество вариантов для каждой строки  и столбца
  2. Находятся  клетки которые точно черные и точно белые последовательно перебирая
строки и столбцы.
  3. Пересчитывают количество вариантов и снова п.2 - выход если количество
вариантов не уменьшается.


--- ifmail v.2.15dev5
 * Origin: JV Izhcom Ltd. (2:5020/400)