прога Японские кроссворды (предложение разработки)

[pluton8]

всем привет!
искал прогу для разгадывания японских кроссвордов, но ничего нативного не нашёл. поэтому пришла мысля написать такое дело.
имхо с++ знаю неплохо, qt4 только начинаю изучать. поэтому трудно пока представить как это всё делать, например, рисование поля, обработка клавиатуры и мыши, и тд. посмотрел в книгу - в qt куча фич, которые можно юзать, но у меня нехватает знаний и опыта.
вобщем, если кто-то хочет помочь мыслёй по проектированию проги, буду рад, обращайтесь. /* JID: pluton-od@ya.ru */
спасибо!

[S7a1k3r]

всем привет!
искал прогу для разгадывания японских кроссвордов, но ничего нативного не нашёл. поэтому пришла мысля написать такое дело.
имхо с++ знаю неплохо, qt4 только начинаю изучать. поэтому трудно пока представить как это всё делать, например, рисование поля, обработка клавиатуры и мыши, и тд. посмотрел в книгу - в qt куча фич, которые можно юзать, но у меня нехватает знаний и опыта.
вобщем, если кто-то хочет помочь мыслёй по проектированию проги, буду рад, обращайтесь. /* JID: pluton-od@ya.ru */
спасибо!

я когда-то по молодости сие дело хотел сотворить (на трупо паскале. молод был, так что не бейте сильно). даже алгоритм расписал как его решать. поищу - скину.
ну gui, положим, не самое сложное, что тут есть. имхо алгорит решения посложнее будет.

[pluton8]

имхо алгорит решения посложнее будет

прога пока предполагается для решения кроссвордов юзером, то есть вручную. а насчёт авто решения, то, конечно, довольно трудно будет.

ну gui, положим, не самое сложное

вот я пока не могу разобраться, на каком виджете и как можно поле рисовать

[promov]

Cтранно, конечно. Зачем спрашивать-то? Хочешь писать так пиши. Будут конкертные вопросы тогда и спрашивай. Ясно дело, тяжело. А так что... Ну, узнаешь ты алгоритм у людей... Что за удовольствие... Слушай, раз хочешь.

Я такую программу написал на TurboPascal. Никакой графики. В качестве решения построчно выводит массив символов типа int из 0 и 1.

Для простоты и начала: на С++ тоже представим таблицу в виде массива. Допустим, 10 строк и 20 столбцов. Понятийный аппарат: клеточка это элемент массива, закрашенная клеточка это 1, незакрашенная 0

Надо так делать:

1) Предполагать, что один из элементов равен 1;
2) Делать вывод о втором элементе (равен 1 или равен 0 или неопределённо. Если неопределённый, значит, предполагать его равным 1);
3) Делать вывод о третьем элементе (равен 1 или равен 0 или неопределённо. Если неопределённый, значит, предполагать его равным 1);
4) Делать вывод о четвёртом элементе (равен 1 или равен 0 или неопределённо. Если неопределённый, значит, предполагать его равным 1);
5) Делать вывод о пятом элементе (равен 1 или равен 0 или неопределённо. Если неопределённый, значит, предполагать его равным 1);
6) И так далее пока всё не заполним, либо к противоречию не придём. Пришли к противоречию- поехали его искать. То есть последний неопределённый элемент (он нами предположен как 1) предполагать равным 0 и снова в путь.

Но это прелюдия. Cам видишь, работы непочатый край. У меня черновых (в смысле рабочих массива штуки 4 в программе). Думай, разбирайся, ломай голову. А теперь главное: нумерация элементов. Cейчас нарисую и прикреплю изображение.

Принцип понятен? Начинать можно, конечно, с любого угла и в любом направлении. Не вопросы типа: как быть, если количество строк не равно количеству столбцов я отвечать не буду (пока). Сам. Всё сам. Теперь о графике: я бы попробовал по-простому реализовать алгоритм, как я (int massiv [n] [m]). Графика потом.

Cложно, конечно. Я писал с месяц. Потом брату бутылк коньяка на прадостях поставил.
В принципе, я бы эту программу найти мог, наверное где-то на дискете- я такие вещи не выкидываю. Но знаешь, в чём там прикол? Там ни одного комментария... У меня хватало ума писать без комментариев. Думал: своё- всегд разберусь.

Как же, разберусь...
P. S. Сам понимаешь, для компьютера нет "правильных" и "неправильных" рисунков. В том смысле, что если решения 2, выведется первое найденное- ну, это у меня так. Ты, может, лучше сделаешь.
P. S. S. Важно от предложенного алгоритма не на шаг не отступать. То есть, если ты видишь, что некоторый элемент по-любому равен 0 (допустим, первый)- тебя это не волнует. Машина всё равно должна предположить, что он равен 1! Потом это исправится- в цепочке рассуждений машина придёт к противоречию, будешь искать в чём ошиблась и придёт к выводу, что элемент номер 1 равен 0.
Решала у меня довольно долго. Таблицу 19x19 решала полчаса. Больше не пробовал. Правда, компьютер был старый.

