Как решить эту головоломку матрицы ILP/CP

Question

Я изучаю алгоритмы и недавно нашел интересную задачу.

Это даст нам несколько строк/столбцов, и наша задача - заполнить таблицу целым числом 1 ~ N, которое отображается только один раз, а их суммы строк и столбцов равны заданной строке/столбцу.

Задача простой пример:

[ ] [ ] [ ] 13 
    [ ] [ ] [ ] 8 
    [ ] [ ] [ ] 24 
    14 14 17 

answer: 

    [2] [6] [5] 13 
    [3] [1] [4] 8 
    [9] [7] [8] 24 
    14 14 17 

Благодаря

Answer 1

Я думаю, что возвратами alghorithm будет работать очень хорошо здесь.

Наверху обратная связь по-прежнему «грубая сила», она может быть очень быстрой в среднем случае. Например, решение SUDOKU с обратным трассированием обычно занимает всего 1000-10000 итераций (что очень быстро, учитывая, что O-сложность O (9^n), где n - пустые пространства, поэтому средняя судоку имеет около ~ 9^60 возможностей, что потребуется несколько лет на среднем компьютере для завершения).

Эта задача имеет множество правил (уникальность чисел и суммы в строках/столбцах), что неплохо для bactracking. Больше правил = больше проверки после каждого шага и отбрасывания ветвей, которые не могут принести решение.

Это может помочь: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms

Answer 2

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

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

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

Вы можете, например, использовать ECLIPSE (а не IDE, а средство программирования ограничение логики) для этого:

:- lib(ic). 
:- import alldifferent/1 from ic_global. 
:- import sumlist/2 from ic_global. 

solve(Problem) :- 
    problem(Problem,N,LA,LB), 
    puzzle(N,LA,LB,Grid), 
    print_Grid(Grid). 

puzzle(N,LA,LB,Grid) :- 
    N2 is N*N, 
    dim(Grid,[N,N]), 
    Grid[1..N,1..N] :: 1..N2, 
    (for(I,1,N), param(N,Grid,LA,LB) do 
     Sc is nth1(I,LA), 
     Lc is Grid[1..N,I], 
     sumlist(Lc,Sc), 
     Sr is nth1(I,LB), 
     Lr is Grid[I,1..N], 
     sumlist(Lr,Sr) 
    ), 
    term_variables(Grid,Vars), 
    alldifferent(Vars), 
    labeling(Vars). 

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

nth1(1,[H|_],H) :- !. 
nth1(I,[_|T],H) :- 
    I1 is I-1, 
    nth1(I1,T,H). 

problem(1,3,[14,14,17],[13,8,24]). 

Программа основана на неопределенно my implementation for multi-sudoku. Теперь вы можете решить эту проблему с помощью Eclipse:

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.00 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.05 seconds 
    2 5 6 
    3 1 4 
    9 8 7 


Yes (0.05s cpu, solution 1, maybe more) ? ; 
    5 2 6 
    1 3 4 
    8 9 7 


Yes (0.05s cpu, solution 2, maybe more) ? ; 
    2 6 5 
    3 1 4 
    9 7 8 


Yes (0.05s cpu, solution 3, maybe more) ? ; 
    3 6 4 
    2 1 5 
    9 7 8 


Yes (0.05s cpu, solution 4, maybe more) ? ; 
    6 2 5 
    1 3 4 
    7 9 8 


Yes (0.05s cpu, solution 5, maybe more) ? ; 
    6 3 4 
    1 2 5 
    7 9 8 


Yes (0.05s cpu, solution 6, maybe more) ? ; 
    2 6 5 
    4 1 3 
    8 7 9 


Yes (0.05s cpu, solution 7, maybe more) ? ; 
    4 6 3 
    2 1 5 
    8 7 9 


Yes (0.05s cpu, solution 8, maybe more) ? 
    6 2 5 
    1 4 3 
    7 8 9 


Yes (0.05s cpu, solution 9, maybe more) ? ; 
    6 4 3 
    1 2 5 
    7 8 9 


Yes (0.05s cpu, solution 10, maybe more) ? ; 

No (0.06s cpu) 

Один просто запрашивает solve(1) и ограничение инструмент логического программирования делает все остальное. Таким образом, существует в общей сложности 10 решений.

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

Answer 3

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

---

Теперь, ваша проблема ILP (Integer Linear Program). Еще до того, как вы прочитаете эту статью, вы должны принять к сведению, что ILP - hard. Ограничение пространства решений на N или Z сильно ограничивает и часто такое решение не существует!

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

