1. Флешом не владею. А кроме пхп на шаред-хостинге ничего нет.
2. Не жалко, будут позже. Сейчас там 50/50 говнокод и ООП. А сам алгоритм построения очень прост.
Здравствуйте. Тут как раз задали домашнее задание – написать судоку-solver. Пока-что я написал простой перебор с небольшой оптимизацией (ставится только то, что можно, а все однозначно определяемые клетки расставляются заранее). На тех тестах ,что нашел работает вроде быстро (0.2- 2 сек), но.. Т.к. задача решения судоку NP-полна, то лучше перебора ничего не придумаешь. А т.к. Вы занимались этой темой, хочу спросить, не знаете-ли какие-нибудь еще методы оптимизации этого перебора?
Не перебором единым. Я думаю, что судоку возможно решить без перебора. По правилам решения (их можно найти в интернете) надо расставить в клетки те числа, которые возможны. До тех пор, пока есть клетки с одной возможной цифрой – вы расставляете туда. Дальше, конечно, сложнее. ( Вообще после любого шага надо пересчитывать допустимые значения, так что эта функция будет выполнятся очень много раз. Если перед вами стоИт задача оптимизации – стОит сосредоточится на этой функции. )
При решении судоку, когда нет очевидных моментов, надо делать предположения. То есть вы находите клетку, где две допустимых цифры. Здесь, можно пустить две ветви решения. Если судоку составлено правильно – одна из них закончится конфликтом.
Такими шагами, я думаю, можно либо прийти к решению, либо сократить количество шагов перебора.
А на чем вы пишете? Постучитесь мне в аську 2275520, было бы интересно поговорить и рассмотреть алгоритм.
Для тех кто знает как играть в судоку это может и нонсенс, а для остальных намного интуитивно понятнее было бы, если бы после клика по белому полю, там появился курсор ввода.
CharnaD, привет)
Совершенно случайно попал на твой блог, если хочешь поговорить об алгоритме решения, можешь мне стукнуть в icq 224116, мне это тоже интересно)
Я писал статью про решение судоку на дельфи, там я описал решение рекурсией (перебором?), быстродействие меня устраивает.
Я также ходил по этой тее по форумам, там достаточно сложные и непонятные варианты были
Ноябрь 9th, 2009 at 20:08
Здорово! Сам написал?
Ноябрь 9th, 2009 at 20:10
Да, за два дня
Ноябрь 9th, 2009 at 20:13
Вторым кликом нашел. Ай-ай-ай))
Ноябрь 9th, 2009 at 20:25
Молодец… хотя смысл этой игры я не знаю )
Ноябрь 10th, 2009 at 00:41
Ну вроде работает. Я просто не фанат судоку.
Ноябрь 10th, 2009 at 13:32
забавная штука.
только я ее так и не прошел
Ноябрь 19th, 2009 at 14:44
Прошел. Круто!
Ноябрь 19th, 2009 at 14:49
таки прошел)
Ноябрь 19th, 2009 at 15:11
до третьего уровня дошел.
дальше сложно((
Ноябрь 19th, 2009 at 23:29
Очень классно… два вопроса:
1) не очень понятно зачем пхп?
2) и где исходники? жалко?
Ноябрь 19th, 2009 at 23:47
1. Флешом не владею. А кроме пхп на шаред-хостинге ничего нет.
2. Не жалко, будут позже. Сейчас там 50/50 говнокод и ООП. А сам алгоритм построения очень прост.
Ноябрь 19th, 2009 at 23:54
Нет… я вообще не понял… а что там на пхп написано? какая часть функциональности?… или сам алгоритм на пхп.. а интерфейс – jQuery?
Ноябрь 20th, 2009 at 00:01
PHP генерирует головоломку, проверяет правильность. В общем весь движок, а jQuery только интерфейс, да.
Ноябрь 23rd, 2009 at 21:12
Здравствуйте. Тут как раз задали домашнее задание – написать судоку-solver. Пока-что я написал простой перебор с небольшой оптимизацией (ставится только то, что можно, а все однозначно определяемые клетки расставляются заранее). На тех тестах ,что нашел работает вроде быстро (0.2- 2 сек), но.. Т.к. задача решения судоку NP-полна, то лучше перебора ничего не придумаешь. А т.к. Вы занимались этой темой, хочу спросить, не знаете-ли какие-нибудь еще методы оптимизации этого перебора?
Ноябрь 23rd, 2009 at 21:25
Не перебором единым. Я думаю, что судоку возможно решить без перебора. По правилам решения (их можно найти в интернете) надо расставить в клетки те числа, которые возможны. До тех пор, пока есть клетки с одной возможной цифрой – вы расставляете туда. Дальше, конечно, сложнее. ( Вообще после любого шага надо пересчитывать допустимые значения, так что эта функция будет выполнятся очень много раз. Если перед вами стоИт задача оптимизации – стОит сосредоточится на этой функции. )
При решении судоку, когда нет очевидных моментов, надо делать предположения. То есть вы находите клетку, где две допустимых цифры. Здесь, можно пустить две ветви решения. Если судоку составлено правильно – одна из них закончится конфликтом.
Такими шагами, я думаю, можно либо прийти к решению, либо сократить количество шагов перебора.
А на чем вы пишете? Постучитесь мне в аську 2275520, было бы интересно поговорить и рассмотреть алгоритм.
Ноябрь 24th, 2009 at 11:42
Для тех кто знает как играть в судоку это может и нонсенс, а для остальных намного интуитивно понятнее было бы, если бы после клика по белому полю, там появился курсор ввода.
Ноябрь 29th, 2009 at 21:34
CharnaD, привет)
Совершенно случайно попал на твой блог, если хочешь поговорить об алгоритме решения, можешь мне стукнуть в icq 224116, мне это тоже интересно)
Я писал статью про решение судоку на дельфи, там я описал решение рекурсией (перебором?), быстродействие меня устраивает.
Я также ходил по этой тее по форумам, там достаточно сложные и непонятные варианты были
Ноябрь 29th, 2009 at 21:55
прошел на 4 уровне.
переодически не совсем корректно определяет цифры которые можно ставить.
Ноябрь 30th, 2009 at 13:12
Наверное, я придираюсь, но на опере 9.10 работает плоховато
Декабрь 16th, 2009 at 12:34
Круто =)
Давно уже игрался. А исходники будут? =)
Декабрь 17th, 2009 at 12:40
Будут, я все хочу найти время доработать их, чтобы было полностью по правилам.
Декабрь 23rd, 2009 at 17:19
Судоку – классная вещь. Меня с нее иногда подштыривает, скажу честно.
Декабрь 25th, 2009 at 13:20
Классная игра. Надо будет попробовать самому такую написать
Январь 7th, 2010 at 17:29
В противовес тебе:
Сапер. =)
Но он полностью на JS и без jQuery. =)
Ночью не спалось…
Август 29th, 2010 at 21:18
Классная вещь!
Автор, если не жалко, пришли код на мыло: triton1989aaa@yandex.ru
Хочу из этого судоку кое что еще замутить, но только твоя основа нужна =)
Август 29th, 2010 at 22:26
Алексей, вам сюда: http://www.charnad.com/blog/isxodniki-sudoku/