matrix - 如何解决这个 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

据我所知，没有比使用回溯方法更有效地解决这个特定问题的直接算法。

不过，与简单地枚举所有可能的解决方案相比，您可以更智能地执行此操作。一种有效的方法是约束编程 (CP)(或派生范例，例如约束逻辑编程 (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 问题。