Автор Тема: Алгоритм решения Японского кроссворда  (Прочитано 26773 раз)

0 Пользователей и 1 Гость просматривают эту тему.

GOGA

  • Гость
Всем привет. Пишу программу на VB6 по составлению и разгадыванию японского кросворда. Первая часть, т.е. составление самого кроссворда уже готова. Нужен алгоритм вычисления для решения Японского кроссворда. Кто знает помогите.

Оффлайн Фокусник

  • Светлый
  • Надворный советник
  • *****
  • Сообщений: 477
  • Репутация: 1
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #1 : јРЩ 09, 2005, 09:02:14 am »
Что такое Японский кроссворд?
Время не имеет значения, важна только жизнь

Оффлайн melkiy

  • Глобальный модератор
  • Действительный статский советник
  • *****
  • Сообщений: 1124
  • Репутация: 24
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #2 : јРЩ 09, 2005, 05:56:37 pm »
GOGA, а ты собираешься отслеживать однозначность решения? Я, хоть и недолго ими увлекался, но успел в газете "Крот" наткнуться на такой кроссворд, где решение в малой области было неоднозначно. Дорисовал по эстетическим соображениям, ясно. я ж не комп. Но осадок остался...
... Есть пауки, которые плетут ловчие сети, и есть пауки-бродяги. В любом случае они хЫщники.

Оффлайн Leopotam

  • Темный свихнувшийся даритель банов, а так же
  • Администратор
  • Тайный советник
  • *****
  • Сообщений: 2119
  • Репутация: 16
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #3 : јРЩ 09, 2005, 06:11:45 pm »
Фокусник, рисуется черно-белая картинка определенного размера. Затем для каждого ряда считаются количество идущих подряд точек (без разрывов пустыми точками), записываются. То же самое повторяется и для столбцов. Решающему кроссворд выдаются только эти числа, по которым он и должен восстановить исхлдное изображение.

Как особо извращенный вариант есть еще разноцветные японские кроссворды.

melkiy, количество вариантов не такое уж и большое, это ведь все-таки ЭВМ, а не человек - пусть потрудится. ;)
Всех убью, один останусь...

PantiL

  • Гость
Re: Алгоритм решения Японского кроссворда
« Ответ #4 : јРЩ 09, 2005, 11:00:15 pm »
Я както тоже пытался решить эту задачку - неудача. Искал по инету алгоритмы, но ничего конкретного не нашел. Увидел только такое утверждение, что если пытаться сделать перебором, то будет очень долго и врядли дождешься окончания. Надо придумывать "умный" алгоритм

Оффлайн Leopotam

  • Темный свихнувшийся даритель банов, а так же
  • Администратор
  • Тайный советник
  • *****
  • Сообщений: 2119
  • Репутация: 16
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #5 : јРЩ 09, 2005, 11:17:48 pm »
Там рекурсия жуткая получается, а так вроде ничего...
Всех убью, один останусь...

Оффлайн LEON

  • Действительный статский советник
  • *****
  • Сообщений: 1557
  • Репутация: 0
  • Пол: Мужской
  • Котята Геринга
Re: Алгоритм решения Японского кроссворда
« Ответ #6 : јРЩ 09, 2005, 11:31:42 pm »
Есть у меня алгоритм, в голове правда и на бумажке, завтра руки дойдут напишу.

Про жуткии рекурсии прошу не выражаться, за последние пол года, я ее полюбил, если кто то еще не умеет правильно юзать рекурсию, то могу несколько статей скинуть.
Йа помню что дал мальчугану конфету в которой в начинке был кал...

Оффлайн Leopotam

  • Темный свихнувшийся даритель банов, а так же
  • Администратор
  • Тайный советник
  • *****
  • Сообщений: 2119
  • Репутация: 16
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #7 : јРЩ 09, 2005, 11:41:43 pm »
LEON, ну-ну... :) :) :)
У меня тоже был прототип - и без рекурсии с обходом вариантов я, честно говоря, не представляю себе решения. А почему жуткая, так это из-за потенциальной опасности обрушить стек - для примера возьми картинку размером 4096 на 4096... :) :) :)
Всех убью, один останусь...

