Начальная проблема

Вот является матрица данных B из подсказок. Первая строка, B(1,2,2), средняя строка 1, столбец 2 имеет подсказку 2. Вторая строка, B(1,5,3), средняя строка 1, столбец 5 имеет подсказку 3. Вот целый матричный B.

B = [1,2,2;
    1,5,3;
    1,8,4;
    2,1,6;
    2,9,3;
    3,3,4;
    3,7,5;
    4,4,8;
    4,6,6;
    5,1,8;
    5,5,1;
    5,9,6;
    6,4,7;
    6,6,5;
    7,3,7;
    7,7,6;
    8,1,4;
    8,9,8;
    9,2,3;
    9,5,4;
    9,8,2];

drawSudoku(B) % For the listing of this program, see the end of this example.

Эта проблема и альтернативный метод решения MATLAB®, были показаны в Углу Клива в 2 009.

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

Этот подход особенно прост, потому что вы не даете алгоритм решения. Только выразите правила Судоку, выразите подсказки как ограничения на решение, и затем MATLAB производит решение.

Бинарный подход целочисленного программирования

Ключевая идея состоит в том, чтобы преобразовать проблему от квадрата 9 9 сетка к кубическим 9 9 9 массивами двоичных значений (0 или 1). Думайте о кубическом массиве, как являющемся 9 квадратными сетками, сложенными друг на друге, где каждый слой соответствует целому числу от 1 до 9. Главная сетка, квадратный слой массива, имеет 1 везде, где решение или подсказка имеют 1. Второй слой имеет 1 везде, где решение или подсказка имеют 2. Девятый слой имеет 1 везде, где решение или подсказка имеют 9.

Эта формулировка точно подходит для бинарного целочисленного программирования.

Целевая функция не нужна здесь и может также быть постоянным термином 0. Проблема состоит в том, чтобы действительно только найти возможное решение, означая то, которое удовлетворяет всем ограничениям. Однако для связи, врывающейся внутренности решателя целочисленного программирования, давая увеличенную скорость решения, используют непостоянную целевую функцию.

Выразите правила для судоку как ограничения

Предположим решение $$x$$ представлен в 9 9 9 двоичными массивами. Какие свойства делает $$x$$ имейте? Во-первых, каждый квадрат в 2D сетке (i, j) имеет точно одно значение, таким образом, существует точно один ненулевой элемент среди записей трехмерного массива $$x(i,j,1),...,x(i,j,9)$$. Другими словами, для каждого $$i$$ и $$j$$,

Точно так же в каждой строке $$i$$ из 2D сетки существует точно одно значение из каждой из цифр от 1 до 9. Другими словами, для каждого $$i$$ и $$k$$,

И каждый столбец $$j$$ в 2D сетке имеет то же свойство: для каждого $$j$$ и $$k$$,

Главные 3х3 сетки имеют подобное ограничение. Для элементов сетки $$1\le i\le 3$$ и $$1\le j\le 3$$, и для каждого $$1\le k\le 9$$,

Чтобы представлять все девять главных сеток, только добавьте 3 или 6 каждому $$i$$ и $$j$$ индекс:

$$\sum _{i=1}^3\sum _{j=1}^{3}x(i+U,j+V,k)=1,$$ где $$U,Vϵ\{0,3,6\}.$$

Специальные подсказки

Каждое начальное значение (подсказка) может быть выражено как ограничение. Предположим что $$(i,j)$$ подсказка $$m$$ для некоторых $$1\le m\le 9$$затем $$x(i,j,m)=1$$. Ограничение $$\sum _{k=1}^{9}x(i,j,k)=1$$ гарантирует что все другой $$x(i,j,k)=0$$ для $$k\ne m$$.

Судоку в форме задачи оптимизации

Создайте переменную x оптимизации это - двоичный файл и размера 9 9 9.

x = optimvar('x',9,9,9,'Type','integer','LowerBound',0,'UpperBound',1);

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

sudpuzzle = optimproblem;
mul = ones(1,1,9);
mul = cumsum(mul,3);
sudpuzzle.Objective = sum(sum(sum(x,1),2).*mul);

Представляйте ограничения что суммы x в каждом координатном направлении тот.

sudpuzzle.Constraints.consx = sum(x,1) == 1;
sudpuzzle.Constraints.consy = sum(x,2) == 1;
sudpuzzle.Constraints.consz = sum(x,3) == 1;

Создайте ограничения, которые суммы главных сеток суммируют одной также.

majorg = optimconstr(3,3,9);

for u = 1:3
    for v = 1:3
        arr = x(3*(u-1)+1:3*(u-1)+3,3*(v-1)+1:3*(v-1)+3,:);
        majorg(u,v,:) = sum(sum(arr,1),2) == ones(1,1,9);
    end
end
sudpuzzle.Constraints.majorg = majorg;

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

for u = 1:size(B,1)
    x.LowerBound(B(u,1),B(u,2),B(u,3)) = 1;
end

Решите Судоку.

sudsoln = solve(sudpuzzle)

Solving problem using intlinprog.
LP:                Optimal objective value is 405.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

sudsoln = struct with fields:
    x: [9x9x9 double]

Вокруг решения гарантировать, что все записи являются целыми числами и отображают решение.

sudsoln.x = round(sudsoln.x);

y = ones(size(sudsoln.x));
for k = 2:9
    y(:,:,k) = k; % multiplier for each depth k
end
S = sudsoln.x.*y; % multiply each entry by its depth
S = sum(S,3); % S is 9-by-9 and holds the solved puzzle
drawSudoku(S)

Можно легко проверять, что решение правильно.

Функция, чтобы чертить судоку

type drawSudoku

function drawSudoku(B)
% Function for drawing the Sudoku board

%   Copyright 2014 The MathWorks, Inc. 


figure;hold on;axis off;axis equal % prepare to draw
rectangle('Position',[0 0 9 9],'LineWidth',3,'Clipping','off') % outside border
rectangle('Position',[3,0,3,9],'LineWidth',2) % heavy vertical lines
rectangle('Position',[0,3,9,3],'LineWidth',2) % heavy horizontal lines
rectangle('Position',[0,1,9,1],'LineWidth',1) % minor horizontal lines
rectangle('Position',[0,4,9,1],'LineWidth',1)
rectangle('Position',[0,7,9,1],'LineWidth',1)
rectangle('Position',[1,0,1,9],'LineWidth',1) % minor vertical lines
rectangle('Position',[4,0,1,9],'LineWidth',1)
rectangle('Position',[7,0,1,9],'LineWidth',1)

% Fill in the clues
%
% The rows of B are of the form (i,j,k) where i is the row counting from
% the top, j is the column, and k is the clue. To place the entries in the
% boxes, j is the horizontal distance, 10-i is the vertical distance, and
% we subtract 0.5 to center the clue in the box.
%
% If B is a 9-by-9 matrix, convert it to 3 columns first

if size(B,2) == 9 % 9 columns
    [SM,SN] = meshgrid(1:9); % make i,j entries
    B = [SN(:),SM(:),B(:)]; % i,j,k rows
end

for ii = 1:size(B,1)
    text(B(ii,2)-0.5,9.5-B(ii,1),num2str(B(ii,3)))
end

hold off

end