Multi-судоку AI подход

Question

Я концептуализации решатель для варианта судоку называется мульти-судоку, где несколько плат перекрываются следующим образом:

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

Я не уверен, как я должен думать об этом. У кого-нибудь есть намеки/концептуальные подсказки? Кроме того, если на ум приходят какие-то темы в искусственном интеллекте, я тоже хотел бы услышать их.

Answer 1

программирование Constraint (CP)

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

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

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

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

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

Есть ограничение программирования решателей как ECLIPSE (не IDE), MiniZinc и т.д., где можно просто определить переменные, домены и ограничения.

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

На сайте ECLIPSE, вы можете найти a model for sudoku. Учитывая, что вы прочитали документацию о 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, _, _, _, _) 
      ) 
    ). 

Я «позаимствовал» модель судоку от Joachim Шимпф, поэтому кредиты ему.Кроме того, обратите внимание, что этот ответ не советует использовать 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 действующих решений.

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

+-----+-----+-----+ 
|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 ... прежде всего, что у вас есть только указать ваша проблема, как она решается что-то вы не» t беспокоиться. Кроме того, такие библиотеки реализуют 30 лет исследований в программировании ограничений: они чрезвычайно оптимизированы, используют ограничения и структуры таким образом, что большинство людей не могут себе представить и с меньшей вероятностью будут содержать ошибки (чем алгоритм, созданный на заказ). Кроме того, если найдены новые стратегии, алгоритмы, ..., обновление ECLiPSe приведет к более быстрой обработке модели.

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

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

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

Answer 2

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

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

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

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

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