Оффлайн LEON

  • Действительный статский советник
  • *****
  • Сообщений: 1557
  • Репутация: 0
  • Пол: Мужской
  • Котята Геринга
Re: Алгоритм решения Японского кроссворда
« Ответ #8 : јРЩ 09, 2005, 11:47:10 pm »
Столько учился, а рекурсию плохо знаешь )))
Ай ай ай )))
Алгоритм рекурсивный, это верно, завтра напишу, обсудим ))
Йа помню что дал мальчугану конфету в которой в начинке был кал...

GOGA

  • Гость
Re: Алгоритм решения Японского кроссворда
« Ответ #9 : јРЩ 11, 2005, 12:59:08 pm »
Не помню я не про какую рекурсию, наверное и не изучал ни когда, так что прошу разъяснить мне что это за штука и как её применить для решения Японского кроссворда?

Оффлайн Leopotam

  • Темный свихнувшийся даритель банов, а так же
  • Администратор
  • Тайный советник
  • *****
  • Сообщений: 2119
  • Репутация: 16
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #10 : јРЩ 11, 2005, 04:32:07 pm »
Гы-гы-гы! "завтра напишу" от 9 числа... :) :) :) Значит не все так просто у LEON-а...
Цитата: GOGA
прошу разъяснить мне что это за штука
В данном контексте это вызов функции из себя самой, т.е. есть какая-то функция (ставящая точку и определяющая корректность установки), внутри которой происходит вызов этой же функции на основании данных, полученных в результате наружного вызова. Звучит дико, но иногда очень полезно. Проблема в том, что нужно где-то сохранять предыдущее состояние переменных (хотя бы точки вызова) перед каждым вложенным вызовом, а на большой картинке это весьма чревато.
А вообще, не парься, вот, почитай на досуге: http://algolist.manual.ru/misc/japancross.php
Всех убью, один останусь...

Оффлайн LEON

  • Действительный статский советник
  • *****
  • Сообщений: 1557
  • Репутация: 0
  • Пол: Мужской
  • Котята Геринга
Re: Алгоритм решения Японского кроссворда
« Ответ #11 : јРЩ 11, 2005, 08:33:50 pm »
Все  просто )) Проще простого, просто времение нет и руки не доходят ))
Йа помню что дал мальчугану конфету в которой в начинке был кал...

GOGA

  • Гость
Re: Алгоритм решения Японского кроссворда
« Ответ #12 : јРЩ 13, 2005, 05:10:06 am »
Раз все так просто, жду решения.
Leopotam'у, спасибо за ссылку.

xbir

  • Гость
Re: Алгоритм решения Японского кроссворда
« Ответ #13 : јРав 30, 2007, 02:53:08 pm »
Тема видимо закрыта?

Оффлайн Robert

  • Коллежский регистратор
  • *
  • Сообщений: 1
  • Репутация: 0
  • Пол: Мужской
  • SkypeID: programmist-robert
Re: Алгоритм решения Японского кроссворда
« Ответ #14 : °ЯаХЫм 08, 2008, 04:23:12 pm »
Я программист, Роберт.
(Программа составлена на языке паскаль)!
Я составил алгоритм  и  программау, для решения японских кроссворда на компьютере!
Я составляю Программы,решение  на компьютере,
не имеющих  стандартного  алгоритма!
Я программист, Роберт.
(Программа составлена на языке паскаль)!
Я составил алгоритм  и  программау, для решения японских кроссворда на компьютере!
Я составляю Программы,решение  на компьютере,
не имеющих  стандартного  алгоритма!

Оффлайн Samael

  • Шпийон Сарумяна
  • Вице-канцлер
  • *****
  • Сообщений: 3543
  • Репутация: 70
  • Пол: Мужской
  • Гик - это не профессия, гик - это призвание...
  • SkypeID: kornev.vladimir
