3 ms·
This is a solver in 11 lines of AMPL (http://www.ampl.com http://www.ampl.com), a modeling language for optimization problems: param n:=9; set N := 1..n;
by merraksh 14y ago
This is a solver in 11 lines of AMPL (http://www.ampl.com http://www.ampl.com), a modeling language for optimization problems:
param n:=9;
set N := 1..n;
var x {N,N,N} binary;
param fix {N,N} integer;
minimize obj: x [1,1,1];
assign {i in N, j in N}: sum {k in N} x [i,j,k] = 1;
row {i in N, k in N}: sum {j in N} x [i,j,k] = 1;
col {j in N, k in N}: sum {i in N} x [i,j,k] = 1;
cell {c1 in 0..2, c2 in 0..2, k in N}:
sum {i in (c1*3+1)..(c1*3+3), j in (c2*3+1)..(c2*3+3)} x [i,j,k] = 1;
fixit {i in N, j in N: fix [i,j] != 0}: x [i,j,fix[i,j]] = 1;
data;
param fix:
1 2 3 4 5 6 7 8 9 :=
1 1 0 0 0 0 7 0 9 0
2 0 3 0 0 2 0 0 0 8
3 0 0 9 6 0 0 5 0 0
4 0 0 5 3 0 0 9 0 0
5 0 1 0 0 8 0 0 0 2
6 6 0 0 0 0 4 0 0 0
7 3 0 0 0 0 0 0 1 0
8 0 4 0 0 0 0 0 0 7
9 0 0 7 0 0 0 3 0 0;
You can solve it by submitting it on line at, for instance,
http://neos.mcs.anl.gov/neos/solvers/milp:scip/AMPL.html http://neos.mcs.anl.gov/neos/solvers/milp:scip/AMPL.html (just save it to a file and submit it in the "AMPL model" field).
This is an optimization model of an assignment problem. Certain problems should be approached not only with the right language, but also with the right tool. Optimization solvers are not always the best tool for feasibility problems, but this solver (of the branch-and-bound type) can also solve difficult sudoku instances.
[Edit: clarification]