数独パズルをSugar制約ソルバーで解く


はじめに

Nikoliによる 数独(Sudoku, ナンバープレース, ナンプレ, Number Place)パズルを Sugar制約ソルバー (A SAT-based Constraint Solver)で解いてみます.

例題

Nikoliによる 数独の例題 です.
例題
  6       1
 7   6   5 
8   1 3 2  
  5  4  8  
 4  7 2  9 
  8  1  7  
  1 2 5   3
 6   7   8 
2       4  

数独のルール

Nikoliによる数独のルールは以下の通りです.
(Rule 1)
あいているマスに,1から9までの数字のどれかを入れます.
(Rule 2)
タテ列(9列あります),ヨコ列(9列あります), 太線で囲まれた3x3のブロック(それぞれ9マスあるブロックが9つあります)の どれにも1から9までの数字が1つずつ入ります.
数独を 制約充足問題(CSP, Constraint Satisfaction Problem)として表すための 方法について考えていきます.

なお,以下ではパズルの盤面の一番上の行を第0行, 一番左の列を第0列として数えます.

Rule 1

(Rule 1)
あいているマスに,1から9までの数字のどれかを入れます.
Ruleに従い,次のようにします. 変数x_0_0は,1から9の値のいずれかを取るので,以下のように宣言します.
    (int x_0_0 1 9)  ; 0行目0列目には1から9のいずれかの値が入る
他の変数も同様に宣言します. ただし,x_0_2のようにすでに値が決まっている場合,以下のように宣言します.
    (int x_0_2 6 6)  ; 0行目2列目には6が入る

Rule 2

(Rule 2)
タテ列(9列あります),ヨコ列(9列あります), 太線で囲まれた3x3のブロック(それぞれ9マスあるブロックが9つあります)の どれにも1から9までの数字が1つずつ入ります.
たとえば,0行目について考えます. Rule 2は,0行目に入っている数がすべて互いに異なっているということですから, allDifferent制約を用いて以下のように表現できます.
    ; 0行目の数はすべて互いに異なっている
    (allDifferent x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_0_5 x_0_6 x_0_7 x_0_8)
他の行,列,ブロックについても同様に制約を付け加えます.

注意: Sugar version 1.13では,allDifferent ではなく alldifferent と小文字で書いてください.

実行結果

すべての制約を記述したファイルを作成し, Sugarで実行すると以下のような結果が得られます.
s SATISFIABLE
a x_0_0	5
a x_0_1	3
a x_0_2	6
a x_0_3	8
a x_0_4	2
a x_0_5	7
a x_0_6	9
a x_0_7	4
a x_0_8	1
a x_1_0	1
a x_1_1	7
a x_1_2	2
a x_1_3	9
a x_1_4	6
a x_1_5	4
a x_1_6	3
a x_1_7	5
a x_1_8	8
a x_2_0	8
a x_2_1	9
a x_2_2	4
a x_2_3	1
a x_2_4	5
a x_2_5	3
a x_2_6	2
a x_2_7	6
a x_2_8	7
a x_3_0	7
a x_3_1	1
a x_3_2	5
a x_3_3	3
a x_3_4	4
a x_3_5	9
a x_3_6	8
a x_3_7	2
a x_3_8	6
a x_4_0	6
a x_4_1	4
a x_4_2	3
a x_4_3	7
a x_4_4	8
a x_4_5	2
a x_4_6	1
a x_4_7	9
a x_4_8	5
a x_5_0	9
a x_5_1	2
a x_5_2	8
a x_5_3	5
a x_5_4	1
a x_5_5	6
a x_5_6	7
a x_5_7	3
a x_5_8	4
a x_6_0	4
a x_6_1	8
a x_6_2	1
a x_6_3	2
a x_6_4	9
a x_6_5	5
a x_6_6	6
a x_6_7	7
a x_6_8	3
a x_7_0	3
a x_7_1	6
a x_7_2	9
a x_7_3	4
a x_7_4	7
a x_7_5	1
a x_7_6	5
a x_7_7	8
a x_7_8	2
a x_8_0	2
a x_8_1	5
a x_8_2	7
a x_8_3	6
a x_8_4	3
a x_8_5	8
a x_8_6	4
a x_8_7	1
a x_8_8	9
a
Sugarの次期リリースには, 問題ファイルを読み込んで 制約条件を記述したCSPファイルを作成するツールを含める予定です. 以下は,その実行例です.
$ ./sudoku.pl data/sudoku-0.txt >csp/sudoku-0.csp

$ /usr/bin/time sugar csp/sudoku-0.csp >log/sudoku-0.log
2.42user 0.08system 0:01.68elapsed 149%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+384outputs (2major+13352minor)pagefaults 0swaps

$ ./sudoku.pl -s log/sudoku-0.log data/sudoku-0.txt
; Sudoku Puzzle
; # http://www.nikoli.co.jp/en/puzzles/sudoku/
; size 9 9
; - - 6 - - - - - 1
; - 7 - - 6 - - 5 -
; 8 - - 1 - 3 2 - -
; - - 5 - 4 - 8 - -
; - 4 - 7 - 2 - 9 -
; - - 8 - 1 - 7 - -
; - - 1 2 - 5 - - 3
; - 6 - - 7 - - 8 -
; 2 - - - - - 4 - -

 5  3  6  8  2  7  9  4  1
 1  7  2  9  6  4  3  5  8
 8  9  4  1  5  3  2  6  7
 7  1  5  3  4  9  8  2  6
 6  4  3  7  8  2  1  9  5
 9  2  8  5  1  6  7  3  4
 4  8  1  2  9  5  6  7  3
 3  6  9  4  7  1  5  8  2
 2  5  7  6  3  8  4  1  9

; END

「パズルをSugar制約ソルバーで解く」に戻る


Naoyuki Tamura
( Last modified: Thu Sep 11 12:32:10 2008 JST ,   ?????  Since June 4, 2008 )