初期パズル

ヒントのデータ行列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 整数計画法を使用した簡単な方法を説明します。

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

0 - 1整数計画アプローチ

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

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

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

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

解 $$x$$が 9 x 9 x 9のバイナリ配列で表されると仮定します。 $$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$$になります。

最適化問題形式の数独

2値でサイズが9 x 9 x 9の最適化変数xを作成します。

x = optimvar (“x”,9,9,9,“类型”,“整数”,下界的0,“UpperBound”,1);

やや適当な目的関数で最適化問題を作成します。この目的関数は,問題に内在する対称性を破壊することで,ソルバーの役に立つ場合があります。

sudpuzzle = optimproblem;mul = 1 (1, 1, 9);mul = cumsum (mul 3);sudpuzzle。目标=总和(金额(金额(x, 1), 2)。* mul);

各座標方向のxの和が 1.になるという制約を表します。

sudpuzzle.Constraints.consx=sum（x，1）==1；sudpuzzle.Constraints.consy=sum（x，2）==1；sudpuzzle.Constraints.consz=sum（x，3）==1；

同様に主なグリッドの和の合計が1になるという制約を作成します。

majorg = optimconstr(3、3、9);为u = 1:3为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）=一（1,1,9）；结束结束sudpuzzle.Constraints.majorg = majorg;

ヒント エントリで下限を 1.に設定して、初期ヒントを含めます。この設定により、対応するエントリの値が 1.に固定されるため、各ヒント値での解がヒント エントリに設定されます。

为u=1:size（B，1）x.LowerBound（B（u，1），B（u，2），B（u，3））=1；结束

数独パズルを解きます。

sudsoln =解决(sudpuzzle)

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

sudsoln =结构体字段:x (9 x9x9双):

すべてのエントリが確実に整数になるように解を丸め,解を表示します。

sudsoln。x＝round(sudsoln.x); y = ones(size(sudsoln.x));为k=2:9y（：，：，k）=k；每个深度k的%乘数结束S = sudsoln.x。* y;%乘以每个条目的深度S=总和（S，3）；% S是9乘9的，并持有已解决的谜题drawSudoku (S)

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

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

类型drawSudoku

function drawSudoku(B) % function for drawing the Sudoku board %公司图;坚持;轴,轴平等%准备画矩形(“位置”,[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)%小竖线矩形(“位置”,[4 0 1 9],“线宽”,1)矩形(“位置”,[7,0,1,9],“线宽”,1)% % % B的行填写线索的形式(i, j, k),我是%的行数上面，j是列，k是线索。要将条目放入%框中，j是水平距离，10-i是垂直距离，%减去0.5使线索在框中居中。% %如果B是一个9 × 9的矩阵，如果size(B,2) == 9 % 9 columns [SM,SN] = meshgrid(1:9);% make i,j entries B = [SN(:)，SM(:)，B(:)];% i,j,k row end for ii = 1:size(B,1) text(B(ii,2)-0.5, 3.5 -B(ii,1)，num2str(B(ii,3)) end hold off end .(如果你的操作失败，你的操作会失败。