Начальная головоломка

Вот матрица данных 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 ® были представлены в «Углу Клева» в 2009 году.

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

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

Двоично-целочисленный подход к программированию

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

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

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

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

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

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

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

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

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

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

Экспресс-подсказки

Каждое начальное значение (ключ) может быть выражено как ограничение. Предположим, что $$(i,j$$) ключ является $$$$m для некоторых $$\mathrm{}\mathrm{}$$1≤m≤9. Тогда $$x(i,j,\mathrm{}$$m) = 1. $$\underset{\mathrm{}}{\overset{\mathrm{Ограничение}}{}}\mathrm{\sum k=19x}(\mathrm{i}$$, j, k) = 1 гарантирует, что $$все\mathrm{остальные}$$ x (i$$,j$$, k) = 0 для k≠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