Японские сканворды

[Yvlad]

Здравствуйте!
Кто ни-будь делал программу для решения японсих сканвордов?

[Роман-вб]

Yvlad
А что?

[Oxygen]

А что конкретно требуется? Если рассматривать само исполнение - то там не так все и сложно. Конкретно для японских сканвордов - нет, а подобные задачи решала когда-то. Кстати, вопрос несколько не по этому разделу форума.

[tyomitch]

http://algolist.manual.ru/misc/japancross.php

[uhm]

Статью с алголиста что-то второй раз пытаюсь прочесть и ниасиливаю.

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

А так - идея была простая. Последовательно идти по строкам и столбцам, заполняя те клетки, которые не могут быть не заполнены. Проходить так много раз, пока не решим кроссворд полностью или не упремся в ситуацию, когда за один полный цикл поле не изменилось.

[Yvlad]

Спасибо за отклик!
Как определить, что в клетке "точно есть" или "точно нет" в разных ситуациях в линиях разными функциями - это я могу. Но это не есть хорошо, а универсальной функции у меня придумать не получается. Статью http://algolist.manual.ru/misc/japancross.php то же понять не могу. И в коде, кажется, есть ошибки.

[uhm]

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

На всякий случай, поясню, какой алгоритм использовал я: берешь строчку или столбец, смотришь все комбинации клеток, не противоречащие уже существующей на поле ситуации и соответствующие цифрам в этой строке. Если в результате во всех этих комбинациях какая-то клетка закрашена или не закрашена, отмечаем ее.

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