Страницы: 1 | (4)
На CPAN выложи, что ли, там и то отзывов будет больше...
твоя прога их будет уметь решать?
как насчет какуро?
их гораздо сложнее в уме решать, имхо прога для какуро более востребованная
Что нового?
1. Как и обещалось, были введена система feedback'ов.
Q. Зачем это нужно?
A. Объект Sudoku::Solve решает судоку и передает некоторую информацию вашей программе, как только что-то удалось выяснить. Удобно? /smiles/kolobok/ad.gif
2. Введено состояние объекта Sudoku::Solve
Это, в основном, для внутренних нужд. Так, например, некоторые feedback'и вызываются не в явном виде в нужных местах, а в функции меняющей это состояние (скажем, объект переходит в состояние SUDOKU_STATE_SOLVING и тут же вызывается feedback по событию SUDOKU_FEEDBACK_START_SOLVING, или при переходе в состояние SUDOKU_STATE_PERFORMING_CHECK вызывается feedback по событию SUDOKU_FEEDBACK_CHECK_START).
3. Карты для чисел теперь глобальные
Дело в том, что в версии 0.5 они хранились в $sudoku->{объект}->{номер объекта}->{'maps'}->{число}. В некоторый момент я заметил, что проверки, которые в действительности привязаны к некоторому объекту, используют карты только для этого объекта. Попытавшись анализировать в каждой проверке все карты, я пришел к правильному решению. /smiles/kolobok/af.gif
Плюс ко всему прочему, карты были спроектированы для использования в последующих версиях. Это лишь означает следующее: если окажется в процессе проверки некоторой гипотезы, что она неверна, то карты можно будет легко восстановить в исходное состояние (до начала проверки), то есть не создавая резервных копий перед проверкой. И это при всем при том, что могут быть вложенные проверки. В самом алгоритме не заложено никаких ограничений на и зависимостей от вложенности проверок.
Существует еще одно состояние - состояние игрового поля (назовем это так). Когда объект только создан (но судоку еще ниоткуда не читалось, то есть игровое поле пусто), это состояние равно нулю. При чтении судоку из файла (короче при заполнении поля начальными числами) и до решения судоку, состояние равно единице. При решении судоку используется состояние равное двум. В дальнейшем, состояние равное трем будет использоваться при проверке гипотезы, четырем и более - вложенных гипотез.
Так вот, в карте для каждого числа и каждой ячейки хранится максимальное состояние, при котором данное число может находиться в этой ячейке. Например, если это состояние равно нулю, то только в нулевом состоянии такое возможно. Если максимальное состояние равно единице, то при состоянии равном двойке (решение судоку) и выше, данное число не может быть в этой ячейке. (На самом деле, все немного сложнее, поскольку очень хочется "наследовать" карты из предыдущего состояния.)
В этих картах яркое применение нашла основная концепция моего алгоритма решения судоку:
при решении судоку, информация, которая нам о нем известна, может лишь уточняться.
То есть, если мы на каком-то этапе поняли, что в некоторой ячейке не может быть определенное число, то впоследствии мы не получим, что это же число может быть в данной ячейке. (Конечно, с небольшой поправкой: речь идет о явном решении или проверке гипотезы. Возврат к точке начала проверки гипотезы означает возврат к той же самой информации, которую затем мы опять будем уточнять.)
4. Поменялся метод error
Теперь туда можно передавать имя файла и номер строки (в отладочных целях).
Так же SUDOKU_WARN и SUDOKU_ERROR приобрели, наконец, свое истинное значение. Теперь модуль Sudoku::Feedback, входящий в данный релиз и фактически полностью эмулирующий старые принты, которыми была напичкана версия 0.5 класса Sudoku::Solve, при ошибке печатает некоторую информацию об ошибке в STDERR, а если эта ошибка имеет уровень SUDOKU_ERROR, то и вовсе завершает работу.
Кстати, на распараллеливание класс не рассчитан. /smiles/kolobok/ap.gif
5. Поменялась стратегия организации проверок
Теперь список проверок, которые, возможно, дадут какие-то результаты при решении, не тупо хранятся в массиве, а организованы в хэше. Это очень полезно ввиду того, что часть проверок, которые добавлялись при проверке, были перенесены в метод set_map (именно изменение карты влечет за собой многие проверки). Но вот он добавлял бы слишком много проверок, если бы не такая организация хранения новых проверок.
6. Исчез тип проверок 'block' (нахождение единственного - если это так - пропущенного числа в объекте - строке, столбце или квадрате три на три)
Тип проверки исчез, а метод check_block остался. /smiles/kolobok/ag.gif Теперь она не осуществляет проверку как check_maps, например, а находит в заданном объекте все числа, у которых в карте (для этого объекта) присутствует лишь одна единица. Например, когда в ходе какой-то проверки находится число, то вызывается эта функция (она не просто проявляет все числа в данном объекте, у которых карта в данный момент содержит ровно одну единицу, а находит одно, обновляет карты, затем повторяет процесс). Такой подход несколько эффективнее.
На самом деле, метод можно вызвать либо для объекта, либо для ячейки, указав в первом случае параметры obj и n, а во втором случае - gpos ячейки. При этом могут быть найдены числа в совсем других объектах. (Смотрите, например, test.check_block.pl.)
7. Добавлена проверка типа 'grps' для группы
Если меняется карта какого-то числа, входящего в группу, то добавляется проверка на поиск групп внутри этой группы. Как правило, группы состоят из небольшого количества чисел, и, следовательно, эта проверка не займет много времени, а результат ее может быть весьма полезным.
8. Исправлено некоторое количество багов
Интересно, для какой более-менее крупной программы (да, думаю, и не только крупной) этого не писали!? /smiles/kolobok/bj.gif
Честно сказать, уже и не помню: то ли это были баги в самой версии 0.5, то ли они появились в ходе эволюции. /smiles/kolobok/bw.gif
Немного о feedback'ах
| Тип feedback'а | Описание | Имя вызываемого метода |
| SUDOKU_FEEDBACK_ERROR | Вызывается при ошибке | onError |
| SUDOKU_FEEDBACK_READ_START SUDOKU_FEEDBACK_READ_END | Вызывается соответственно при начале и конце чтения судоку из файла | onReadStart onReadEnd |
| SUDOKU_FEEDBACK_SOLVE_START SUDOKU_FEEDBACK_SOLVE_END | Вызывается соответственно при начале и конце процесса решения судоку | onSolveStart onSolveEnd |
| SUDOKU_FEEDBACK_SOLVE_ITERATION_START SUDOKU_FEEDBACK_SOLVE_ITERATION_END | Вызывается соответственно в начале и конце основного цикла алгоритма решения судоку | onSolveIterationStart onSolveIterationEnd |
| SUDOKU_FEEDBACK_CHECK_START SUDOKU_FEEDBACK_CHECK_END | Вызывается соответственно в начале и в конце каждой выполняемой проверки (не все проверки, что вызываются из метода solve, выполняются) | onCheckStart onCheckEnd |
| SUDOKU_FEEDBACK_FOUND | Вызывается в тех случаях, когда в процессе решения было найдено число или группа | onFound |
| SUDOKU_FEEDBACK_UPDATED | Вызывается, когда в процессе проверки внутри объекта удалось исключить некоторые позиции. Одним словом, это происходит тогда, когда информация о судоку была уточнена | onUpdated |
| SUDOKU_FEEDBACK_NEW_CHECK | Вызывается, если была добавлена новая проверка | onNewCheck |
SYNOPSIS писать лень. Он, в общем-то, такой же, как и для версии 0.5. Скажу только, что помимо скрипта test.sudoku.pl (который был также включен и в релиз версии 0.5), в данный релиз входит скрипт test.solve.pl, который для судоку sudoku.xml проверяет конкретные гипотезы. Он, по сути, представляет из себя весьма упрощенный алгоритм полного решения, ожидаемого в последующей версии.
Все багрепорты, предложения и прочее пишите сюда, по электронной почте или в аську.
Для запуска требуется Perl и wxPerl. (Более детально сообщить не смогу пока. /smiles/kolobok/bh.gif /smiles/kolobok/bn.gif )
sh>perl ./test.gui.pl
Если предыдущая версия была лишь "пробой пера", то эта версия значительно продвинулась вперед.
В релиз также входит версия 0.7.3b проекта Sudoku::Solve. В ней были исправлены весьма серьезные ошибки релиза 0.7a.
По прежнему жду от вас предложений по программам и сообщений об ошибках. /smiles/kolobok/ad.gif