[pluton8]

promov , спасибо за объяснения, но я пока хочу написать прогу для решения вручную, просто оболочку.
авторешалка мож будет пожже

как я понимаю, начать надо с морды, то есть рисование поля, клацание мышей и клавиатурой. какой виджет юзать, и как правильно это сделать?

[OCTAGRAM]

Таблицу 19x19 решала полчаса. Больше не пробовал. Правда, компьютер был старый.

Мой AMD-K5 100MHz на сложных случаях мог полтора дня стоять. Кроссворды брались из "Крота", разгадывались, ответы отсылались. В течение нескольких месяцев. Правда, так ничего и не выиграли.

В программе постоянно появлялись новые оптимизации. Правда, я так и не попробовал перевести свой движок на корутины, но я тогда даже не знал, что это такое По идее, это могло бы ещё более ускорить перебор.

[Subj]

Я такую программу написал на TurboPascal. Никакой графики. В качестве решения построчно выводит массив символов типа int из 0 и 1.

Для 0 и 1 могло и Boolean хватить

[OCTAGRAM]

Для 0 и 1 могло и Boolean хватить

Там в промежуточных "вычислениях" ещё неопределённость должна быть.

[promov]

Тут ведь ещё какая фишка.
Если, допустим решение улучшить и ввести в алгоритм несколько приёмов, которыми пользуется человек, то это будет супер. Даже внедрение одного приёма здорово убыстрит решение. Самый простой пример: имеем некоторую строку, допустим длиной 20 и единственную цифру рядом с ней 15. Это значит, что мы гарантированно закрасим 10 клеточек в этой строке.

Если подобные приёмы реализовать в алгоритме, это конечно, высший класс. Это для фанатиков (в хорошем смысле слова). Ну и, программа будет заметно больше.

Я ничего подобного не делал. Только способ, предложенный в моём первом сообщении.

[RasenHerz]

вот я пока не могу разобраться, на каком виджете и как можно поле рисовать

на любом.) я люблю рисовать на QLabel =)

З.Ы. будет круто если напишешь эту прогу используя OpenGL.
З.З.Ы в примерах от Trolltech видел игру крестики-нолики(tic-tac-toe) - пример называется Task Menu Extension Example (Qt Designer Manual -> Examples -> Task Menu Extension Example)
Еще посмотри Qt Reference Documentation -> Tutorials and Examples - там много примеров по рисованию

[pluton8]

на любом.) я люблю рисовать на QLabel =)

очень интересно )))) я пока раскопал QPixmap. мне надо, чтобы оно реагировало на перемещение крысы, и клацание кнопок на клаве. это делать с помощью эвентов?

З.Ы. будет круто если напишешь эту прогу используя OpenGL.

)) да уж. сейчас хоть обычно написать бы

[RasenHerz]

QPixmap - всего-лишь картинка, тебе надо будет ее "применить" к виджету. практически все виджеты могут отслеживать движение курсора(во всяком случае главная форма должна), на клаву тож реагировать будут. читай доки и книжки.

[pluton8]

RasenHerz, спасибо за объяснение. но ведь должен быть какой-то специальный виджет для рисования?

читай доки и книжки

вот читаю, буду думать и пробовать

[RasenHerz]

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

[OCTAGRAM]

Тут ведь ещё какая фишка.
Если, допустим решение улучшить и ввести в алгоритм несколько приёмов, которыми пользуется человек, то это будет супер. Даже внедрение одного приёма здорово убыстрит решение. Самый простой пример: имеем некоторую строку, допустим длиной 20 и единственную цифру рядом с ней 15. Это значит, что мы гарантированно закрасим 10 клеточек в этой строке.

Если подобные приёмы реализовать в алгоритме, это конечно, высший класс. Это для фанатиков (в хорошем смысле слова). Ну и, программа будет заметно больше.

Я ничего подобного не делал. Только способ, предложенный в моём первом сообщении.

Собственно, так оно и работало. Рекурсивная функция, если обнаруживала, что на её интервале одни вопросы, заполняла их автоматом. Это сильно ускорило процесс. Потом до меня дошло, что при рекурсивном переборе нужно чередовать, с какой стороны перебирать позицию палки. Экземпляр перебирающий позицию первой палки, вызывает экземпляры, перебирающие позицию последней палки, потом позицию второй, потом позицию предпоследней. Разгдадывание на обоих краях идёт, а в центре часто вопросы, так что, когда крайние палки разместились, рекурсивный вызов часто получает последовательность вопросов, с которой он уже знает, что делать. Потом было усовершенствовано заполнение автоматом. Функция при каждом вызове пытается заполнить автоматом переданное ей пространство. Если там, где должны быть плюсы, были плюсы, там, где заполнение автоматом не даёт определённости, не было минусов или плюсов, то, конечно, можно применять заполнение автоматом. Это тоже сильно ускорило процесс. Потом, помню, убрал повторяющиеся обсчёты строчек/столбцов, если за прошлый раз ничего не изменилось. (там попеременно горизонтально/вертикально проходы шли). Это тоже сильно ускорило процесс.

