Решение судоку на Prolog

      Комментарии к записи Решение судоку на Prolog отключены

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 3 мес. назад.

  • Автор
    Сообщения
  • #2571

    questioner
    Участник

    Здравствуйте, у меня есть описание задачи и исходный код, помогите мне в нем разобраться:

    Судоку — популярная головоломка с числами.
    Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.

    Сложность судоку зависит от количества изначально заполненных клеток и от методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.

    :- use_module(library(clpfd)).
     
    sudoku(Rows) :-  
      append(Rows, Vs), Vs ins 1..9,
      maplist(all_distinct, Rows),
      transpose(Rows, Columns),     
      maplist(all_distinct, Columns),     
      Rows = [A,B,C,D,E,F,G,H,I],     
      blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),     
      maplist(label, Rows).      
     
    blocks([], [], []).       
    blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
      all_distinct([A,B,C,D,E,F,G,H,I]),      
      blocks(Bs1, Bs2, Bs3).
    
    sudoku(1, [[6,_,7,_,_,_,_,3,2],
                [1,4,_,_,_,3,5,9,_],
                [_,8,_,_,5,4,_,_,1],
                [_,1,8,6,_,5,_,_,_],
                [_,_,6,_,9,_,8,_,_],
                [_,_,_,8,_,2,7,1,_],
                [8,_,_,4,1,_,_,6,_],
                [_,6,1,3,_,_,_,5,7],
                [9,2,_,_,_,_,1,_,4]]).

    Вложения:
  • #2573

    В коде используется библиотека CLPFD (Constraint Logic Programming over Finite Domains). Она подключается в первой строке с помощью команды:
    :- use_module(library(clpfd)).
    Используемые предикаты из библиотеки:

    1. append — Объединение списков
    2. all_distinct — Истина, если все числа в списке имеют разные значения
    3. maplist — Истина, если операция была успешно применена ко всем элементам списка
    4. transpose — Транспонирование
    5. label — Позволяет построить только одно конкретное значение в том случае, если есть более одного решения

    Программа работает по следующему алгоритму:

    • Предикат Sudoku(Rows) принимает матрицу, представленную в виде набора списков (строк).
    • Строки объединяются функцией append.
    • С помощью maplist вызывается предикат all_distinct, который возвращает истину в случае, если числа в строке (элементе Rows) встречаются один раз.
    • Матрица транспонируется чтобы заменить строки столбцами, с транспонированной матрицей еще раз выполняется проверка (фактически проверятся столбцы исходной матрицы).
    • С помощью предиката blocks матрица преобразуется в блоки 3×3 и выполняется проверка уникальности чисел в блоке.
    • Снова используется maplist для вызова предиката label для строк. label гарантирует, что все числа имеют одно конкретное значение, но только в том случае, если есть более одного решения судоку

    Алгоритм работы функции blocks:

    • предикат истинен, если он получает три пустых списка в качестве входных. Это точка выхода для рекурсии;
    • blocks имеет непустое значение. С помощью оператора разделения списка на голову и хвост | разбиваются данные строк в первых трех элементах и хвосте, которые используются позже;
    • имеется получился блок 3×3, включающий три элемента из каждой строки, изначально взятой из blocks в sudoku. Опять происходит проверка, что число повторяется только один раз;
    • рекурсивно обрабатывается остальная часть списков (пока не получится пустых списков).

Для ответа в этой теме необходимо авторизоваться.