整数計画法によるパズル解法 数独

キューブ王 海永

「数独」パズルの求解コードを、GLPKMathProg言語で記述してみた。

普通の数独については、導入の記事(GLPKでのペンシルパズル(ナンリンなど)攻略法)で既に解法を提示しているので、ここでは変形数独を包含した解法を示す。

 

[名称]

まずは、ニコリに敬意を表し、名称の由来をwikipediaからそのまま紹介する。

------------------------------------------

「数独」という呼称は「数字は独身に限る(すうじはどくしんにかぎる)」の略語で、日本国内においては日本のパズル制作会社ニコリの発行するパズル雑誌『パズル通信ニコリ』をはじめとした、同社の関与する媒体で使用される名称。同社によって商標登録されており、日本国内においては同社が制作に関与していないものについては「ナンプレ(ナンバープレース)」等の表記が使われている。2008年、高等学校英語の教科書に取り上げられた数独に関する文章について、教科書検定の結果「特定の商品の宣伝になる恐れがある」との理由で表記を『Sudoku』から『puzzle』などに修正を求められたと報じられた。

一方、日本国外では同社による商標登録が行われておらず、同社が制作に関与していないものについても「sudoku」の呼称が用いられている場合がある。また、従前からの名称である「number place」「figure place」の呼称も引き続き用いられている

-------------------------------------------

 

[ルール、問題例]

ルールは以下のよう。

(1) 3*3のブロックに区切られた 9×9の正方形の枠内に19までの数字を入れる。

(2) 空いているマスに19のいずれかの数字を入れる。

(3) 縦・横の各列及び、太線で囲まれた3×3のブロック内に同じ数字が複数入ってはいけない。

以下は、問題例と解答例。右端はブロック分割の指定(普通の数独では本来不要)

ルール(1)3*3ブロック分割の部分に変形を加えた変形数独もある。以下は、その問題例と解答例。右端は、ブロック分割を指定するもの。

 [解法コード]

解法コードの基本部は以下。

 

## ----------- sudoku -------------------

param bid{0..9,0..9} integer default 0;                         # block id

param ini{1..9,1..9} integer;                                        # pre-located digits

var ban{1..9,1..9,1..9} binary;                                       # ban[r,c,n]=1 ß-à board[r,j] = d

var van{1..9,1..9} integer, >=1, <=9;

 

s.t. uniq{ r in 1..9, c in 1..9}: sum{ n in 1..9} ban[r,c,n] =1;          # ban[r,c]=n

s.t. hori{ r in 1..9, n in 1..9}: sum{ c in 1..9} ban[r,c,n] =1;          # Latin square

s.t. vert{ c in 1..9, n in 1..9}: sum{ r in 1..9} ban[r,c,n] =1;          # Latin square

s.t. mat { m in 1..9,n in 1..9}:sum{r in 1..9, c in 1..9:bid[r,c]=n}ban[r,c,m]   =1;

s.t. init{ r in 1..9, c in 1..9, n in 1..9: n=ini[r,c]}: ban[r,c,n] =1;

s.t. conv{ r in 1..9, c in 1..9}: van[r,c]=sum{ n in 1..9} n*ban[r,c,n];

 

  Param bidは、ブロック分割を指定するための2次元配列。指定例は[ルール、問題例]節や最後の[問題定義コード]節参照。

Param ini1は、予め数字が入っている部分を指定するもの。以上の2つが問題定義配列。

Var ban[r,c,n]はマス[r,c]に数字nが入っているかどうかを示す3次元binary配列。

Var van[r,c]ban[r,n,c]の2次元化整数配列。解答ダンプ用。

 

制約uniqは、個別のセル[r,c]に数字が1つ置かれるというもの。

制約horiは、個別の行r1..9の各数字が1つ置かれるというもの。

制約vertは、個別の列c1..9の各数字が1つ置かれるというもの。

制約matは、個別のブロックn(n=ini[r,c])に1..9の各数字が1つ置かれるというもの。

制約initは、予め指定されていた数字を解答配列ban[r,c, ]に設定するもの。

制約convは、ban[r,c, ]の情報をvan[r,c]に代入するもの。単にダンプ用。

 