Не помню другой такой творческой задачи.

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

[pluton8]

всем привет!
пишу прогу, разбираюсь с кутёй4.
есть такая проблема: как проверить строку/столбец поля на соответствие тому, что там может быть (по левому и верхнему заголовкам)? пока что я придумал такое: преобразовал строку поля в текстовое представление, потом составил по заголовку регэксп, и проверяю. результаты, конечно, странные
сырцы проги можно забрать по адресу: https://jcw.svn.sourceforge.net/svnroot/jcw/trunk
спасибо!

[zhekas]

Всем привет Я написал прогу на Лазарусе с gtk2 (раньше писал на Turbo Pascale). Она именно решает Кроссворд людскими методами. Достаточно большие кроссворды размером этак 70*50(больше не встречал) решает меньше чем за пол-секунды. Вашим перебором такие кроссворды просто зависнут.Интерфейс самый примитивный. Даные сохраняю в текстовом документе.
Кому надо стучите в личку.

[promov]

Не верю.

[zhekas]

Не верю.

Вышли мне свой e-mail. Я тебе пришлю исходник, исполняемый файл и примеры

[promov]

Лазарус, я так понимаю это язык? А на Pascal сможешь? На Си не сможешь, наверное, раз ты его не упоминаешь.
Вообще, строго говоря, тут неувязочка небольшая выходит. Дело вот в чём.
Существует целый ряд кроссвордов, имеющих не одно решение. Моя программа выдаст первое попавшееся решение. А что выдаст твоя программа? Тоже первое попавшеся решение? Но тогда получается, что она использует имено машинные методы!
Если не согласен, могу проиллюстрировать на примере.

[zhekas]

После того прошол основной метод. Идет метод перебора. Только не просто перебор, а с помощью основного метода. Грубо говоря, берется пустая клетка и на её место ставится произвольное значение. После производится снова основной метод. Если находится ошибка, то значе клетки меняется на противоположный. И это решает быстрее, чем обычный перебор.

[zhekas]

На паскале у меня было на писано пкрвым делом. Только там проблема с выводом на экран. Могу тебе переслать Паскалевский документ.

[promov]

Посмотри сюда.
У кого есть безпроводной интернет и Linux?
Видишь, я пока ограничен в пользовании интернетом. Но всё равно спасибо как руки дойдут, так доберусь.

Пока же предлагаю здесь обсудить кое-какие вещи. Первое: что ты называешь основным методом?

[zhekas]

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

[promov]

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

[zhekas]

Без перебора, как ты заметил, не обойтись. Иначе простая матрица 2*2 с еденицами не даст решени. Однако в переборе задействован и основной метод. Его доля (основного метода)гораздо больше. Фактически программа задумывалась как именно как описание алгоритма человеческого метода. И затем был дописан небоьшой кусок(по сравнению с основным методом) кода перебора

[promov]

Ну, ясно. Теперь картина более или менее прояснилвсь. Действительно, почему бы не быть такому, что используя основной метод и метод переюбора, кроссворды решались быстрее, нежели просто методом перебора?

Ведь метод перебора чем плох? Предполагаешь первую клетку и пока до последней не дойдёшь, не уверен в правильности предположения. На последжней споткнулся- и запросто может случиться, что тыошибся имено в первой клетке. И начинаешь решение сначала.

Основной метод позволяет определять некоторые клетки со стопроцентной вероятностью: закрашены олни или нет. К ним то есть нет необюходимости возвращаться. Это во многом убыстряет решение. (Должно, по крайней мере, на практике не проверял)

Но! При решении некоторых японских кроссвордов метод перебора+основной метод всё же проигрывает методу перебора. Угу?

[zhekas]

Честно, я не знаю. В полне возможно. Хотя, к примеру, я сечас попробовал матрицу 90*90 с 5-ю еденицами в каждой строке и столбце. Решил за 1.5 секунды.

[promov]

Говоря "некоторые", я имел ввиду, имеющие много решений. Допустим, матрица 5 на 5, в каждой строчке по одной закрашенной клеточке.
Тогда простой метод простого перебора выласт первое попавшееся решение.
Метод перебора+ основной метод тоже выдаст первое попавшеея решение (если так запрограммировать), но плюс к этому потеряет кучу времени на обращение к непосредственно к основному методу. Ни одно из обращений не будет иметь смысла- а поэтому тут не будет выигрыша во времени...

Хотя нет, вру. Последнее обращение к основному методу будет иметь смысл. Ибо там можно будет со 100-процентной уверенностью определить последнюю клетку.
Но не предпоследнее обращение к основному методу, не предпредпоследнее, ни все предыдущие не будут иметь смысла, но будут быть. А это- потеря времени.

[zhekas]

а по твоему 90*90 по 5 едениц в каждой строке и столбцу имеет 1 решение? Он имеет гораздо больше решений чем 90*90 с одной еденицей в каждой строке и столбце, не говоря уже 5*5