初期パズル

ヒントのデ，タ行列Bを以下に示します。最初の行B(1、2、2)は1行2列目にヒント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)有关此程序的列表，请参见本例的末尾。

このパズルと代替のmatlab®解法は，2009年の克里夫的角落で特集されていました。

数独パズルを手作業で解く多数の方法があるのと同じように,プログラムによって解く多数の方法があります。この例では，0-1整数計画法を使用した簡単な方法を説明します。

この方法は解のアルゴリズムを指定しないので特に単純です。単に数独のル，ルを表現し，ヒントを解の制約として記述し，intlinprogが解を求めます。

0-1整数計画アプロチ

基本となる考え方は,正方形の9行9列のグリッドを2進数値(0または1)の3次元9 x 9 x 9の配列に変換することです。3次元配列を相互に積み重ねられた9個の正方形グリッドとして考えます。配列の正方形レイヤーである最上位グリッドは,解またはヒントとして1が表示されている位置に1が表示されています。2番目のレヤは，解またはヒントとして2が表示されている位置に1が表示されています。9番目のレヤは，解またはヒントとして9が表示されている位置に1が表示されています。

この定式は0-1整数計画法に適しています。

ここでは目的関数は不要であり，0である可能性もあります。問題は実行可能解，まりすべての制約を満たす解を実際に求めることです。ただし,整数計画ソルバーの内部をタイブレーキングし,解を求める速度を向上させるために非定数目的関数を使用します。

数独のル，ルを制約として記述する

解 $$x$$が9 × 9 × 9のバescナリ配列で表されると仮定します。 $$x$$にはどのような特徴があるでしょうか。まず2次元グリッド(i, j)内の各四角形には厳密に1つの値が存在するので,3次元配列のエントリ $$x（我，j，1），．．．，x（我，j，9）$$には厳密に1の非ゼロ要素が存在します。まり，すべての $$我$$および $$j$$にいて次のようになります。

同様に，2次元グリッドの各行 $$我$$には，1 ~ 9の各数値から厳密に1の値が含まれます。まり， $$我$$と $$k$$のそれぞれにいて次のようになります。

さらに2次元グリッドの各列 $$j$$は同じ特徴になり， $$j$$と $$k$$のそれぞれにいて次のようになります。

主な3行3列のグリッドは同様の制約をもます。グリッド要素 $$1\le 我\le 3.$$と $$1\le j\le 3.$$および $$1\le k\le 9$$のそれぞれにいて次のようになります。

9 $$我$$および $$j$$のそれぞれに3または6を加算します。

$$\underset{我＝1}{\overset{3.}{\sum }}\underset{j＝1}{\overset{3.}{\sum }}x（我+U，j+V，k）＝1，$$ここで， $$U，Vϵ｛0，3.，6｝．$$

ヒントを記述する

各初期値(ヒント)は制約として記述することができます。ヒント $$（我，j）$$は, $$1\le 米\le 9$$に対して $$米$$であると仮定します。すると， $$x（我，j，米）＝1$$になります。制約 $$\underset{k＝1}{\overset{9}{\sum }}x（我，j，k）＝1$$によって， $$k\ne 米$$に対して他はすべて $$x（我，j，k）＝0$$になります。

数独のル，ルを書き込む

数独ルルは9 × 9 × 9解の配列xを用いて簡単に記述できますが，線形制約はベクトル解行列x (:)として与えられます。したがって,数独プログラムを書き込む際は,9 x 9 x 9初期配列から派生した制約を使用する必要があります。

以下に，制約としてヒントも含む数独ル，ルを設定する1の方法を示します。sudokuEngineファ@ @ルはソフトウェアに付属しています。

类型sudokuEngine

function [S,eflag] = sudokuEngine(B) %该函数设置数独规则。它读入矩阵B中表示的谜题%，调用intlinprog来解决谜题，并返回矩阵s中的解% %。矩阵B应该有3列和至少17行(因为一个数独谜题%需要至少17个条目才能唯一解决)。每一行的前两个%元素是线索的i,j坐标，第三个%元素是线索的值，从1到9的整数。如果B是% 9 × 9矩阵，该函数首先将其转换为3列形式。版权所有2014 The MathWorks, Inc. if isequal(size(B)，[9,9]) % 9 × 9线索%转换为81 × 3 [SM,SN] = meshgrid(1:9);% make i,j entries B = [SN(:)，SM(:)，B(:)];% i,j,k行%现在删除零行[rrem，~] = find(B(:，3) == 0);B(rrem，:) = [];end if size(B,2) ~= 3 || length(size(B)) > 2 error('输入矩阵必须是N-by-3或9-by-9') end if sum([any(B ~= round(B))，any(B < 1)，any(B > 9)]) %强制条目1-9错误('条目必须是1到9之间的整数')end %%数数游戏规则:N = 9^3;x中自变量的百分比，一个9 × 9 × 9的数组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);解决开头所描绘的谜题

LP:最优目标值为29565.000000。找到最优解。Intlinprog停止在根节点，因为目标值在最佳值的间隙公差范围内，选项。AbsoluteGapTolerance = 0(默认值)。intcon变量是公差范围内的整数，选项。IntegerTolerance = 1e-05(默认值)。

drawSudoku (S)

解が正しいかどうかを容易に確認できます。

数独パズルを描画する関数

类型drawSudoku

function drawSudoku(B) %用于绘制数独板的函数%版权所有公司图;坚持;轴,轴平等%准备画矩形(“位置”,[0 0 9 9],“线宽”,3,“剪裁”,“关闭”)%外边界矩形(“位置”,[3 0 3 9],“线宽”,2)%沉重的竖线矩形(“位置”,[3]0、3、9日,“线宽”,2)%沉重的水平线矩形(“位置”,[1]0 1 9日,“线宽”,1)%小横线矩形(“位置”,[1]0、4、9日,“线宽”,1)矩形(“位置”,[1]0、7、9日,“线宽”,1)矩形(“位置”,[1,0,1,9],“线宽”,1)%小垂直直线矩形('Position'，[4,0,1,9]，'LineWidth'，1)矩形('Position'，[7,0,1,9]，'LineWidth'，1) %填充线索% % B的行为(i,j,k)的形式，其中i是从%开始计数的行，j是列，k是线索。为了将条目放在%框中，j是水平距离，10-i是垂直距离，%我们减去0.5以使线索在框中居中。如果B是一个9乘9的矩阵，如果size(B,2) == 9 % 9列[SM,SN] = meshgrid(1:9)，则先将其转换为3列;% make i,j entries B = [SN(:)，SM(:)，B(:)];% i,j,k行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