Re: Алгоритм решения Японского кроссворда
« Ответ #15 : °ЯаХЫм 08, 2008, 07:05:05 pm »
Я Дед Мороз, развозчик подарков.
(Подарок сделан в Одессе)!
Я придумал совершенно новый подарок, который включает в себя новый букварь и словарь по русскому языку.
Я нанял гномов, которые написали и распечатали эти подарки на ручных печатных станках, не имеющих аналогов в мире.
Один терапевт - это 1024 гигапевта, или 1048576 мегапевтов.
Все вышесказанное - исключительно IMHO :Samael:
Если Вам кто-то помог, нажмите

Оффлайн #535

  • Действительный статский советник
  • *****
  • Сообщений: 1794
  • Репутация: 38
  • Пол: Мужской
  • Make scene,not war!
Re: Алгоритм решения Японского кроссворда
« Ответ #16 : °ЯаХЫм 08, 2008, 07:29:19 pm »
Что это было? o_O


Оффлайн gigauser

  • Статский советник
  • *****
  • Сообщений: 976
  • Репутация: 20
  • Banned
Re: Алгоритм решения Японского кроссворда
« Ответ #17 : °ЯаХЫм 08, 2008, 10:23:48 pm »
Я программист, Роберт.
(Программа составлена на языке паскаль)!
Я составил алгоритм  и  программау, для решения японских кроссворда на компьютере!
Я составляю Программы,решение  на компьютере,
не имеющих  стандартного  алгоритма!
ты прикалываешься?
в олимпиадных задачах встречал нечто подобное, но командой так и не придумали ничего кроме тупого перебора.
2 Sam, жжешь+1
« Последнее редактирование: °ЯаХЫм 08, 2008, 10:26:18 pm от gigauser »
Banned

Оффлайн VladiMirdn

  • Коллежский регистратор
  • *
  • Сообщений: 1
  • Репутация: 0
  • Пол: Мужской
  • SkypeID: VladiMirdn
Re: Алгоритм решения Японского кроссворда
« Ответ #18 : °ТУгбв 03, 2008, 02:43:01 am »
Нужен алгоритм вычисления для решения Японского кроссворда. Кто знает помогите.
  Здравия желаю!
 Был приятно удивлен количеством интересующихся Японскими кроссвордами. Судя по дате, товарищ уже должен был составить алгоритм. Только ПК - это всего лишь перебор вариантов. Компьютер будет проводить анализ строк, столбцов последовательно. А весь смак решения японских кроссвордов в нахождении оптимального пути решения. Отыскать ключик, найти, как говорится, критическую точку. Это я говорю как автор книги "Японские кроссворды. Стань профессионалом. Советы мастера."   Наверняка, если бы товарищ прочел эту книгу, то не стал бы здесь просить помощи. И "сделал" бы всех японцев. Чего я и вам всем желаю!
« Последнее редактирование: °ТУгбв 03, 2008, 02:45:35 am от VladiMirdn »
"Ракетчик" - звучит гордо!

Оффлайн CooLeRa

  • Коллежский регистратор
  • *
  • Сообщений: 4
  • Репутация: 0
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #19 : °ТУгбв 03, 2008, 06:50:36 am »
Что такое Японский кроссворд?
Чувак! Ты счастливчик, раз не знаешь, что такое японский кроссворд!!! Завидую...  :good:
Вся жизнь - х@йня, все бабы - стервы, а солнце - @баный фонарь. Остановите землю, я сойду...

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #20 : °ТУгбв 30, 2008, 09:25:41 am »
А весь смак решения японских кроссвордов в нахождении оптимального пути решения.

0.3 секунды на решение кросворда 70*70 куда смакованей и куда оптимальней.

Только ПК - это всего лишь перебор вариантов.

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

Оффлайн Samael

  • Шпийон Сарумяна
  • Вице-канцлер
  • *****
  • Сообщений: 3543
  • Репутация: 70
  • Пол: Мужской
  • Гик - это не профессия, гик - это призвание...
  • SkypeID: kornev.vladimir
