我正在研究算法，最近发现了一个有趣的挑战。
它会给我们一些行/列，我们的任务是用整数 1~N 填充表格，它只显示一次，并且它们的行和列总和等于给定的行/列。
挑战简单示例：
[ ] [ ] [ ] 13
[ ] [ ] [ ] 8
[ ] [ ] [ ] 24
14 14 17
answer:
[2] [6] [5] 13
[3] [1] [4] 8
[9] [7] [8] 24
14 14 17
谢谢
据我所知，没有比使用回溯方法更有效地解决这个特定问题的简单算法。
但是，您可以比简单地枚举所有可能的解决方案更智能地做到这一点。一种有效的方法是约束编程（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]).
该程序模糊地基于我对 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。
哦，当这些小优化问题出现时，我只是喜欢它。他们总是让我想起在我第一年的时候，我做了一个可以解决数独问题的东西，并从中获得了很多乐趣！您可能会猜到从那以后我解决了多少数独问题:)。
现在，您的问题是ILP (Integer Linear Program)。甚至在您阅读那篇文章之前，您就应该注意ILP很难。将解决方案空间限制在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 的求解器也能很好地工作。如果不是这样，我认为我的措辞比 Willem Van Onsem 已经拥有的更好，我想指导您参考他的实施答案。
下面是另一个约束规划模型，使用与Willem Van Onsem 的解决方案类似的方法，即使用全局约束“all_different”，这是一种确保矩阵中的数字只分配一次的有效方法。（“全局约束”的概念在 CP 中非常重要，并且有很多研究发现不同类型的常见约束的快速实现。）
这是一个 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
----------
我认为回溯算法在这里可以很好地工作。
尽管回溯仍然是“蛮力”，但在一般情况下它可以非常快。例如，用回溯法求解数独通常只需要 1000-10000 次迭代（考虑到 O 复杂度为 O(9^n)，其中 n 是空白空间，这真的很快，因此平均数独有大约 9^60 种可能性，其中平均计算机需要数年才能完成）。
这个任务有很多规则（数字的唯一性和行/列的总和），这对于回溯非常有用。更多规则 = 在每一步之后进行更多检查，并丢弃无法解决问题的分支。
这可以提供帮助：https ://en.wikipedia.org/wiki/Sudoku_solving_algorithms