|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : akrivosheev@utc.ru 2:5020/400 25 Jul 2002 07:59:21
To : Sergey Turikov
Subject : Re: Тетрис, японские кроссворды.
--------------------------------------------------------------------------------
> А в алгоритме решения японских кроссвордов, я так понимаю, плотно
> используются понятия дискретной математики. Сам я что то пока не
> догоняю(нахожусь в отношении "чайник" с дис.мат.), поэтому интересуют
> изыскания и достижения более продвинутых в данной области людей.
Я видел два пути решения японских кроссвордов:
1. Рекурсия
1 зачерним самый правый верхний квадрат. если данный вариант возможен то на
шаг 4
2 стираем и проверяем снова если этот вариант возможен то на шаг 4
3 переходим к предыдущей ячейке
4 зачерним следующюю ячейку
Способ по скорости очень быстрый, но если при составлени кроссворда хоть где-то
ошибка, то не решается обычно, и кроме того находятся не все варианты.
2. Перебор.
Очень долго, но все варианты находятся, если есть ошибка при составлении то
может
найти, и по крайней выдаст почти решеный кроссворд даже при наличии ошибки.
1. Подсчитываются количество вариантов для каждой строки и столбца
2. Hаходятся клетки которые точно черные и точно белые последовательно
перебирая
строки и столбцы.
3. Пересчитывают количество вариантов и снова п.2 - выход если количество
вариантов не уменьшается.
--- ifmail v.2.15dev5
* Origin: JV Izhcom Ltd. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Тетрис, японские кроссворды. 