Re: Алгоритм решения Японского кроссворда
« Ответ #21 : БХЭвпСам 18, 2008, 06:37:31 pm »
Алгоритм, я так понимаю, держите в секрете?
Один терапевт - это 1024 гигапевта, или 1048576 мегапевтов.
Все вышесказанное - исключительно IMHO :Samael:
Если Вам кто-то помог, нажмите

Оффлайн gigauser

  • Статский советник
  • *****
  • Сообщений: 976
  • Репутация: 20
  • Banned
Re: Алгоритм решения Японского кроссворда
« Ответ #22 : БХЭвпСам 18, 2008, 07:10:46 pm »
Сем, у zhekas'а 2 поста, где он всех обосрал и смылся, вот второй*ЛОЛ*
(типа я знаю, но ничего не скажу)
Banned

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #23 : БХЭвпСам 19, 2008, 01:22:00 am »
Да бе
Алгоритм, я так понимаю, держите в секрете?
Да без проблем. Скажите куда. Я скину исходник или исполняемый файл (как вам угодно) на фрипаскале(freepascal) и примеры.
Сем, у zhekas'а 2 поста, где он всех обосрал и смылся, вот второй*ЛОЛ*
(типа я знаю, но ничего не скажу)

В теме на которую вы указали было все коректно. Я даже предложил вариант решения.
Без грубостей. В данной теме немного повысил тон(но не обосрал) из-за самоуверенности предыдущего оратора.
« Последнее редактирование: БХЭвпСам 19, 2008, 01:32:44 am от zhekas »

Оффлайн Samael

  • Шпийон Сарумяна
  • Вице-канцлер
  • *****
  • Сообщений: 3543
  • Репутация: 70
  • Пол: Мужской
  • Гик - это не профессия, гик - это призвание...
  • SkypeID: kornev.vladimir
Re: Алгоритм решения Японского кроссворда
« Ответ #24 : БХЭвпСам 19, 2008, 09:50:12 am »
zhekas, с радостью посмотрю и исходники и ехе-ку (т.к. компилятора нет, но паскаль читаю =) ). Если можно, то киньте на мыло evil_not_dead {at} list.ru
Один терапевт - это 1024 гигапевта, или 1048576 мегапевтов.
Все вышесказанное - исключительно IMHO :Samael:
Если Вам кто-то помог, нажмите

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #25 : БХЭвпСам 19, 2008, 01:28:11 pm »
Отправил.

Оффлайн melkiy

  • Глобальный модератор
  • Действительный статский советник
  • *****
  • Сообщений: 1124
  • Репутация: 24
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #26 : БХЭвпСам 19, 2008, 08:33:38 pm »
и ещё мне, если можно  :)
strider {at} land.ru
... Есть пауки, которые плетут ловчие сети, и есть пауки-бродяги. В любом случае они хЫщники.

Оффлайн nauk

  • Коллежский регистратор
  • *
  • Сообщений: 1
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #27 : ѕЪвпСам 30, 2008, 07:06:52 pm »
Mr.zhekas. Очень интересно! Прошу скинте мне плиз! :)
nauk@fromru.com
« Последнее редактирование: ѕЪвпСам 30, 2008, 07:11:01 pm от nauk »

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #28 : ѕЪвпСам 30, 2008, 09:00:34 pm »
Так как предполагаю, что на ваш e-mail мое письмо не дошло. Выкладываю арххив с файлами сюда. В архиве содержатся: исходник japan722.pas, исполняемый файл japan722.exe и примеры в виде текстовых файлов, которые(примеры) находятся в папке japex.

Перед запуском japan722.exe убедитесь, чтоб в той же дирректории находилась папка japex. В программе нужно вводить только имя файла (без пути).

В исходнике нет ни одного коментария. Так что желаю удачи в изучении алгоритма.
« Последнее редактирование: ѕЪвпСам 31, 2008, 03:16:38 pm от zhekas »

