Программирование с ограничениями (CP)

Судоку — типичная задача программирования с ограничениями. У вас есть набор переменных (полей в сетке), каждая из которых имеет домен (здесь цифры от 0 до 9), и набор ограничений над этими переменными (тот факт, что число встречается только один раз в строке, столбце, блоке,...).

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

При выборе вы выбираете значение для определенной переменной. Хорошая стратегия состоит в том, чтобы выбрать переменную с небольшим количеством оставшихся возможных значений. Затем вы снова размножаетесь и, возможно, делаете другой выбор и так далее.

Возможно, ваша программа обнаружит, что выбор был неправильным: она сделает область определения одной или нескольких переменных пустой. В этом случае вы возвращаетесь: вы отменяете выбор, который вы сделали ранее (а также распространение, которое было сделано после этого выбора), и выбираете другое значение.

Этот ответ, очевидно, не направлен на предоставление углубленного обзора темы, но страница Википедии может дать лучший обзор и указатели на дополнительную информацию.

Существуют решатели программирования с ограничениями, такие как ECLiPSe (не IDE), MiniZinc и т. д., где можно просто определить переменные, домены и ограничения.

Решение проблемы с ECLiPSe

На веб-сайте ECLiPSe вы можете найти модель для судоку. Учитывая, что вы прочитали некоторую документацию по ECLiPSe, вы можете превратить этот файл в модель для мульти-судоку. Я внес несколько небольших изменений, в результате которых появилось следующее быстрое и грязное решение:

% credits to Joachim Schimpf for his model of sudoku
% http://eclipseclp.org/examples/sudoku.ecl.txt
:- lib(ic).
:- import alldifferent/1 from ic_global.

solve(ProblemName) :-
    problem(ProblemName,BA,BB),
    multi_sudoku(3,BA,BB),
    print_board(BA),
    print_board(BB).

multi_sudoku(N,BA,BB) :-
    sudoku(N,BA,VA),
    sudoku(N,BB,VB),
    N2 is N*N,
    Inc is N2-N,
    (multifor([I,J],1,N,1),param(BA,BB,Inc) do
        BA[I+Inc,J+Inc] #= BB[I,J]
    ),
    append(VA,VB,Vars),
    labeling(Vars).

sudoku(N,Board,Vars) :-
    N2 is N*N,
    dim(Board,[N2,N2]),
    Board[1..N2,1..N2] :: 1..N2,
    ( for(I,1,N2), param(Board,N2) do
        Row is Board[I,1..N2],
        alldifferent(Row),
        Col is Board[1..N2,I],
        alldifferent(Col)
    ),
    ( multifor([I,J],1,N2,N), param(Board,N) do
        ( multifor([K,L],0,N-1), param(Board,I,J), foreach(X,SubSquare) do
        X is Board[I+K,J+L]
        ),
        alldifferent(SubSquare)
    ),
    term_variables(Board, Vars).


print_board(Board) :-
    dim(Board, [N,N]),
    ( for(I,1,N), param(Board,N) do
        ( for(J,1,N), param(Board,I) do
            X is Board[I,J],
        ( var(X) -> write("  _") ; printf(" %2d", [X]) )
        ), nl
    ), nl.


%----------------------------------------------------------------------
% Sample data
%----------------------------------------------------------------------

problem(1, [](
    [](_, _, _, _, 6, _, _, _, _),
    [](_, _, _, 4, _, 9, _, _, _),
    [](_, _, 9, 7, _, 5, 1, _, _),
    [](_, 5, 2, _, 7, _, 8, 9, _),
    [](9, _, _, 5, _, 2, _, _, 4),
    [](_, 8, 3, _, 4, _, 7, 2, _),
    [](_, _, _, 2, _, 8, _, _, _),
    [](_, _, _, 6, _, 4, _, _, _),
    [](_, _, _, _, 5, _, _, _, _)
           ),
           [](
    [](_, _, _, _, 3, _, _, _, _),
    [](_, _, _, 8, _, 7, _, _, _),
    [](_, _, _, 1, _, 6, 3, _, _),
    [](_, 9, 8, _, _, _, 1, 2, _),
    [](2, _, _, _, _, _, _, _, 3),
    [](_, 4, 3, _, _, _, 6, 5, _),
    [](_, _, 7, 3, _, 5, 9, _, _),
    [](_, _, _, 4, _, 2, _, _, _),
    [](_, _, _, _, 6, _, _, _, _)
           )
    ).

Я «позаимствовал» модель судоку у Иоахима Шимпфа, так что ему спасибо. Кроме того, обратите внимание, что этот ответ не рекомендует использовать ECLiPSe вместо другого инструмента. Я просто лучше знаком с набором инструментов Prolog, когда дело доходит до программирования в ограничениях. Но если вы больше увлекаетесь C++, Gecode справится с задачей примерно с такой же (или даже лучшей) производительностью.

который генерирует вывод:

