Published on
Updated on 

Решение Чудо Судоку в Прологе

Authors

Автор статьи - Ben Congdon, ссылка на оригинал: Solving the "Miracle Sudoku" in Prolog. Перевод опубликован с разрешения автора.

Если вы еще не видели его, вы обязаны посмотреть это видео на "CrackingTheCryptic" конкурсного решателя судоку, работающего над головоломкой "Чудо Судоку":

https://www.youtube.com/watch?v=yKf9aUIxdb4&feature=emb_title

Посмотрев это видео, я вспомнил об одном из моих курсов по языкам программирования, на котором мы написали простой растворитель судоку в Prolog. Так как Prolog - это декларативный язык, написание судоку-решателя удивительно лаконично. По сути, все, что нужно программисту, это определить ограничения игры, и Prolog достаточно умен, чтобы найти решение:

-

            sudoku(Rows) :-
                length(Rows, 9), maplist(same_length(Rows), Rows),
                append(Rows, Vs), Vs ins 1..9,
                maplist(all_different, Rows),
                transpose(Rows, Columns),
                maplist(all_different, Columns),
                Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
                blocks(As, Bs, Cs),
                blocks(Ds, Es, Fs),
                blocks(Gs, Hs, Is).

            blocks([], [], []).
            blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
                    all_different([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
                    blocks(Ns1, Ns2, Ns3).

Приведенный выше код взят из документов SWI Prolog, в которых используется расширение программирования логики ограничения. Вы можете поиграть с ним в онлайн-среде SWISH от Prolog.

Крутая вещь в этом коде заключается в том, что он работает как решатель судоку и как генератор судоку. Вы можете запросить его с частично решенной доской, и он найдет все допустимые решения. Это означает, что вы также можете дать ему пустую доску, и Prolog сгенерирует все возможные решения для судоку (хотя это займет некоторое время, так как 6,7 ×10216,7×1021 действительные доски [1]).

Как заявление об отказе от ответственности, я не очень хорошо знаю Prolog. Я с ним только что-то возился, поэтому уверен, что его использование неоптимально. Несмотря на это, мне удалось написать рабочий решатель Miracle Sudoku. 😄

Чудо Судоку Солвер

Чтобы написать решатель для головоломки Miracle Sudoku, нам нужно закодировать следующие правила:

  • Применяются нормальные правила судоку:
    • Все строки / столбцы должны содержать 1..9 ровно один раз.
    • Каждый блок 3x3 должен содержать 1..9 ровно один раз.
  • Любые две клетки, разделенные ходом коня или ходом короля, не могут содержать одну и ту же цифру.
  • Любые две ортогонально смежные ячейки (то есть ячейки, имеющие общее ребро) не могут содержать последовательные цифры.

Ортогональная смежность ограничение является самым простым кодированием. Для каждой сетки 3х3 на доске нам нужно убедиться, что углы отличаются от соседей как минимум на один. (Мы используем углы вместо середины для обработки граничных случаев на краю сетки.)

            %-  [N4, N5, N6],
            %-  [N7, N8, N9]]
            ortho_adjacent([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
                abs(N1 - N2) #> 1, abs(N1 - N4) #> 1,
                abs(N3 - N2) #> 1, abs(N3 - N6) #> 1,
                abs(N7 - N4) #> 1, abs(N7 - N8) #> 1,
                abs(N9 - N8) #> 1, abs(N9 - N6) #> 1,
                append([N2, N3], Ns1, Z1),
                append([N5, N6], Ns2, Z2),
                append([N8, N9], Ns3, Z3),
                ortho_adjacent(Z1, Z2, Z3).
            ortho_adjacent([_,_], [_,_], [_,_]). %- Base case

Далее - ограничение на передвижение короля, которое так же просто. Я решил использовать функцию all_different в качестве ярлыка для неравенства. Можно было бы использовать оператор #= на соседях N5, но нужно еще и обработать края сетки, поэтому нужно еще и ограничить углы - N1, N3, N7, и N9. К сожалению, это создает дублирующие ограничения.

            %-  [N4, N5, N6],
            %-  [N7, N8, N9]]
            kings_move([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
                    all_different([N1, N2, N4]), all_different([N4, N7, N8]),
                    all_different([N2, N3, N6]), all_different([N8, N9, N6]),
                    all_different([N5, N4, N2]), all_different([N2, N5, N6]),
                    all_different([N5, N6, N7]), all_different([N4, N5, N8]),
                    append([N2, N3], Ns1, Z1),
                    append([N5, N6], Ns2, Z2),
                    append([N8, N9], Ns3, Z3),
                    kings_move(Z1, Z2, Z3).
            kings_move([_,_], [_,_], [_,_]).

Сначала я думал, что ограничение движения Рыцаря будет труднее написать, но оказывается, что оно выкладывается так же хорошо, как и другие: все движения «L» рыцаря также фиксируются в сетке 3x3.

            %-  [N4, N5, N6],
            %-  [N7, N8, N9]]
            knights_move([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
                N1 #\= N6, N1 #\= N8,
                N3 #\= N8, N3 #\= N4,
                N7 #\= N2, N7 #\= N6,
                N9 #\= N4, N9 #\= N2,
                append([N2, N3], Ns1, Z1),
                append([N5, N6], Ns2, Z2),
                append([N8, N9], Ns3, Z3),
                knights_move(Z1, Z2, Z3).
            knights_move([_,_], [_,_], [_,_]).

Теперь, когда мы написали отношения для правил Miracle Sudoku, нам нужно добавить их в исходную sudoku функцию. Каждая функция занимает 3 строки за раз и должна работать над каждым окном из трех строк на доске. Подробный способ сделать это заключается в следующем:

                ...
                Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
                ...
                ortho_adjacent(As, Bs, Cs),
                ortho_adjacent(Bs, Cs, Ds),
                ortho_adjacent(Cs, Ds, Es),
                ortho_adjacent(Ds, Es, Fs),
                ortho_adjacent(Es, Fs, Gs),
                ortho_adjacent(Fs, Gs, Hs),
                ortho_adjacent(Gs, Hs, Is),
                ...

Мы утверждаем ortho_adjacent связь по строкам (A, B, C), затем (B, C, D) и так далее. Мы можем использовать, maplist чтобы сделать это более компактным:

                ...
                Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
                ...
                append(Chunk1,       [_, _], Rows),
                append([_|Chunk2],   [_],    Rows),
                append([_,_|Chunk3], [],     Rows),
                maplist(ortho_adjacent, Chunk1, Chunk2, Chunk3),
                maplist(knights_move,   Chunk1, Chunk2, Chunk3),
                maplist(kings_move,     Chunk1, Chunk2, Chunk3).

Для объяснения: мы используем append для создания 3 «кусков» строк. Chunk1эквивалентно [As,Bs,Cs,Ds,Es,Fs,Gs], Chunk2 есть [Bs,Cs,Ds,Es,Fs,Gs, Hs]и Chunk3 есть [Cs,Ds,Es,Fs,Gs,Hs,Is]. Затем мы maplist применяем эти куски к нашим отношениям. Когда вы передаете несколько списков maplist, он вызывает предоставленное отношение с i элементом j списка в качестве аргумента отношения.

Обозначения из maplist документации объясняют его образец применения аргумента:

                P(X11, ..., Xm1),
                ...
                P(X1n, ..., Xmn).

Теперь у нас есть краткий способ описания проблемы Чудесного Судоку в Prolog!

                length(Rows, 9), maplist(same_length(Rows), Rows),
                append(Rows, Vs), Vs ins 1..9,
                maplist(all_different, Rows),
                transpose(Rows, Columns),
                maplist(all_different, Columns),
                Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
                blocks(As, Bs, Cs),
                blocks(Ds, Es, Fs),
                blocks(Gs, Hs, Is),
                append(Chunk1,       [_, _], Rows),
                append([_|Chunk2],   [_],    Rows),
                append([_,_|Chunk3], [],     Rows),
                maplist(ortho_adjacent, Chunk1, Chunk2, Chunk3),
                maplist(knights_move,   Chunk1, Chunk2, Chunk3),
                maplist(kings_move,     Chunk1, Chunk2, Chunk3).

Это работает?

Оригинальное чудо судоку из видео начинается с этой подсказки.

Мы можем закодировать эту проблему в Prolog, создав доску 9x9 и наполнив ее 2-значными подсказками. Мы оставляем остальную часть доски как '_', чтобы Prolog знал, что это свободные переменные. Наш решатель будет держать 1 и 2 в тех позициях , которые они установлены, но волен выбрать любое значение для остальных '_' х, с учетом ограничений , головоломки.

                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,1,_,_,_,_,_,_],
                        [_,_,_,_,_,_,2,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_]]).

Теперь мы можем запросить решения с помощью нашего решателя:

Вот что делает запрос:

  • problem(1, Rows) утверждает, что Rows должен соответствовать подсказке.
  • sudoku(Rows) утверждает, что решение должно соответствовать ограничениям Miracle Sudoku.
  • maplist(label, Rows) говорит Prolog найти конкретные значения для каждой из свободных переменных в Rows. (В противном случае мы просто получаем список ограничений для каждой переменной)
  • maplist(portray_clause, Rows) довольно печатает решение.

И результат?


            [4, 8, 3, 7, 2, 6, 1, 5, 9].
            [7, 2, 6, 1, 5, 9, 4, 8, 3].
            [1, 5, 9, 4, 8, 3, 7, 2, 6].
            [8, 3, 7, 2, 6, 1, 5, 9, 4].
            [2, 6, 1, 5, 9, 4, 8, 3, 7].
            [5, 9, 4, 8, 3, 7, 2, 6, 1].
            [3, 7, 2, 6, 1, 5, 9, 4, 8].
            [6, 1, 5, 9, 4, 8, 3, 7, 2].
            [9, 4, 8, 3, 7, 2, 6, 1, 5].

Решатель работает! Чтобы проверить, что нам не просто повезло, было бы неплохо попробовать это на другом экземпляре головоломки. К счастью, канал CrackingTheCryptic позже опубликовал видео со второй загадкой.

Включив это в наш решатель, мы можем быстро найти решение:

                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,4,_,_,_,_],
                        [_,_,3,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_]]).
            problem(2, Rows), sudoku(Rows), maplist(label, Rows), maplist(portray_clause, Rows).

            [9, 4, 8, 3, 7, 2, 6, 1, 5].
            [3, 7, 2, 6, 1, 5, 9, 4, 8].
            [6, 1, 5, 9, 4, 8, 3, 7, 2].
            [4, 8, 3, 7, 2, 6, 1, 5, 9].
            [7, 2, 6, 1, 5, 9, 4, 8, 3].
            [1, 5, 9, 4, 8, 3, 7, 2, 6].
            [8, 3, 7, 2, 6, 1, 5, 9, 4].
            [2, 6, 1, 5, 9, 4, 8, 3, 7].
            [5, 9, 4, 8, 3, 7, 2, 6, 1].

