sudoku.m
函数数独(文件名)% 2023年版权,Gurobi优化,LLC * / % %数独的例子狗万app足彩。% % 9 x9网格数独板,这是进一步分为3 x3网格% 3 x3的网格。网格中的每个单元格必须采取一个值从0到9。%没有两个网格细胞在相同的行,列,或3 x3次网格可能需要%值相同。% % MIP配方,二进制变量x (i, j, v)表明是否%细胞< i, j >价值“v”。约束如下:% 1。每个单元格必须采取一个值(sum_v x (i, j, v) = 1) % 2。每个值完全使用一次每一行(sum_i x (i, j, v) = 1) % 3。每个值是完全一次使用每列(sum_j x (i, j, v) = 1) % 4。每个值是完全一次使用/ 3 x3的次网格(sum_grid x (i, j, v) = 1) % %输入数据集对于这个示例中可以找到例子/数据/数独*。 % SUBDIM = 3; DIM = SUBDIM*SUBDIM; fileID = fopen(filename); if fileID == -1 fprintf('Could not read file %s, quit\n', filename); return; end board = repmat(-1, DIM, DIM); for i = 1:DIM s = fgets(fileID, 100); if length(s) <= DIM fprintf('Error: not enough board positions specified, quit\n'); return; end for j = 1:DIM if s(j) ~= '.' board(i, j) = str2double(s(j)); if board(i,j) < 1 || board(i,j) > DIM fprintf('Error: Unexpected character in Input line %d, quit\n', i); return; end end end end % Map X(i,j,k) into an index variable in the model nVars = DIM * DIM * DIM; % Build model model.vtype = repmat('B', nVars, 1); model.lb = zeros(nVars, 1); model.ub = ones(nVars, 1); for i = 1:DIM for j = 1:DIM for v = 1:DIM var = (i-1)*DIM*DIM + (j-1)*DIM + v; model.varnames{var} = sprintf('x[%d,%d,%d]', i, j, v); end end end % Create constraints: nRows = 4 * DIM * DIM; model.A = sparse(nRows, nVars); model.rhs = ones(nRows, 1); model.sense = repmat('=', nRows, 1); Row = 1; % Each cell gets a value */ for i = 1:DIM for j = 1:DIM for v = 1:DIM if board(i,j) == v model.lb((i-1)*DIM*DIM + (j-1)*DIM + v) = 1; end model.A(Row, (i-1)*DIM*DIM + (j-1)*DIM + v) = 1; end Row = Row + 1; end end % Each value must appear once in each row for v = 1:DIM for j = 1:DIM for i = 1:DIM model.A(Row, (i-1)*DIM*DIM + (j-1)*DIM + v) = 1; end Row = Row + 1; end end % Each value must appear once in each column for v = 1:DIM for i = 1:DIM for j = 1:DIM model.A(Row, (i-1)*DIM*DIM + (j-1)*DIM + v) = 1; end Row = Row + 1; end end % Each value must appear once in each subgrid for v = 1:DIM for ig = 0: SUBDIM-1 for jg = 0: SUBDIM-1 for i = ig*SUBDIM+1:(ig+1)*SUBDIM for j = jg*SUBDIM+1:(jg+1)*SUBDIM model.A(Row, (i-1)*DIM*DIM + (j-1)*DIM + v) = 1; end end Row = Row + 1; end end end % Save model gurobi_write(model, 'sudoku_m.lp'); % Optimize model params.logfile = 'sudoku_m.log'; result = gurobi(model, params); if strcmp(result.status, 'OPTIMAL') fprintf('Solution:\n'); for i = 1:DIM for j = 1:DIM for v = 1:DIM var = (i-1)*DIM*DIM + (j-1)*DIM + v; if result.x(var) > 0.99 fprintf('%d', v); end end end fprintf('\n'); end else fprintf('Problem was infeasible\n') end
