Решить Судоку головоломки с помощью целочисленного программирования: на основе решателя

Открыть сценарий в реальном времени

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

Вы наверняка видели головоломки Судоку. Головоломка состоит в заполнении сетки 9 на 9 целыми числами от 1 до 9, так что каждое целое число появляется только один раз в каждой строке, столбце и большом квадрате 3 на 3. Сетка частично заполнена подсказками, и ваша задача - заполнить остальную часть сетки.

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

Вот матрица данных 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 году.

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

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

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

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

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

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

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

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

$_{}^{} ∑k=19x (i, j, k)$ = 1.

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

$_{}^{} ∑j=19x (i, j, k)$ = 1.

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

$_{}^{} ∑i=19x (i, j, k)$ = 1.

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

$_{}^{}_{}^{} ∑i=13∑j=13x (i, j, k)$ = 1.

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

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

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

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

Написать правила для Судоку

Хотя правила Судоку удобно выражены с точки зрения множества решения 9 на 9 на 9 x, линейные ограничения даны в терминах матрицы векторного решения x(:). Поэтому при написании программы Судоку необходимо использовать матрицы ограничений, полученные из начальных массивов 9 на 9.

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

type sudokuEngine

function [S,eflag] = sudokuEngine(B)
% This function sets up the rules for Sudoku. It reads in the puzzle
% expressed in matrix B, calls intlinprog to solve the puzzle, and returns
% the solution in matrix S.
%
% The matrix B should have 3 columns and at least 17 rows (because a Sudoku
% puzzle needs at least 17 entries to be uniquely solvable). The first two
% elements in each row are the i,j coordinates of a clue, and the third
% element is the value of the clue, an integer from 1 to 9. If B is a
% 9-by-9 matrix, the function first converts it to 3-column form.

%   Copyright 2014 The MathWorks, Inc. 

if isequal(size(B),[9,9]) % 9-by-9 clues
    % Convert to 81-by-3
    [SM,SN] = meshgrid(1:9); % make i,j entries
    B = [SN(:),SM(:),B(:)]; % i,j,k rows
    % Now delete zero rows
    [rrem,~] = find(B(:,3) == 0);
    B(rrem,:) = [];
end

if size(B,2) ~= 3 || length(size(B)) > 2
    error('The input matrix must be N-by-3 or 9-by-9')
end

if sum([any(B ~= round(B)),any(B < 1),any(B > 9)]) % enforces entries 1-9
    error('Entries must be integers from 1 to 9')
end

%% The rules of Sudoku:
N = 9^3; % number of independent variables in x, a 9-by-9-by-9 array
M = 4*9^2; % number of constraints, see the construction of Aeq
Aeq = zeros(M,N); % allocate equality constraint matrix Aeq*x = beq
beq = ones(M,1); % allocate constant vector beq
f = (1:N)'; % the objective can be anything, but having nonconstant f can speed the solver
lb = zeros(9,9,9); % an initial zero array
ub = lb+1; % upper bound array to give binary variables

counter = 1;
for j = 1:9 % one in each row
    for k = 1:9
        Astuff = lb; % clear Astuff
        Astuff(1:end,j,k) = 1; % one row in Aeq*x = beq
        Aeq(counter,:) = Astuff(:)'; % put Astuff in a row of Aeq
        counter = counter + 1;
    end
end

for i = 1:9 % one in each column
    for k = 1:9
        Astuff = lb;
        Astuff(i,1:end,k) = 1;
        Aeq(counter,:) = Astuff(:)';
        counter = counter + 1;
    end
end

for U = 0:3:6 % one in each square
    for V = 0:3:6
        for k = 1:9
            Astuff = lb;
            Astuff(U+(1:3),V+(1:3),k) = 1;
            Aeq(counter,:) = Astuff(:)';
            counter = counter + 1;
        end
    end
end

for i = 1:9 % one in each depth
    for j = 1:9
        Astuff = lb;
        Astuff(i,j,1:end) = 1;
        Aeq(counter,:) = Astuff(:)';
        counter = counter + 1;
    end
end

%% Put the particular puzzle in the constraints
% Include the initial clues in the |lb| array by setting corresponding
% entries to 1. This forces the solution to have |x(i,j,k) = 1|.

for i = 1:size(B,1)
    lb(B(i,1),B(i,2),B(i,3)) = 1;
end

%% Solve the Puzzle
% The Sudoku problem is complete: the rules are represented in the |Aeq|
% and |beq| matrices, and the clues are ones in the |lb| array. Solve the
% problem by calling |intlinprog|. Ensure that the integer program has all
% binary variables by setting the intcon argument to |1:N|, with lower and
% upper bounds of 0 and 1.

intcon = 1:N;

[x,~,eflag] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);

%% Convert the Solution to a Usable Form
% To go from the solution x to a Sudoku grid, simply add up the numbers at
% each $(i,j)$ entry, multiplied by the depth at which the numbers appear:

if eflag > 0 % good solution
    x = reshape(x,9,9,9); % change back to a 9-by-9-by-9 array
    x = round(x); % clean up non-integer solutions
    y = ones(size(x));
    for k = 2:9
        y(:,:,k) = k; % multiplier for each depth k
    end

    S = x.*y; % multiply each entry by its depth
    S = sum(S,3); % S is 9-by-9 and holds the solved puzzle
else
    S = [];
end

Вызов решателя Sudoku

S = sudokuEngine(B); % Solves the puzzle pictured at the start

LP:                Optimal objective value is 29565.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).

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

Связанные темы

Решить Судоку головоломки с помощью целочисленного программирования: на основе проблем

Документация