Поправь еще раз! Одним из полезных аспектов решателя Prolog является то, что он может найти все правильные решения для любой подсказки. В Prolog REPL, когда решение найдено, вы можете нажать, ;чтобы перейти к следующему решению. В обеих вышеупомянутых головоломках подсказка имеет ровно одно правильное решение. По определению, головоломки Судоку должны иметь только одно решение, так что эти головоломки действительно действительны.

Создание головоломок

Теперь, когда у нас есть решатель проблем Miracle Sudoku, можем ли мы создать некоторые из наших собственных? Чтобы проверить это, я запросил решатель с полностью пустой доской:

                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,_,_,_,_]]).
            problem(3, Rows), sudoku(Rows), maplist(label, Rows), maplist(portray_clause, Rows).

И результат? Ну ... ничего. Просто звук поклонников моего ноутбука вращается. Я думаю, что способ, которым я инструктирую Prolog для поиска решений, слишком наивен, чтобы создавать доски без подсказок. Моя ставка заключается в том, что maplist(label, Rows)выполняется поиск «угадать и проверить» по всему пространству, что слишком медленно для создания досок без ограничения намека.

Немного разочаровывает отсутствие возможности создавать новые доски с помощью этого решателя. Возможно, кто-то с большим знанием Prolog сможет реализовать более эффективное решение.