以上でいい。別にダンプ用のコードが必要だが、それについては省略。勿論、[求解コード」節には載せてある。

 

[速度など]

 以下の結果となった。速度は問題とならない。

 

 

 [MathProg求解コード]

 

## ----------- sudoku -------------------

param bid{0..9,0..9} integer default 0;                            # block id

param ini{1..9,1..9} integer;                             # pre-located digits

var ban{1..9,1..9,1..9} binary;                                          # board[r,j] is d

var van{1..9,1..9} integer, >=1, <=9;

 

s.t. uniq{ r in 1..9, c in 1..9}: sum{ n in 1..9} ban[r,c,n] =1;             # ban[r,c]=n

s.t. hori{ r in 1..9, n in 1..9}: sum{ c in 1..9} ban[r,c,n] =1;              # Latin square

s.t. vert{ c in 1..9, n in 1..9}: sum{ r in 1..9} ban[r,c,n] =1;              # Latin square

s.t. mat { m in 1..9,n in 1..9}:sum{r in 1..9, c in 1..9:bid[r,c]=n}ban[r,c,m]   =1;

s.t. init{ r in 1..9, c in 1..9, n in 1..9: n=ini[r,c]}: ban[r,c,n] =1;

s.t. conv{ r in 1..9, c in 1..9}: van[r,c]=sum{ n in 1..9} n*ban[r,c,n];

 

#minimize value: ban[1,5,1]+5*ban[9,9,1];

#minimize value: sum{r in 1..9}van[r,5];

solve;

 

printf "--block id--\n";

for{r in 1..9}{ 

    for{c in 1..9}{ printf " %s", bid[r,c]; } printf("\n");

}

 

printf "--ini--\n";

for{r in 1..9}{ 

  for{c in 1..9}{printf if bid[r-1,c]-bid[r,c] then "+--" else "+  ";} printf "+\n";

  for{c in 1..9}{

            printf if bid[r,c-1]-bid[r,c] then "|" else " ";                       

            printf " %s", if ini[r,c] then ini[r,c] else " ";

  } printf "|\n";

} for{c in 1..9}{printf "+--";} printf "+\n";

 

printf "--answer--\n";

for{r in 1..9}{ 

  for{c in 1..9}{printf if bid[r-1,c]-bid[r,c] then "+--" else "+  ";} printf "+\n";

  for{c in 1..9}{

            printf if bid[r,c-1]-bid[r,c] then "|" else " ";                       

            printf " %s", van[r,c];

  } printf "|\n";

} for{c in 1..9}{printf "+--";} printf "+\n";

end;

 

 

[問題定義コード]

 

#p01.txt

data;       ## ---------- input --------------

param bid:  1 2 3 4 5 6 7 8 9:=

               1  1 1 1 2 2 2 3 3 3

               2  1 1 1 2 2 2 3 3 3

               3  1 1 1 2 2 2 3 3 3

               4  4 4 4 5 5 5 6 6 6

               5  4 4 4 5 5 5 6 6 6

               6  4 4 4 5 5 5 6 6 6

               7  7 7 7 8 8 8 9 9 9

#             6  4 4 7 5 5 5 6 6 6

#             7  4 7 7 8 8 8 9 9 9

               8  7 7 7 8 8 8 9 9 9

               9  7 7 7 8 8 8 9 9 9;

param ini:  1 2 3 4 5 6 7 8 9:=

         1  0 0 5 3 0 0 0 0 0

         2  8 0 0 0 0 0 0 2 0

         3  0 7 0 0 1 0 5 0 0

         4  4 0 0 0 0 5 3 0 0

         5  0 1 0 0 7 0 0 0 6

         6  0 0 3 2 0 0 0 8 0

         7  0 6 0 5 0 0 0 0 9

         8  0 0 4 0 0 0 0 3 0

         9  0 0 0 0 0 9 7 0 0

; end;

 

#p02.txt

data;       ## ---------- input --------------

param bid:  1 2 3 4 5 6 7 8 9:=

               1  1 1 1 2 2 2 3 3 3

               2  1 1 1 2 2 2 3 3 3

               3  1 1 1 2 2 2 3 3 3

               4  4 4 4 5 5 5 6 6 6

               5  4 4 4 5 5 5 6 6 6

               6  4 4 4 5 5 5 6 6 6

               7  7 7 7 8 8 8 9 9 9

               8  7 7 7 8 8 8 9 9 9

               9  7 7 7 8 8 8 9 9 9;

param ini:  1 2 3 4 5 6 7 8 9:=

      1     0 2 0 0 7 5 0 1 0

      2     1 0 0 0 0 4 5 0 8

      3     0 5 6 8 0 0 2 0 0

      4     8 1 0 0 0 0 7 0 0

      5     9 0 0 0 0 0 0 0 3

      6     0 0 2 0 0 0 0 4 5

      7     0 0 9 0 0 1 4 3 0

      8     3 0 1 7 0 0 0 0 9

      9     0 7 0 3 9 0 0 2 0

; end;

 

#p03.txt

data;       ## ---------- input --------------

param bid:  1 2 3 4 5 6 7 8 9:=

     1  1 1 1 2 2 2 3 3 3

     2  1 1 1 2 2 2 3 3 3

     3  1 1 1 2 2 2 3 3 3

     4  4 4 4 5 5 5 6 6 6

     5  4 4 4 5 5 5 6 6 6

     6  4 4 4 5 5 5 6 6 6

     7  7 7 7 8 8 8 9 9 9

     8  7 7 7 8 8 8 9 9 9

     9  7 7 7 8 8 8 9 9 9;

param ini:  1 2 3 4 5 6 7 8 9:=

      1     8 0 0 0 0 0 0 0 0

      2     0 0 3 6 0 0 0 0 0

      3     0 7 0 0 9 0 2 0 0

      4     0 5 0 0 0 7 0 0 0

      5     0 0 0 0 4 5 7 0 0

      6     0 0 0 1 0 0 0 3 0

      7     0 0 1 0 0 0 0 6 8

      8     0 0 8 5 0 0 0 1 0

      9     0 9 0 0 0 0 4 0 0

; end;

 

#p04.txt

data;       ## ---------- input --------------

param bid:  1 2 3 4 5 6 7 8 9:=

               1  1 1 1 2 2 2 3 3 3

               2  1 1 1 2 2 2 3 3 3

               3  1 1 1 2 2 2 3 3 3

               4  4 4 4 5 5 5 6 6 6

               5  4 4 4 5 5 5 6 6 6

               6  4 4 4 5 5 5 6 6 6

               7  7 7 7 8 8 8 9 9 9

               8  7 7 7 8 8 8 9 9 9

               9  7 7 7 8 8 8 9 9 9;

param ini:  1 2 3 4 5 6 7 8 9:=

      1     0 0 8 4 0 0 1 0 6

      2     5 0 0 0 0 0 0 0 0

      3     0 9 0 0 0 7 0 3 0

      4     0 0 5 3 0 0 0 0 0

      5     0 2 0 0 6 0 8 0 0

      6     0 0 9 2 0 0 0 0 0

      7     0 4 0 0 0 5 0 9 0

      8     8 0 0 0 0 0 0 0 0

      9     0 0 3 6 0 0 4 0 2

; end;

 

#p05.txt

data;       ## ---------- input --------------

param bid:  1 2 3 4 5 6 7 8 9:=

               1  1 1 2 2 2 3 3 3 3

               2  1 1 2 2 2 3 3 3 3

               3  1 1 2 2 2 4 4 4 3

               4  1 5 5 5 5 4 4 4 6

               5  1 7 7 7 5 4 4 4 6

               6  1 7 7 7 5 5 5 5 6

               7  8 7 7 7 9 9 9 6 6

               8  8 8 8 8 9 9 9 6 6

               9  8 8 8 8 9 9 9 6 6;

param ini:  1 2 3 4 5 6 7 8 9:=

      1     1 0 0 4 0 8 2 7 9

      2     6 0 7 0 8 0 0 5 3

      3     4 0 0 9 0 0 7 0 0

      4     0 1 0 0 0 2 0 4 0

      5     0 0 4 0 9 0 6 0 0

      6     0 6 0 3 0 0 0 2 0

      7     0 0 2 0 0 6 0 0 8

      8     9 7 0 0 2 0 3 0 4

      9     2 4 1 6 0 9 0 0 7

; end;

 

#p06.txt

data;

param bid:  1 2 3 4 5 6 7 8 9:=

              1   1 1 2 2 2 2 2 3 3

              2   1 1 2 2 2 3 3 3 3

              3   1 1 2 4 4 4 3 3 3

              4   1 1 1 4 5 5 5 5 5

              5   6 6 6 4 4 4 5 5 7

              6   6 6 8 4 9 9 5 5 7

              7   6 6 8 4 9 9 7 7 7

              8   6 8 8 8 9 9 7 7 7

              9   6 8 8 8 8 9 9 9 7;

param ini:  1 2 3 4 5 6 7 8 9:=

              1   6 0 8 7 5 0 1 3 9

              2   3 0 0 9 0 7 8 0 0

              3   2 9 3 0 0 0 4 1 6

              4   0 0 0 0 1 0 3 0 2

              5   1 0 2 0 0 0 5 0 0

              6   5 0 0 0 2 0 0 0 4

              7   7 3 5 0 8 0 9 0 1

              8   0 0 0 3 0 0 0 0 0

              9   9 2 1 0 4 5 0 7 3

; end;

 

 

トップページへ

 

Ads by TOK2