Главная страница - Стеллецкий В.
Развлекательная страничка
Некоторые размышления о Японских кроссвордах и их решении
Я программно реализовал алгоритм решения японских кроссвордов исключительно как хобби, и за особой эффективностью не гнался.
Программа у меня состоит из двух частей:
1) решение строки (столбца)
2) общее управление и отображение на экране процесса решения.
Первая часть реализована на языке программирования рефал/2; вторая - на Turbo C 2.0. Взаимодействие этих частей осуществляется посредством вызова bat-файла выполнения рефала из C с передачей данных через файловую систему.
В случае, если часть "общее управление" приходит к выводу, что решение отдельных строк и столбцов не приводит к новым результатам, то включается алгоритм решения кроссворда перебором. Т.е. выбирается крайняя нерешенная строка (или столбец) и в ней заполняется крайняя незаполненная клетка. Оба варианта закрашенный и незакрашенный помещаются в очередь на решение. Эта очередь тоже реализована файлом.
В связи с ограничениями MS DOS, под которой может выполняться программа, размер файла не может превышать 2Гб.
Пишите мне в Гостевую книгу
Отзывы:
 | Очень хотелось бы увидеть исходник, если не трудно вышлите пожалуйста! Интересно было бы узнать чем обусловлен выбор языков? |
|
А Вы разберете, что написано в программе на рефале?
Алгоритм (в итоге) оказался сложный. Программа в рамках одной строки (столбца) умеет делать все то, что я сам умею делать с одной строкой. На рефале мне это было писать удобнее (и короче и нагляднее, а языком я владею). |
|
Забрела случайно к вам...Остались крайне приятные впечатления!!! PS Согласна по поводу японских кроссвордов на все 100%!! |
| :) Спасибо. Последнее время в тех японских кроссвордах, что я смотрю, неоднозначности мне не попадались... Может это была "болезнь роста"? |
|
Привет, я заинтересовался кроссвордами (японскими)
и взялся решать кросcворд тот что с боксером, хотелось бы узнать сколько решений Вы уже отыскали и ск какой скоростью в среднем происходит поиск (у меня порядка 3 милионов уже). Заранее благодарен за ответ:) |
|
Спасибо за Ваш интерес и отклик в гостевой книге.
Теперь про задачу с боксером. Первый раз 2Гб я достиг найдя 116060 решений. Тогда, надеясь, что решений будет не намного больше, и размеры файлов с очередью вариантов на решение начнут уменьшаться, я выделил из этой очереди маленький кусок (около 2% размера очереди) и попробовал решить его. Когда файл с решениями достиг 2Гб, было зафиксировано 947401 решений. При этом общее время решения заняло несколько суток, а очередь вариантов на решение заполнила в упакованном виде еще гигибайт 5, что соответствовало размеру ресурса, который я мог выделить на решение этой задачи. И я решил не продолжать решение этой задачи. |
|
прошу помощи
В самых простых примерах объясняется, что мол, находите самое большое число и закрашиваете всю строчку или столбец.. а если нет такого большого одиночного числа ни в столбиках ни в строчках ? и в каких случаях строка или столбец с этим самым большим числом закрашивается иногда где-то посередине и почему...? |
| Если Вы знаете, что в n клетках строки или столбца находится элемент из m ячеек, и m>n/2, то вы можете быть уверены, что средние 2m-n клеток (из рассматриваемых n) обязательно закрашены... |
| Хороший сайт. Скажи, где взять программу для решений японских кроссвордов, на которую ты ссылаешься. |
| Спасибо. Программу я пока еще не раздаю... |