Отступление: Пикат

Во время написания этой статьи я наткнулся на решатель Miracle Sudoku Хакана Кьеллерстранда, написанный на Picat, языке программирования на основе логики, о котором я никогда раньше не слышал.

Решатель Хакана намного быстрее моего - он настолько быстр, что может генерировать все возможные доски Чудо Судоку примерно за то время, которое у меня уходит на решение одного экземпляра головоломки. Удивительно, но есть только 72 платы решений, которые соответствуют ограничениям Miracle Sudoku [2]. Я знаю о Пикате даже меньше, чем о Prolog, поэтому я не уверен, что решение Хакана намного быстрее, чем мое.

Я бы порекомендовал прочитать исходный код решателя Picat. Поскольку решение Хакана очень быстрое, он может открыть для себя еще пару интересных свойств головоломки Miracle Sudoku:

  • Минимальное количество подсказок, необходимых для однозначного определения доски решений, равно 2.
  • Доски с одной размещенной подсказкой всегда имеют 8 решений - независимо от того, какая цифра подсказки или где она размещена.
  • Есть много, много действительных подсказок с двумя цифрами. Например, существует 2320 способов разместить буквы 1и А 2на доске, что приводит к уникальному решению. Поскольку существует всего 72 уникальных платы для решений, у вас не хватит интересных решений, прежде чем не хватит подсказок.

