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

Вот матрица данных 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 ® были представлены в журнале Cleve's Corner в 2009 году.

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

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

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

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

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

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

Выражение правил Судоку в качестве ограничений

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

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

И каждый столбец $$j$$ в 2-D сетке имеет одно и то же свойство: для каждого $$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)

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

Функция для рисования головоломки Sudoku

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