Minimise 0 (arbitrary objective function) 

условии,

x1 + x2 + x3 = 13 
x4 + x5 + x6 = 8 
x7 + x8 + x9 = 24 

x1 + x4 + x7 = 14 
x2 + x5 + x8 = 14 
x3 + x6 + x9 = 17 

И

x_i in N, x_i distinct. 

В матричной форме эти уравнения,

|1 1 1 0 0 0 0 0 0| 
    |0 0 0 1 1 1 0 0 0| 
A = |0 0 0 0 0 0 1 1 1| 
    |1 0 0 1 0 0 1 0 0| 
    |0 1 0 0 1 0 0 1 0| 
    |0 0 1 0 0 1 0 0 1| 

И

|13| 
    | 8| 
B = |24| 
    |14| 
    |14| 
    |17| 

Такое, что ограничения сводятся к A*x = B. Таким образом, проблема, которую мы хотим решить теперь то же самое можно записать в виде,

Minimise 0 

условии,

A * x = B 

И

x in N^7, x_i distinct. 

ли это вглядеться вам? Если нет, подумайте об этом: реальная линия огромна, и на этой линии время от времени это крошечная точка. Это целое число. Нам нужны некоторые из них. Мы не знаем, какие из них. По сути, идеальная аналогия искала бы иглу в стоге сена.

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

Я хочу дать вам рабочий код, но я не знаю вашего предпочтительного выбора языка/инструментария. Если это просто подход для любителей, даже решатель Excel будет работать красиво. Если это не так, я не думаю, что я мог бы сформулировать это лучше, чем у Виллема Ван Насема, и я хотел бы направить вас к его ответу на реализацию.

Answer 4

Ниже приведена другая модель программирования Constraint, использующая аналогичный подход, такой как решение Willem Van Onsem, т. Е. Использование глобального ограничения «all_different», что является эффективным методом обеспечения того, чтобы числа в матрице присваивались только один раз. (Концепция «глобальных ограничений» очень важна в СР, и есть много исследований, которые быстро обнаруживают быстрые реализации для разных общих ограничений.)

Вот модель MiniZinc: http://hakank.org/minizinc/matrix_puzzle.mzn

include "globals.mzn"; 
% parameters 
int: rows; 
int: cols; 
array[1..rows] of int: row_sums; 
array[1..cols] of int: col_sums; 

% decision variables 
array[1..rows,1..cols] of var 1..rows*cols: x; 

solve satisfy; 

constraint 
    all_different(array1d(x)) /\ 
    forall(i in 1..rows) (
    all_different([x[i,j] | j in 1..cols]) /\ 
    sum([x[i,j] | j in 1..cols]) = row_sums[i] 
) 
    /\ 
    forall(j in 1..cols) (
    all_different([x[i,j] | i in 1..rows]) /\ 
    sum([x[i,j] | i in 1..rows]) = col_sums[j] 
); 

    output [ 
    if j = 1 then "\n" else " " endif ++ 
     show_int(2,x[i,j]) 
    | i in 1..rows, j in 1..cols 
    ]; 

    % Problem instance 
    rows = 3; 
    cols = 3; 
    row_sums = [13,8,24]; 
    col_sums = [14,14,17]; 

Вот первые два (10) решений:

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

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

Дополнительный комментарий: Забавная вещь с CP - а также важная концепция - состоит в том, что можно создать новые экземпляры проблем, используя почти идентичную модель: http://hakank.org/minizinc/matrix_puzzle2.mzn

Единственная разница заключается в том, следующие строки, т. е. изменить «row_sums» и «col_sums» на переменные решения и прокомментировать подсказки.

array[1..rows] of var int: row_sums; % add "var" 
    array[1..cols] of var int: col_sums; % add "var" 

    % ... 

    % row_sums = [13,8,24]; 
    % col_sums = [14,14,17]; 

Вот три сгенерированные проблемные случаи (от 9 = 362880 можно!):

row_sums: [21, 15, 9] 
    col_sums: [19, 15, 11] 

    5 9 7 
    8 4 3 
    6 2 1 
    ---------- 
    row_sums: [20, 16, 9] 
    col_sums: [20, 14, 11] 

    5 8 7 
    9 4 3 
    6 2 1 
    ---------- 
    row_sums: [22, 14, 9] 
    col_sums: [18, 15, 12] 

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