Вопрос к аналитикам. Написал программку, реализующую алгоритм решения японских кроссвордов. Для каждой строки/столбца кроссворда вызывается рекурсивная функция, которая пытается разместить блоки один за другим во всех допустимых позициях; и так - пока кроссворд не решится . Проблема в следующем: для кроссворда размером 35x30 та рекурсивная функция вызывается больше чем полмиллиона раз. Для кроссворда 55x65 эта цифра уже немного недотягивает до половины миллиарда. Это при том, что при обработке строки или столбца используется таблица для хранения информации о возможности расположения уже проверенных блоков, чтобы не вызывать рекурсию лишний раз. Это конечно намного понизило количество вызовов подпрограммы, но все же мне кажется цифра слишком большая. Косяки искал, уже голова пухнет. А может и нету их? Код и exeшник внизу↓ Если кто будет смотреть - исходный файл называется src.txt. Если нужно решить кроссворд какой - переименовываем его в src.txt. Для примера в архиве есть что-то вроде бинокля и Петр Первый. P.S. Для тех у кого машина не особо сильная сообщаю - кроссворд будет дорешан, когда полоска заполнится до конца строки консольного окна (т.е. 80 символов), т.е. прийдется подождать...
KeSqueer А ты стандартные ситуации вначале не разруливаешь (я имею в виду, когда на основе данных по конкретной строке или столбцу можно однозначно указать местоположение крестиков)? Рекурсия - дело хорошее, но на каждом шагу нужно максимум информации извлекать из ситуации. Блин, почти калламбур.
для строки ширины m, поиск подстроки размера n >= (m/2 + 1) и выделение 2*n - m клеточек упрощают решение японского кроссворда
t00x Я так понимаю, прийдется описать алгоритм. Попробую покороче и попроще (двухцветный кроссворд) Если блок последний, отмечаем на картинке соответствующие клетки как "возможно закрашенная и/или возможно не закрашенная" Если блок не последний: Берем блок и пытаемся разместить его с первой клетки. Критерии его размещения: - если блок первый, левее него не должно быть закрашенных клеток; - на протяжении всего блока не должно быть клеток, состояние которых определено 100% как "пустая"; - следующая клетка правее блока не должна быть закрашенной; - если блок последний, то правее него не должно быть ни одной закрашенной клетки. Если для n-го блока условия выполняются, выполнить поцедуру для следующего блока Увеличиваем начальную позицию n-го блока на 1 и повторяем цикл. Пока не достигнем последней возможной позиции. Когда ее достигаем, в строке получаются клетки с состояниями "точно закрашенная", "точно не закрашенная" и "хз какой ее цвет". Затем берем следующую строку или столбец. Согласен. Такой вариант (когда n>=(m/2+1)) сам собой разруливается с помощью приведенного выше алго. Вот пример: Есть строка с блоками 4, 5 и длиной 12. Поэтапно получаем следующее (перебор вариантов): Код (Text): xxxx.xxxxx.. xxxx..xxxxx. xxxx...xxxxx .xxxx.xxxxx. .xxxx..xxxxx ..xxxx.xxxxx Отсюда заключаем следующее: ,,XX,,,XXX,, Здесь "x"-предположительно закрашенная, "." - предположительно незакрашенная "," - неизвестно (может да, а может нет), "X" - точно закрашенная Если бы, скажем, вторая клетка имела состояние "0" (точно не закрашенная) то вариантов не было бы, и заключение было таковым: 00XXXX0XXXXX Если говорить конкретно про ваш вариант "ищем подстроку длиной больше половины строки и в середине отмечаем несколько клеток", то будет ли это менее "времяемкая" работа? Но во всяком случае этим способом нельзя рассмотреть некоторые случаи. Как в приведенном выше примере. Надеюсь что-то прояснил. А вообще странно, что эта тема не поднималась, ИМХО, довольно интересная. /add t00x хотя, для самого глубокого вызова (для последнего блока), это, возможно, будет лучшим вариантом..
отчего же. ищем строку с самым мощным блоком, например строка с блоками 2, 6 (самый мощный из всего кроссворда) и длиной 10. делаем прямой перебор вариантов размещения блоков: Код (Text): XX.XXXXXX. XX..XXXXXX .XX.XXXXXX на множестве из 3-х элементов "закрашенная"="X", "неизвестно"=",", "незакрашенная"="." имеем: Код (Text): ,,,,XXXXX,
KeSqueer Это можно сделать без всякого перебора. Я, когда разгадываю японские кроссворды (мое хобби, что еще в метро делать ), пользуюсь следующим правилом: пусть комбинация длин в строке (столбце) n1, n2,...,nk, а строка (столбец) имеет длину m. Если n1+n2+...+nk+(k-1)>m, то можно выставить следующую комбинацию: (d=m - (n1+n2+...+nk+k-1)) .........XXXXXX.......XXXXXX..................XXXXXXX........ d n1-d d+1 n2-d d+1 ... d+1 nk-d d
crypto Все так просто, когда это делаешь на бумаге Тоже мое увлечение.. И тоже точно так же и решаю. Но это все работает на изначально пустой линии к примеру встречается такая ситуация: 2 3 4: ....x0........ Как здесь будет? Решение одно единственное, но здесь IMHO недостаточно использовать Один предложенный метод Опять же не скажу, что здесь нельзя добавить что-то такое небольшое, чтобы все работал отлично..
KeSqueer У меня кстати есть одна такая программка (написана моим знакомым на Билдере бог знает когда). Если хочешь, могу бросить.
не одно: Код (Text): XX..x0.,,,X,,, .XX.x0.,,,X,,, и т.д. наверно будет одно, если брать значения из перпендикулярно направленных данных. P.S. всё равно надо начинать с наибольших блоков
t00x Имелось в виду 2 3 4: ....x0........ 2,3 и 4 - размеры блоков, 0 - точно не закрашенная клетка; тогда решение будет: 000хх0ххх0хххх - единственное crypto Намыльте, плиз )
