Комментарии участников:
Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.ояибу!!! решение методом перебора! Я в шоке! как он догадался???
судя по всему вы не имеете отношения к программированию — вам простительно ваше незнание.
метод перебора — самый очевидный и самый неэффективный подход при решении задач.
математиков-программистов с первого курса учат, что есть метод перебора (например, "пузырек") а есть грамотный подход (например, "метод деления на два") и в последствии бьют по рукам за перебор.
метод перебора — самый очевидный и самый неэффективный подход при решении задач.
математиков-программистов с первого курса учат, что есть метод перебора (например, "пузырек") а есть грамотный подход (например, "метод деления на два") и в последствии бьют по рукам за перебор.
Судя по описанию в статье, он предлагал не тупой перебор а гулянию по дереву — типичный подход в AI.
И второе, накипело у меня к "пузырьку". Удивительно как большинство програмеров путают O(n) и конкретное время выполнения задачи для данного n. Да, O(n) bubble sort и скажем, quicksort, очень сильно разнятся О(n*log(n))) vs O(n^2). Но проверьте и удивитесь, bubble sort обгоняет quick sort для n в сотни тысяч а то и миллионы. Он на столько эффективнее использует кэш и пайплайн что так вот странно получается.
И второе, накипело у меня к "пузырьку". Удивительно как большинство програмеров путают O(n) и конкретное время выполнения задачи для данного n. Да, O(n) bubble sort и скажем, quicksort, очень сильно разнятся О(n*log(n))) vs O(n^2). Но проверьте и удивитесь, bubble sort обгоняет quick sort для n в сотни тысяч а то и миллионы. Он на столько эффективнее использует кэш и пайплайн что так вот странно получается.
с "деревьями" учат работать даже будущих офицеров ;)
а на счет больших n — это уже задача другой сферы, и к алгоритмам в общем смысле она отношения не имеет, вам ли не знать :)
а на счет больших n — это уже задача другой сферы, и к алгоритмам в общем смысле она отношения не имеет, вам ли не знать :)
Да, согласен. Судя по краткому описанию, предложеный алгоритм — классический до тривиальности. На оригинальную статью, правда, нет времени.
В шашки уже нельзя выиграть у компьютера :( Теперь и до судоку добрались. Скоро из настольных игр нам останется 
только Чапай.
только Чапай.
И чего? Я на своем телефоне на самом большом уровне сложности любой судоку "вскрываю" где-то за 13-15 минут.
Реально ларчик просто открывается:
1. Эвристика: смотришь приблизительно в каком из квадрантов больше всего уже заполненных цифр и движешься от него к наименее заполненному. Т.е., например, если больше заполнены нижние ряды, а более конкретно — правые нижние, то выбираешь направление движения "справа-налево снизу-вверх"
2. используя выбранное на шаге 1 направление движения далее заполняешь подряд все пустые клетки по кругу 1-2-3-4-...-9, при этом проверяя, чтобы не было коллизий с уже заполненными клетками. Если коллизии не избежать, то возвращаешься на предыдущий ход и увеличиваешь значение. Если и там не избежать, то ещё на один ход назад...
В общем, кто этот алгоритм понял, тому уже играть в судоку неинтересно будет…
Реально ларчик просто открывается:
1. Эвристика: смотришь приблизительно в каком из квадрантов больше всего уже заполненных цифр и движешься от него к наименее заполненному. Т.е., например, если больше заполнены нижние ряды, а более конкретно — правые нижние, то выбираешь направление движения "справа-налево снизу-вверх"
2. используя выбранное на шаге 1 направление движения далее заполняешь подряд все пустые клетки по кругу 1-2-3-4-...-9, при этом проверяя, чтобы не было коллизий с уже заполненными клетками. Если коллизии не избежать, то возвращаешься на предыдущий ход и увеличиваешь значение. Если и там не избежать, то ещё на один ход назад...
В общем, кто этот алгоритм понял, тому уже играть в судоку неинтересно будет…
Вы будете смеяться, но я на втором курсе университета от нечего делать написал такую программулинку. Полный перебор конечно не катит, можно будет чайник чаю выпить пока он будет считать более-менее сложную головоломку, но перебор тут и не нужен. Достаточно просто для каждой клетки запомнить все возможные числа, которые в ней могут стоять (на основании уже расставленных чисел в строке и столбце), и искать клетки, в которые можно поставить только одно число. Если нет таких — выставляем какое-нибудь число случайно, и "переходим на шаг один".
Алгоритм простой, до него додумается любой школьник, а главное — его производительность вполне приемлима.
Новость спокойно запиливать под лозунгом "британские учёные доказали".
Алгоритм простой, до него додумается любой школьник, а главное — его производительность вполне приемлима.
Новость спокойно запиливать под лозунгом "британские учёные доказали".