ECLiPSe Constraint Logic Programming System [kernel]
Kernel and basic libraries copyright Cisco Systems, Inc.
and subject to the Cisco-style Mozilla Public Licence 1.1
(see legal/cmpl.txt or http://eclipseclp.org/licence)
Source available at www.sourceforge.org/projects/eclipse-clp
GMP library copyright Free Software Foundation, see legal/lgpl.txt
For other libraries see their individual copyright notices
Version 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015
[eclipse 1]: solve(1).
lists.eco  loaded in 0.00 seconds
WARNING: module 'ic_global' does not exist, loading library...
queues.eco loaded in 0.00 seconds
ordset.eco loaded in 0.01 seconds
heap_array.eco loaded in 0.00 seconds
graph_algorithms.eco loaded in 0.03 seconds
max_flow.eco loaded in 0.00 seconds
flow_constraints_support.eco loaded in 0.00 seconds
ic_sequence.eco loaded in 0.01 seconds
ic_global.eco loaded in 0.07 seconds
  2  1  4  8  6  3  9  5  7
  8  7  5  4  1  9  2  6  3
  6  3  9  7  2  5  1  4  8
  4  5  2  3  7  1  8  9  6
  9  6  7  5  8  2  3  1  4
  1  8  3  9  4  6  7  2  5
  5  4  1  2  3  8  6  7  9
  7  2  8  6  9  4  5  3  1
  3  9  6  1  5  7  4  8  2

  6  7  9  5  3  4  2  8  1
  5  3  1  8  2  7  4  6  9
  4  8  2  1  9  6  3  7  5
  7  9  8  6  5  3  1  2  4
  2  6  5  7  4  1  8  9  3
  1  4  3  2  8  9  6  5  7
  8  2  7  3  1  5  9  4  6
  9  1  6  4  7  2  5  3  8
  3  5  4  9  6  8  7  1  2

Моей машине потребовалось примерно 0,11 секунды. Кроме того, всего имеется 60 допустимых решений.

Последние две «матрицы» показывают решение для двух судоку. Как вы можете видеть (я не проверял это полностью), они имеют общий блок (один и тот же вывод), и все ограничения судоку действительны. Более удобное представление решения показано ниже:

+-----+-----+-----+
|2 1 4|8 6 3|9 5 7|
|8 7 5|4 1 9|2 6 3|
|6 3 9|7 2 5|1 4 8|
+-----+-----+-----+
|4 5 2|3 7 1|8 9 6|
|9 6 7|5 8 2|3 1 4|
|1 8 3|9 4 6|7 2 5|
+-----+-----+-----+-----+-----+
|5 4 1|2 3 8|6 7 9|5 3 4|2 8 1|
|7 2 8|6 9 4|5 3 1|8 2 7|4 6 9|
|3 9 6|1 5 7|4 8 2|1 9 6|3 7 5|
+-----+-----+-----+-----+-----+
            |7 9 8|6 5 3|1 2 4|
            |2 6 5|7 4 1|8 9 3|
            |1 4 3|2 8 9|6 5 7|
            +-----+-----+-----+
            |8 2 7|3 1 5|9 4 6|
            |9 1 6|4 7 2|5 3 8|
            |3 5 4|9 6 8|7 1 2|
            +-----+-----+-----+

Я ничего не знаю о библиотеке программирования с ограничениями в Python и не знаю о переносе ECLiPSe на Python. Но мой опыт показывает, что все современные языки программирования имеют такой инструмент.

Преимущество использования инструментов программирования с ограничениями, таких как ECLiPSe, Gecode,... прежде всего заключается в том, что вам нужно всего лишь указать вам не о чем беспокоиться, как решить вашу проблему. Кроме того, в таких библиотеках реализованы 30-летние исследования программирования с ограничениями: они чрезвычайно оптимизированы, используют ограничения и структуры так, как большинство людей не могут себе представить, и с меньшей вероятностью содержат ошибки (по сравнению с алгоритмом, созданным на заказ). Кроме того, если будут найдены новые стратегии, алгоритмы и т. д., обновление ECLiPSe приведет к ускорению обработки модели.

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

Другие методы

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

Другой подход заключается в использовании генетического алгоритма. Которая основана на биологической эволюции. Генетические алгоритмы являются частью эволюционных алгоритмов и, следовательно, имеют аналогию «фитнес-функция». Правильное решение находится с помощью рекомбинации, отбора и мутации.

Основная концепция состоит в том, чтобы случайным образом инициализировать ряд решений «индивидуально», состоящих из «хромосом» (конечно, решения могут быть ошибочными). Определите «фитнес-функцию», которая оценивает качество каждого человека в текущем «поколении». Возьмите с большей вероятностью особи с лучшей приспособленностью, чтобы рекомбинировать их в «дочерний» раствор и с малой вероятностью мутировать некоторых особей в новом поколении. Повторяйте, пока некоторые критерии (max_iteration_count, valid_solution_found) не станут истинными.

Чтобы подогнать генетический алгоритм к вашей проблеме. Вы можете сделать что-то вроде следующего. Создайте для каждой судоку 3x3 или 9x9 локальное правильное решение. Это хромосомы. Поместите их в одну структуру данных. Это индивидуум. Создайте группу из них, чтобы сформировать поколение. Оценивайте каждого человека по ограничениям, которые он нарушает. Вычислите соответствующую вероятность. Рекомбинируйте особей, мутируйте некоторые хромосомы, повторите.

Вы можете видеть это как комбинацию локальной и глобальной оптимизации. Поскольку вам понадобится какой-то жадный алгоритм (или что-то еще, что вы хотите использовать для решения локального судоку), чтобы найти локальный, и GA, чтобы найти общий глобальный оптимум. Я думаю, что не имеет смысла использовать только GA и пытаться решить эту проблему. Недавно я применил ГА к комбинаторной задаче, и без локальной оптимизации результаты в большинстве случаев были довольно ужасными.

Однако хорошая вещь в ГА заключается в том, что они делают большие шаги в начале поиска, сходясь к оптимуму, но по-прежнему охватывают большие части пространства поиска. Но, как всегда с советником, настройка параметров может быть довольно сложной.