Здравствуйте, Jeka_B, Вы писали:
J_B>Здравствуйте. Интересует алгоритм проверки на наличие ошибки в частично заполненном столбце (или строке) японского кроссворда.
J_B>Может кто-то знает, как решается такая проблема, может привести пример кода или сказать, где такое можно найти.
Если я вас правильно понял, то мы рассматриваем именно строку (или столбец) в изоляции и пытаемся проверить, можно ли докрасить ее так, чтобы выполнялись условия на соответствующую строку (или столбец). При этом если так докрасить можем, то хотим определить, к каким числам относятся уже закрашенные клетки.
В этом слуае я могу даже пример кода дать
В архиве код, можно посмотеть, как работает одна из решалок — src/ru/maxkar/puzzle/solver/LineHeuristicSolver.java. Она делает не совсем то (строит решение), но после небольшой доработки она будет отвечать на ваши вопросы.
Сразу предупреждаю — когда будете читать, обратите внимание, что у клетки не 2, а 3 состояния (Определенно заполнена (FILLED), определенно не заполнена (EMPTY) и не определено (UNKNOWN)), иначе путаница будет.
Вкратце алгоритм:
Определение: "Полоска" — непрерывная последовательность закрашенных клеток, т.е. то, что соответствует одному числу из описания задачи.
Определяем, в каких клетках может начинаться полоска определенной длины (для всех длин "полосок" из условия). Условия простые — в полоску не должны попадать "определенно пустые" клетки, по краям должна быть возможность иметь пустые клетки (т.е. те, которые еще не являются определенно заполненными).
Для каждой клетки определяем, может ли в этой клетке начинаться i-я полоска и при этом будет существовать хоть какая-нибудь корректная раскраска правой части строки. Вычисляем это начиная с самой правой полоски. Условия — в указанной клетке должна быть возможность начать нашу (i-ю) полоску (см. предыдущий пункт), при этом где-нибудь справа должна существовать возможность начать (i+1)-ю полоску (что автоматически даст и раскраску для i+k, k=2,3,... полосок по построению). Тонкость, которую нужно учесть — между i и i+1 полосками не может быть "определенно заполненных" клеток, иначе это явное нарушение правил.
Всевозможные "суффиксы" мы "построили". Теперь будем строить префиксы а заодно решения. Сами по себе префиксы по сути строятся точно так же, как и суффиксы. Зная префиксы и суффиксы мы можем определить, что i-я полоска может начинаться с клетки j в каком-нибудь, если она там может начинаться в префиксах и суффиксах одновременно — очевидно, такие перфикс + суффикс дадут одно из решений. Точно так же, если есть решение, где i-я полоска может начинаться с клетки j, то в префиксах и суффиксах она может начинаться в той же клетке (если мы, конечно, не ошиблись при построении суффиксов). В коде не строятся отдельно префиксы, строится сразу объединение.
В вашем случае (в коде нет, он правильность не проверяет) — если нет возможной позиции для самой левой полоски, то значит что-то заведомо заполнено неправильно (т.е. не получится заполнить строку так, чтобы условия выполнялись). Что именно не правильно оно не скажет, и я боюсь, что в сложных случаях какой-нибудь простой нарушаемой "эвристикой" обойтись не получится, придется использовать разбор различных вариантов.
Для каждой клетки строки вычисляем, к какой полоске она может относится. Здесь все просто.
В коде (вам не нужно) вычисляется, какие клетки могут быть пустыми. Решалке это нужно, чтобы определить, что клетка уже не может быть пустой (вне зависимости от того, определили ли мы, к какому числу из условия оно относится) и на итерациях "по столбцам" использовать это знание.
Ну и финал — применение всех полученных ранее знаний. Помечаются заведомо пустые и заполненные клетки. Для заведомо заполненных клеток определяется, к какой именно полоске из условия относятся клетки (если это вообще возможно определить однозначно). Причем это работает по всем клеткам, в том числе тем, которые уже были заполнены заранее.
Ну и можно определить, какие числа из условия заполнены полностью. Там все делается вообще элементарно — по количеству клеток, которые заведомо отнесены к каждой полоске. Код тоже есть, рядом — DumbResolvedLineMarker.java
Если интересно — могу написать и выложить более формальные доказательства, с определениями объектов (полоски и т.п.), выводами и т.п. Хотя ничего принципиально нового по сравнению с приведенным выше там уже не будет.
