Решение стандартных судоку с использованием SWI-Prolog clpfd
В Руководстве по clpfd к SWI-Prolog уже есть пример использования clpfd для решения головоломки Судоку. Это действительно показывает силу программирования ограничений Prolog для решения сложных задач с помощью набора строк кода. Но недавно узнал, что вариантов судоку очень много. Итак, я хотел бы показать, как мы можем добавить очень небольшую модификацию в решатель Судоку, чтобы очень легко решить эту проблему в Прологе.
Судоку-убийца и определение проблемы судоку-убийцы
Убийственная судоку - это известный вариант стандартной судоку. Помимо стандартных правил Судоку, Судоку-убийца делится на клетки, сумма чисел в клетках должна равняться маленькому числу в левом углу, и одно и то же число не может появляться в клетке более одного раза. . Убийственная судоку - это комбинация судоку и какуро.
Судоку-убийца сочетает в себе правило Судоку-убийцу и Судоку сравнения и имеет отношение суммы для некоторых клеток вместо информации о сумме. Пример Судоку Большого Убийцы может быть показан в виде следующего изображения из Судоку ежедневного убийцы.
Решение Убийственной Судоку
Чтобы решить Killer Sudoku, нам просто нужно добавить ограничения клеток в решатель, когда мы определяем задачу, мы также даем информацию о клетках и их соответствующую сумму.
Вся программа выглядит примерно так.
get_value_by_key([], _, _) :- !. get_value_by_key([X-Y|_], X, Y) :- !. get_value_by_key([Z-_|Ps], X, Y) :- Z \= X, get_value_by_key(Ps, X, Y).region_constrain(Sums, X-Vs) :- get_value_by_key(Sums, X, Value), all_distinct(Vs), sum(Vs, #=, Value). killer_sudoku(Rows, Splits, Sums) :- length(Rows, 9), maplist(same_length(Rows), Rows), length(Splits, 9), maplist(same_length(Splits), Splits), append(Rows, Vs), Vs ins 1..9, append(Splits, Ks), pairs_keys_values(Pairs, Ks, Vs), sort(1, @>=, Pairs, SortedPairs), group_pairs_by_key(SortedPairs, Regions), maplist(all_distinct, Rows), transpose(Rows, Columns), maplist(all_distinct, Columns), Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs),blocks(Ds, Es, Fs),blocks(Gs, Hs, Is), maplist(region_constrain(Sums), Regions).
Таким образом, нам нужно только передать информацию о дополнительных клетках и соответствующую им информацию о сумме и построить для них отношение ограничения. Это всего на 10 строк кода больше, чем у стандартного решателя Судоку, и мы уже можем решить каждую убийственную судоку на Прологе.
И также мы должны заметить, что, несмотря на название, сложные уровни Killer Sudoku различаются, простая Killer Sudoku может быть даже проще, чем обычная Sudoku, но для взлома самого сложного может потребоваться часы или дни.
Итак, я провожу несколько тестов, чтобы решить различные Убийственные судоку, которые я нашел в Интернете, и смотрю, насколько хорошо решатель может решать проблемы.
Для проблемы из вики он решает проблему мгновенно, но для решения некоторых более сложных проблем могут потребоваться минуты или часы.
?- problem(wiki, Rows, Splits, Sums), killer_sudoku(Rows, Splits, Sums),
| append(Rows, Vs), time(label(Vs)), maplist(portray_clause, Rows).
% 591 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 17776040 Lips)
[2, 1, 5, 6, 4, 7, 3, 9, 8].
[3, 6, 8, 9, 5, 2, 1, 7, 4].
[7, 9, 4, 3, 8, 1, 6, 5, 2].
[5, 8, 6, 2, 7, 4, 9, 3, 1].
[1, 4, 2, 5, 9, 3, 8, 6, 7].
[9, 7, 3, 8, 1, 6, 4, 2, 5].
[8, 2, 1, 7, 3, 9, 5, 4, 6].
[6, 5, 9, 4, 2, 8, 7, 1, 3].
[4, 3, 7, 1, 6, 5, 2, 8, 9].Уровень сложности 10/10 Убийственная судоку от сайта ежедневных убийц судоку. На поиск решения уходит около 2 минут, а на то, чтобы доказать, что есть другие решения, требуется около 6 минут. Поскольку на сайте она отмечена как самая сложная Убийственная судоку, я думаю, что скорость уже довольно высокая. На веб-сайте указано, что среднее время решения проблемы составляет 44 минуты, но это может быть связано с тем, что вы можете использовать подсказку для задачи для простой задачи (сложный уровень 1/10), среднее время также составляет около 40 минут, поэтому скорее всего, либо все люди, которые пытаются решить сложную задачу, являются экспертами в решении Убийственной судоку, либо время на самом деле не отражает сложный уровень проблемы (например, люди хотят использовать подсказку, когда они застряли).
10/10 Судоку-убийца
?- problem(daily_killer_sudoku_hard, Rows, Splits, Sums), killer_sudoku(Rows, Splits, Sums),
| append(Rows, Vs), time(label(Vs)), maplist(portray_clause, Rows).
% 277,532,279 inferences, 112.211 CPU in 112.575 seconds (100% CPU, 2473301 Lips)
[2, 9, 6, 7, 1, 3, 4, 8, 5].
[3, 7, 5, 2, 4, 8, 1, 9, 6].
[1, 4, 8, 5, 6, 9, 3, 7, 2].
[8, 5, 3, 9, 7, 1, 2, 6, 4].
[9, 6, 1, 3, 2, 4, 7, 5, 8].
[4, 2, 7, 8, 5, 6, 9, 1, 3].
[6, 3, 2, 1, 9, 5, 8, 4, 7].
[5, 8, 9, 4, 3, 7, 6, 2, 1].
[7, 1, 4, 6, 8, 2, 5, 3, 9].
% 906,040,567 inferences, 382.551 CPU in 384.761 seconds (99% CPU, 2368417 Lips)
false.Затем я случайно наткнулся на страницу, где говорилось, что существует самая сложная в мире 19 клеток Убийца Судоку. Хотя я не думаю, что существует объективный стандарт сложности, но он кажется довольно сложным, поскольку каждая клетка не ограничена одним блоком, что делает простую стратегию решения Убийственной судоку неработающей. И в посте автор сказал, что на решение проблемы у него уходит шесть дней. Итак, я решил попробовать решатель ограничений.
Самая сложная убийственная судоку
На самом деле решение проблемы занимает довольно много времени (около 12 часов, чтобы найти решение). Но поскольку, кроме ограничений определения задачи, я не использую никакой другой продвинутой стратегии, я думаю, что скорость уже удовлетворительна.
?- problem(most_difficult_killer_sudoku, Rows, Splits, Sums), killer_sudoku(Rows, Splits, Sums),
| append(Rows, Vs), time(label(Vs)), maplist(portray_clause, Rows).
% 98,413,615,883 inferences, 43078.045 CPU in 43212.116 seconds (100% CPU, 2284542 Lips)
[9, 2, 8, 3, 4, 7, 6, 1, 5].
[3, 6, 7, 5, 1, 8, 4, 9, 2].
[5, 1, 4, 6, 2, 9, 7, 3, 8].
[2, 8, 3, 9, 7, 6, 1, 5, 4].
[7, 9, 1, 4, 3, 5, 2, 8, 6].
[4, 5, 6, 1, 8, 2, 9, 7, 3].
[6, 3, 2, 7, 5, 1, 8, 4, 9].
[8, 7, 5, 2, 9, 4, 3, 6, 1].
[1, 4, 9, 8, 6, 3, 5, 2, 7].Решение судоку для великих убийц
Чтобы решить судоку «Великий убийца», нам просто нужно добавить отношение ограничения сравнения к решателю. И мы также должны заметить, что некоторые клетки не имеют информации о сумме, поэтому при построении ограничения для информации о сумме мы должны выбирать только область с информацией о сумме. Программа похожа на следующую.
compare_constrain(Regions, [X, Y]-Relation) :- get_value_by_key(Regions, X, Xs), get_value_by_key(Regions, Y, Ys), all_distinct(Xs), all_distinct(Ys), sum(Xs, #=, Vx), sum(Ys, #=, Vy), (Relation = less -> Vx #< Vy ; ( Relation = equal -> Vx #= Vy ; Vx #> Vy ) ).has_sum_info(Pos, X-_) :- member(X, Pos).greater_killer_sudoku(Rows, Splits, Sums, Compares) :- length(Rows, 9), maplist(same_length(Rows), Rows), length(Splits, 9), maplist(same_length(Splits), Splits), append(Rows, Vs), Vs ins 1..9, append(Splits, Ks), pairs_keys_values(Pairs, Ks, Vs), sort(1, @>=, Pairs, SortedPairs), group_pairs_by_key(SortedPairs, Regions), maplist(all_distinct, Rows), transpose(Rows, Columns), maplist(all_distinct, Columns), Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs),blocks(Ds, Es, Fs),blocks(Gs, Hs, Is), maplist(compare_constrain(Regions), Compares), pairs_keys(Sums, PosHasSumValue), pairs_values(Regions, Vss), maplist(all_distinct, Vss), include(has_sum_info(PosHasSumValue), Regions, RegionsHasSum), maplist(region_constrain(Sums), RegionsHasSum).
Мы определяем другой предикат с именем compare_constrain, который принимает информацию о регионах и отношение сравнения двух клеток. Это что-то вроде [a, b]-less, что означает, что сумма клетки a меньше суммы клетки b. И мы просто добавляем эти ограничения в решатель. Все остальное точно такое же, как решатель Killer Sudoku.
Я использую вышеуказанный решатель, чтобы решить самую сложную большую убийственную судоку из ежедневной убийственной судоку, как показано ниже, и на ее решение уходит гораздо больше времени (около 5 часов), чем на самую сложную Убийственную судоку с веб-сайта. Я думаю, это связано с тем, что отношения сравнения не являются очень сильным ограничением и в некоторых клетках отсутствует информация об ограничении суммы, что делает пространство поиска для распространения ограничения намного больше, чем в обычном Убийственном судоку.
Пример судоку-убийцы
?- problem(daily_greater_killer_sudoku_hard, Rows, Splits, Sums),
| greater_killer_sudoku(Rows, Splits, Sums,
| [[a,b]-equal, [j, o]-less, [r, v]-equal, [u, y]-greater, [y, v]-equal]),
| append(Rows, Vs), time(label(Vs)), maplist(portray_clause, Rows).
% 26,391,594,689 inferences, 17021.320 CPU in 17080.693 seconds (100% CPU, 1550502 Lips)
[5, 4, 2, 9, 6, 8, 7, 3, 1].
[8, 9, 1, 3, 7, 5, 2, 4, 6].
[6, 7, 3, 4, 2, 1, 5, 8, 9].
[9, 2, 8, 5, 4, 7, 1, 6, 3].
[3, 1, 7, 8, 9, 6, 4, 5, 2].
[4, 6, 5, 2, 1, 3, 9, 7, 8].
[7, 3, 6, 1, 5, 2, 8, 9, 4].
[1, 8, 4, 7, 3, 9, 6, 2, 5].
[2, 5, 9, 6, 8, 4, 3, 1, 7].Вывод
Таким образом, цель этой статьи не состоит в том, чтобы собрать самые быстрые решатели Убийственные Судоку и Великие Убийцы Судоку, а просто показать, как мы можем просто добавить кучу строк кода в стандартный решатель Судоку в clpfd. получить универсальный решатель, который может решать Убийственные судоку и Великие убийственные судоку за достаточно разумное время, и показать, что clpfd в SWI-Prolog на самом деле является очень хорошим предметно-ориентированным языком для решения таких задач с целыми числами. домен. А выразительность clpfd делает решение очень простым и менее подверженным ошибкам.
Таким образом, в целом, имея всего около 20 строк кода, мы можем решить два известных расширения обычных задач Судоку в Прологе, и этот код является кратким и выражает высокоуровневое определение проблемы и, следовательно, менее подвержен ошибкам, и действительно может решить очень сложные задачи в разумные сроки :).
Вы можете найти всю программу в clpfd-killer-sudoku.