Оффлайн jx

  • Глобальный модератор
  • Коллежский асессор
  • *****
  • Сообщений: 291
  • Репутация: 16
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #29 : ѕЪвпСам 31, 2008, 02:16:59 pm »
тут вирус!
но вылечился каспером

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #30 : ѕЪвпСам 31, 2008, 03:17:46 pm »
Щас перекомпилировал exe-ку. Выложил другой архив. Может лучше будет

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #31 : јРЩ 14, 2009, 10:52:37 pm »
Собственно вот моя программа, решающая Японские кроссворды на C++ https://sourceforge.net/projects/jsolver/

Оффлайн AnnaSofi

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #32 : БХЭвпСам 04, 2009, 10:15:09 pm »
zhekas, не мог бы ты в общих словах объяснить основные положения алгоритма решения японского кроссворда?

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #33 : БХЭвпСам 06, 2009, 01:05:19 pm »
Если в общих чертах, то. Есть основное поле jpn(i)(j) -поле решения, Оно может принимать значение yest - когда точно поле закрашено, net - когда точно не закращено и pusto - когда не известно. Есть два массива данных stro(i)(j) и sto(i)(j) - массив данных по строкам и столбцам соответственно. Далее для stro(i)(j) организуются два массива lev[()(j) и prav(i)(j) таких же размарностей что и stro. lev(i)(j) - это левая граница для группы закрашенных клеток соответствующих числу stro(i)(j), т.е. номер столбца в jpn(i) , левее которого данная группа точно не попадает. Аналогично prav(i)(j) - это правая граница. Аналогично verh и niz -это верняя и нижняя границы -для sto(i)(j). Ну и задача данного алгоритма - свести lev(i)(j) и prav(i)(j) на расстояние stro(i)(j) (verh(i)(j) и niz(i)(j) на расстояние sto(i)(j)).
« Последнее редактирование: БХЭвпСам 06, 2009, 11:33:24 pm от zhekas »

Оффлайн AnnaSofi

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #34 : БХЭвпСам 06, 2009, 10:19:09 pm »
Спасибо. Вроде стало яснее, правда не уверена, что получится все это реализовать...

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #35 : БХЭвпСам 06, 2009, 10:23:20 pm »
Будут проблемы (а они будут), обращайтесь. По icq или джаберу. Помогу.
« Последнее редактирование: БХЭвпСам 06, 2009, 10:32:57 pm от zhekas »

Оффлайн AnnaSofi

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #36 : БХЭвпСам 06, 2009, 10:49:15 pm »
Хорошо.

Оффлайн ksenja

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #37 : ДХТаРЫм 20, 2011, 05:37:30 pm »
Всем привет!!! Дали курсовую, в которой нужно написать программу-калькулятор чтсленное решение нелинейного уравнения от одной переменное, заданного выражением (например, 5+(12*sin(2*x)+pow(x,3))=0 на заданном отрезке (реализовать методы: дихотомии, хорд, касательных). Пожалуйста, кто может помогите с написанием программы!!!!

Оффлайн ksenja

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #38 : ДХТаРЫм 20, 2011, 05:38:20 pm »
программа должна быть написана на Си

Оффлайн ksenja

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: Алгоритм решения Японского кроссворда
« Ответ #39 : ДХТаРЫм 20, 2011, 05:40:12 pm »
А может у кого-нибудь есть программа для решения японского кроссворда на Си, то киньте пожалуйста ее)))

Оффлайн zhekas

  • Губернский секретарь
  • **
  • Сообщений: 25
  • Репутация: 4
  • Пол: Мужской
Re: Алгоритм решения Японского кроссворда
« Ответ #40 : ДХТаРЫм 20, 2011, 06:39:21 pm »
Моя программа хоть и написана на C++ использует процедурный язык. ни каких классов там нет. Так что переделать её на чистый C не очень сложно.
Хотя подозреваю что вам надо всё и сразу. И хоть что-то делать вы не хотите.