Я недавно написал программу на Python, которая может решить головоломку судоку. Это в основном алгоритм обратного отслеживания, который грубо форсирует пространство поиска. Я разместил более подробную информацию о фактическом алгоритме в этой теме .
Здесь, однако, я бы хотел больше сосредоточиться на процессе оптимизации. Чтобы быть более точным, я исследовал различные подходы, чтобы минимизировать время решения и количество итераций. И это больше о алгоритмических улучшениях, которые могут быть сделаны, а не о программировании.
Итак, подумав об этом, в алгоритме обратного отслеживания грубой силы не так много вещей, которые можно было бы оптимизировать (рад, что здесь вы ошиблись). Два реальных улучшения, которые могут быть сделаны: во-первых, метод, с помощью которого выбирается следующая пустая ячейка, и, во-вторых, метод, с помощью которого выбирается следующая возможная цифра. Эти два варианта могут иметь значение для перехода по тупиковому пути поиска или к поисковому пути, который заканчивается решением.
Затем я сел и попытался придумать разные методы для вышеупомянутых двух вариантов. Вот что я придумал.
Следующая пустая ячейка может быть выбрана следующими способами:
- A - первая ячейка слева направо, сверху вниз
- B - первая ячейка справа налево, снизу вверх
- C - случайно выбранная ячейка
- D - ближайшая ячейка к центру сетки
- E - ячейка с наименьшим количеством доступных вариантов (выбор
здесь означает цифру от 1 до 9)
- F - ячейка с наибольшим количеством доступных вариантов
- G - ячейка с наименьшим количеством пустых связанных ячеек (связанных ячеек)
один из той же строки, из того же столбца или из того же 3x3
квадрант)
- H - ячейка с наиболее пустыми ячейками
- I - ячейка, ближайшая ко всем заполненным ячейкам (измеренная по
от центра ячейки к центру ячейки)
- J - клетка, наиболее удаленная от всех заполненных клеток
- K - ячейка, у которой соответствующие пустые ячейки имеют наименьшее количество доступных
выбор
- L - ячейка, чьи связанные пустые ячейки имеют наибольшее количество доступных
выбор
И следующую цифру можно выбрать следующими способами:
- 0 - самая низкая цифра
- 1 - самая высокая цифра
- 2 - случайно выбранная цифра
- 3 - эвристически, наименее используемая цифра на доске
- 4 - эвристически, наиболее часто используемая цифра по всем направлениям
- 5 - цифра, при которой соответствующие пустые ячейки будут иметь наименьшее количество
количество доступных вариантов
- 6 - цифра, из-за которой соответствующие пустые ячейки будут иметь наибольшее количество
количество доступных вариантов
- 7 - цифра, которая является наименее распространенным доступным выбором среди связанных
пустые клетки
- 8 - цифра, которая является наиболее распространенным из доступных вариантов среди
пустые ячейки
- 9 - цифра, которая является наименее распространенным из доступных вариантов
доска
- a - цифра, которая является наиболее распространенным из доступных вариантов
доска
Итак, я запрограммировал вышеуказанные методы в программу. Предыдущие цифры и буквы могут быть переданы в качестве параметров в программу, и она будет использовать соответствующий метод оптимизации. Более того, поскольку иногда две и более ячейки могут иметь одинаковую оценку, существует возможность указать второй параметр сортировки. Например, параметр «EC» будет означать выбор случайной ячейки из всех ячеек с наименьшим количеством доступных вариантов.
Первая функция назначит веса, умноженные на 1000, а вторая функция добавит новые веса, умноженные на 1. Таким образом, если, например, из первой функции три ячейки имеют одинаковый вес, например, 3000, 3000 3000, тогда вторая функция добавит свои веса. например 3111, 3256, 3025. При сортировке всегда выбирают наименьший вес. А если нужно обратное, то весовые функции вызываются с -1000 драм -1, но сортировка по-прежнему выбирает наименьший вес.
Прежде чем продолжить, стоит отметить, что программа всегда выбирает пустую ячейку (не заполненную) и всегда выбирает цифру, которая соответствует текущим ограничениям Судоку для ячейки (в противном случае это просто неразумно).
Имея вышеизложенное, я тогда решил запустить программу с каждой возможной комбинацией параметров и посмотреть, что произойдет, какие из них работают лучше всего - в основном для грубой силы грубой силы :) Есть 12 методов для выбора ячейки и 11 методов для выбора цифр в теории существует 17244 комбинаций, которые нужно попробовать, но я удалил некоторые ненужные (такие как «AA», «BB» и т. д., а также исключил случайные методы, так как все они ужасно неэффективны), поэтому число комбинаций в итоге было 12,100. Каждый прогон был сделан на одной и той же головоломке Судоку, которая очень проста:
0,3,0,0,9,0,6,1,0
6,0,8,5,0,3,4,9,7
0,9,0,6,7,0,0,0,3
0,5,0,8,0,4,0,0,1
1,6,0,3,0,0,9,8,2
0,0,2,9,6,0,3,0,0
0,8,0,1,3,0,2,0,6
3,0,5,0,4,6,0,7,9
0,4,6,0,8,0,1,0,0
... и пространство поиска составляет 36 691 771 392. Это просто простое произведение количества вариантов выбора для каждой пустой ячейки данной головоломки. Это преувеличение, потому что, как только одна ячейка заполнена, это уменьшает количество вариантов выбора для других ячеек, но это самый быстрый и простой показатель, который я мог придумать.
Я написал короткий скрипт (конечно, на Python), который автоматизировал весь процесс тестирования - он запускал решатель для каждого набора параметров, записывал время завершения и выкидывал все в файл. Кроме того, я решил сделать по 20 прогонов каждого, потому что я получал 0 раз из функции time.time () для одиночных прогонов. А также, если для выполнения какой-либо комбинации потребуется более 10 секунд, сценарий остановится и перейдет к следующей.
Сценарий, завершенный в 13:04:31 часов на ноутбуке с Intel Core i7-4712MQ 2,30 ГГц, использовалось не более 2 из 8 ядер, а средняя загрузка ЦП составляла около 12%. 8 652 из 12 100 комбинаций, выполненных менее чем за 10 секунд.
И победителями являются: (* числа, скорректированные для единичного времени выполнения / итераций)
1) Самое быстрое время 1,55 мс:
«A0» и «A1» с 84 итерациями и 46 итерациями возврата
и "B0", "B01", "B1", "B10", "BA01", "BA1", "BD01", "BD1" и "BD10" с 65 итерациями и 27 итерациями возврата.
Самые быстрые методы - самые простые, такие как A, B и D. Другой метод не появляется до ранжирования 308, а это «E0».
2) Наименьшее количество итераций из 38 и 0 итераций возврата:
Удивительно, что многим методам удалось добиться этого, самыми быстрыми из которых были "B17", "B6", "B7", "BA16", "BA60", "BA7", "BD17" и "BD70" со временем 2,3 мс и самые медленные из них: «IK91», «JK91», «KI91», «KJ91», «KJ9a», «IK9a», «JK9a» и «KI9a» со временем около 107 мс.
Также удивительно, что метод F имеет несколько хороших позиций, таких как «FB6» с 7 мс (???)
В целом, A, B, D, E, G и K, по-видимому, работают значительно лучше, чем C, F, H и L, а I и J вроде как промежуточные. Кроме того, выбор цифры, казалось, не имел большого значения.
И, наконец, давайте посмотрим, как эти методы-победители справляются с самой сложной в мире головоломкой судоку, как утверждается в этой статье http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html
* Учитывая, что алгоритмы не всегда бывают быстрыми, возможно, некоторые алгоритмы лучше справляются с некоторыми головоломками Судоку, но не с другими ...
Загадка:
8,0,0,0,0,0,0,0,0
0,0,3,6,0,0,0,0,0
0,7,0,0,9,0,2,0,0
0,5,0,0,0,7,0,0,0
0,0,0,0,4,5,7,0,0
0,0,0,1,0,0,0,3,0
0,0,1,0,0,0,0,6,8
0,0,8,5,0,0,0,1,0
0,9,0,0,0,0,4,0,0
... и пространство поиска составляет 95 865 912 019 648 512 x 10 ^ 20.
Победителем становится «A0», заканчивающийся за 1092 мс с 49 559 итерациями и 49 498 итерациями возврата. Большинство других не очень хорошо. «A0», «A1», «B0», «B01», «B1», «B10», «BA01», «BA1», «BD01», «BD1» и «BD10» закончили примерно за 2500 мс и 91k итерации, а остальные 30+ секунд, 400 тыс. + итераций.
Но этого недостаточно, поэтому я выполнил полный тест всех наборов параметров и для самого сложного судоку. На этот раз делать один раз не 20, а также время отключения 2,5 секунды. Сценарий завершен в 8:23:30 часов. 149 из 12 100 комбинаций, выполненных менее чем за 2,5 секунды.
Победителями в обеих категориях являются «E36», «E37», «EA36» и «EA37» со временем 109 мс, 362 итерациями и 301 итерациями возврата. Кроме того, на первых 38 позициях доминировала начальная буква «Е».
В целом E возглавляет чарты, без сомнения, просто взглянув на сводную таблицу. A, B, I и J имеют несколько рейтингов, но ничего особенного, а остальные даже не успели раз в 2,5 секунды.
В заключение, я думаю, что можно с уверенностью сказать, что если головоломка Судоку является простой, то используйте грубую силу с наименьшим сложным алгоритмом, но если головоломка Судоку является сложной, то стоит потратить накладные расходы на выбор методы.
Надеюсь, это поможет:)