В этом примере показано, как решить Судоку с помощью бинарного целочисленного программирования. Для подхода, основанного на проблеме смотрите, Решают Судоку Через Целочисленное программирование: основанный на проблеме.
Вы, вероятно, видели Судоку. Проблема должна заполнить 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®, были показаны в Углу Клива в 2 009.
Существует много подходов к решению Судоку вручную, а также многих программируемых подходов. Этот пример показывает прямой подход с помощью бинарного целочисленного программирования.
Этот подход особенно прост, потому что вы не даете алгоритм решения. Только выразите правила Судоку, выразите подсказки как ограничения на решение, и затем intlinprog
производит решение.
Ключевая идея состоит в том, чтобы преобразовать проблему от квадрата 9 9 сетка к кубическим 9 9 9 массивами двоичных значений (0 или 1). Думайте о кубическом массиве, как являющемся 9 квадратными сетками, сложенными друг на друге. Главная сетка, квадратный слой массива, имеет 1 везде, где решение или подсказка имеют 1. Второй слой имеет 1 везде, где решение или подсказка имеют 2. Девятый слой имеет 1 везде, где решение или подсказка имеют 9.
Эта формулировка точно подходит для бинарного целочисленного программирования.
Целевая функция не нужна здесь и может также быть 0. Проблема состоит в том, чтобы действительно только найти возможное решение, означая то, которое удовлетворяет всем ограничениям. Однако для связи, врывающейся внутренности решателя целочисленного программирования, давая увеличенную скорость решения, используют непостоянную целевую функцию.
Предположим решение представлен в 9 9 9 двоичными массивами. Какие свойства делает имейте? Во-первых, каждый квадрат в 2D сетке (i, j) имеет точно одно значение, таким образом, существует точно один ненулевой элемент среди записей трехмерного массива . Другими словами, для каждого и ,
Точно так же в каждой строке из 2D сетки существует точно одно значение из каждой из цифр от 1 до 9. Другими словами, для каждого и ,
И каждый столбец в 2D сетке имеет то же свойство: для каждого и ,
Главные 3х3 сетки имеют подобное ограничение. Для элементов сетки и , и для каждого ,
Чтобы представлять все девять главных сеток, только добавьте 3 или 6 каждому и индекс:
где
Каждое начальное значение (подсказка) может быть выражено как ограничение. Предположим что подсказка для некоторых затем . Ограничение гарантирует что все другой для .
Несмотря на то, что правила Судоку удобно выражаются в терминах 9 9 9 массивами решения x
, линейные ограничения даны в терминах векторной матрицы решения x(:)
. Поэтому, когда вы написали программу Судоку, необходимо использовать ограничительные матрицы, выведенные от 9 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
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