Вывод

У меня не так много применений Prolog в моей повседневной работе, но интересно работать на (относительно) непонятном языке, подобном этому, когда он хорошо подходит для этой задачи. Я сделал пометку, чтобы тоже проверить Пиката. Сайт Хакана имеет множество примеров проблем с решениями.

Я также понятия не имел, что существуют производители головоломок, расширяющие традиционный судоку - на его странице в Википедии есть более десятка вариантов. В канале CrackingTheCryptic на Youtube есть достаточно корма для вариантов головоломки, для которых можно написать решатели.

Смотрите также

Обновления

Согласно этому комментарию Триски, посвященному обсуждению Hacker News, мы можем существенно ускорить решение, изменив стратегию поиска, которую использует Prolog:

                sudoku(Rows),
                append(Rows, Vs),
                labeling([ff], Vs),
                maplist(portray_clause, Rows).

Результат по-прежнему намного медленнее, чем решение Picat, но такой подход к маркировке позволяет нам создавать новые платы! Документы SWIPL for labelingсодержат дополнительную информацию о настройке стратегии поиска.

Теперь мы также можем проверить, что число наших решений соответствует решателю Picat, запросив Prolog для всех допустимых решений:

               (problem(3, Rows),
                 sudoku(Rows),
                 append(Rows, Vs),
                 labeling([ff], Vs)),
               Count).

Результат 72, как и ожидалось.

Более ранняя версия этого поста использовалась all_distinct вместо all_different. Опять же, согласно комментарию, связанному выше с помощью triska (спасибо!), Мы можем улучшить производительность поиска, изменив способ формирования ограничений.

  1. https://en.wikipedia.org/wiki/Matmatics_of_Sudoku#Sudoku_with_rectangular_regions
  2. Смотрите полный список здесь.
Was this helpful?

Result: 0, total votes: 0

I'm Vladimir, your guide in the expansive world of technology journalism, with a special focus on GPS technologies and mapping. My journey in this field extends over twenty fruitful years, fueled by a profound passion for technology and an insatiable curiosity to explore its frontiers.