日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

解集合プログラミングを用いたクイーン支配問題の解法に関する一考察
加藤 聖人

田村 直之

番原 睦則

本稿では，解集合プログラミング (ASP) を用いたクイーン支配問題の解法について述べる．クイーン支配問題とは，クイーングラフと正の整数 k が与えられたとき，サイズ k の支配集合が存在するかどうかを判定する問題である．ク
イーン支配問題の ASP 符号化として，基本符号化と改良符号化の 2 種類を考案した．改良符号化は，各行，各列，各対角線に対してクイーンの有無を表す補助アトムを導入することにより，基本符号化と比較して基礎化後の補助ア
トムの数を少なく抑えられる点が特長である．また，高速化のための工夫として，(i) クイーンが配置された行数，列数，対角線数に関するヒント制約，(ii) 配置されるクイーンの数をなるべく少なくする探索ヒューリスティックス，を考案した．さらに，クイーン支配遷移問題への拡張も行なった．クイーン支配遷移問題の ASP 符号化は，改良符号化の自然な拡張となっている．考案した符号化の有効性を評価するために，n 次のクイーン支配問題 (10 ≤ n ≤ 26)
を用いて実行実験を行なった．その結果，改良符号化と工夫 (i)(ii) を組み合わせた手法の優位性を確認できた．

lem; [2]) は，入力グラフを n × n のクイーングラフ

1 はじめにQn に限定した支配集合問題である．クイーングラフ

支配集合問題 (dominating set problem; [3]) は，

Qn は，n × n のチェス盤について，各マスを頂点とグラフ G と正の整数 k が与えられたとき，サイズ k

し，クイーンが移動できるマス同士が辺で結ばれていの G の支配集合が存在するかどうかを判定する問題

るグラフである．クイーン支配問題に関する研究の歴である．支配集合問題は一般に NP 完全に属する問史は古く，1862 年に文献 [2] で Q8 の最小支配集合の題である [3]．支配集合問題は，スケジューリングやサイズが 5 であることが示されてから継続的に研究

電波塔配置問題など多くの現実問題を応用にもつこされている．クイーン支配遷移問題は，クイーン支配とが知られている [6] [7]．

問題を基とする支配集合遷移問題である．

支配集合遷移問題 (dominating set reconﬁguration

解集合プログラミング (Answer Set Programming;

problem; [5] [12]) は，基となる支配集合問題とその 2

ASP [1] [4] [8] [9]) は，論理プログラミングから派生しつの実行可能解が与えられたとき，一方から他方へ，た宣言的プログラミングパラダイムである．ASP 言

遷移制約を満たしつつ，実行可能解のみを経由して到語は一階論理に基づく知識表現言語の一種である．

達可能かどうかを判定する問題である．支配集合遷移

論理プログラムは ASP のルールの有限集合である．

問題は組合せ遷移問題 [10] [13] の 1 つであり，一般のASP システムは論理プログラムから安定モデル意味

グラフに対して PSPACE 完全である．

論 [4] に基づく解集合を計算するシステムである．近n 次のクイーン支配問題 (Queen Domination ProbA Study on Solving Queen Domination Problem with
Answer Set Programming
Masato Kato, Mutsunori Banbara, 名古屋大学大学院情報学研究科, Graduate School of Informatics, Nagoya
University.
Naoyuki Tamura, 神戸大学, Kobe University.

年，SAT 技術を応用した高速 ASP システムが開発され，AI 分野を中心に，スケジューリング，プラン
ニング，モデル検査，最適化など様々な分野への実用的応用が急速に拡大している．
本稿では，解集合プログラミングを用いたクイーン
支配問題の解法，および，クイーン支配遷移問題への

拡張について述べる．クイーン支配問題の ASP 符号化として，基本符号化と改良符号化の 2 種類を考案Qした．基本符号化は，チェス盤の各マスごとに，そのマスがカバーされているか (そのマスにクイーンが配Q置されているか，あるいは，そのマスに移動できるク
イーンがあるか) を表す補助アトムを導入する．改良
符号化は，チェス盤の各行，各列，各対角線に対してクイーンの有無を表す補助アトムを導入する．これ

Qにより，基本符号化と比較して，改良符号化は基礎化
後の補助アトムの数を少なく抑えられる点が特長である．

図1

クイーングラフ Q5 の最小支配集合の例

また，高速化のための工夫として，(i) クイーンが配置された行数，列数，対角線数に関するヒント制について各マスを頂点とし，クイーンが移動できるマ約，(ii) 配置されるクイーンの数をなるべく少なくす

ス同士が辺で結ばれているグラフである．

る探索ヒューリスティックス，を考案した．さらに，クイーングラフの支配数は，1862 年に文献 [2]クイーン支配遷移問題への拡張も行なった．クイーン

で γ(Q8 ) = 5 が 示 さ れ て か ら 研 究 さ れ て お り，

支配遷移問題の ASP 符号化は，改良符号化の自然な

そ の 後 ，n = 3, 11 を 除 い て n ≤ 132 に 対 し て ，拡張となっている．

⌈n/2⌉ ≤ γ(Qn ) ≤ ⌈n/2⌉ + 1 であることが証明され考案した符号化の有効性を評価するために，n 次のている [11]．表 1 に，THE ON-LINE ENCYCLO-

クイーン支配問題 (10 ≤ n ≤ 26) を用いて実行実験

PEDIA OF INTEGER SEQUENCES に掲載されているクイーングラフの支配数を示す †1 ．

を行なった．その結果，改良符号化に工夫 (i)(ii) を組
み合わせた手法の優位性を確認できた．
以降の構成は以下の通りである．第 2 節でクイーン支配問題の概要を述べる．第 3 節で ASP の言語構
文を簡単に説明する．第 4 節でクイーン支配問題のASP 符号化を提案し，その実験結果を第 5 節で示す．
第 6 節では，クイーン支配遷移問題への拡張について述べる．最後に，第 7 節で本稿をまとめる．

チェス盤で考えると，クイーン支配問題は以下の 2
つの制約で表される．
個数制約: チェス盤上に配置されるクイーンの個数は k 個である．
支配制約: すべてのマスにひとつ以上のクイーンが移動可能である．
図 1 に，クイーングラフ Q5 と正の整数 k = 3 に対するクイーン支配問題の解の例を示す．チェス盤上

2 クイーン支配問題に 3 つのクイーンが配置されており，すべてのマス

無向グラフ G = (V, E) の頂点の部分集合 S ⊂ Vにひとつ以上のクイーンが移動できることがわかる．

に対して，任意の頂点 u ∈ V \ S にも辺 (u, v) ∈ E が

この解は，Q5 の最小支配集合になっている．

存在し，v ∈ S を満たすとき，S を G の支配集合という．支配集合の要素数をサイズとよび，サイズが最3 解集合プログラミング

小の支配集合を G の最小支配集合とよぶ．最小支配

ASP の言語は，一般拡張選言プログラムに基づい集合のサイズを G の支配数とよび γ(G) と表す．

ている [8]．本稿では，説明の簡略化のため，そのサ

n 次のクイーン支配問題は，n × n のクイーングラ

ブクラスである標準論理プログラムについて説明す

フ Qn と正の整数 k が与えられたとき，サイズが kる．以降，標準論理プログラムを単に論理プログラム

である Qn の支配集合が存在するかどうかを判定する問題である．クイーングラフとは，n × n のチェス盤†1 https://oeis.org/A075458

表1

クイーン支配問題の支配数nγ(Qn )nγ(Qn )nγ(Qn )nγ(Qn )nγ(Qn )

1

1

6

3

11

5

16

9

21

11

2

1

7

4

12

6

17

9

22

12

3

1

8

5

13

7

18

9

23

12

4

2

9

5

14

8

19

10

24

13

5

3

10

5

15

9

20

11

25

13

とよぶ．本稿で示す論理プログラムは，clingo 言語の構文に従って記述されている †2 ．
論理プログラムは，以下の形式のルールの有限集合である．

1 n(1..n).
2
3 % cardinality constraints
4 k { q(I,J) : n(I), n(J) } k.
5a0 :- a1 , . . . ,am , not am+1 , . . . ,not an .

6 covered(I,J) :- q(I,_), n(I), n(J).

ここで，0 ≤ m ≤ n であり，各 ai はアトム，notはデフォルトの否定 †3 ，“,” は連言を表す．“:-” の7 covered(I,J) :- q(_,J), n(I), n(J).

左側をヘッド，右側をボディとよぶ．“.” はルールの10

終わりを表す終端記号である．ルールの直観的な意味

8 covered(I,J) :- q(X,Y), n(I), n(J), X+Y == I+J.
9 covered(I,J) :- q(X,Y), n(I), n(J), X-Y == I-J.

11 % domination constraints
12 :- not covered(I,J), n(I), n(J).

は，「a1 , . . . , am がすべて成り立ち，am+1 , . . . , an のそれぞれが成り立たないならば，a0 が成り立つ」で

コード 1

クイーン支配問題の基本符号化ある．ボディが空のルール (すなわち a0 :- .) をファクトと呼び，“:-” を省略することができる．
ヘッドが空のルールを一貫性制約とよぶ．例えば，
一貫性制約 “:- not a1 ,a2 ,a3 .” は，「not a1 と a2 とa3 が同時に成り立つことはない」を意味する．

先度を 3 に上げ (デフォルトは 0)，最初に偽を割り当てるヒューリスティックスを表す．

ASP システムは，与えられた論理プログラムから，安定モデル意味論 [4] に基づく解集合を計算するシス

ASP 言 語 に は ，組 合 せ 問 題 を 解 く た め に 便 利テムである．clingo を含め最新の ASP システムは，な 拡 張 構 文 が 用 意 さ れ て い る ．そ の 代 表 的 な もグラウンダーを用いて変数を含む論理プログラムをの に ，選 択 子と個 数 制 約が あ る ．例 え ば ，選 択 子

変数を含まない論理プログラムに変換 (基礎化) した“{a1 ; . . . ;an }.” を ファク ト と し て 書 く と ，「アト

のち，ASP ソルバーを用いて解集合を計算する方式

ム集合 {a1 , . . . , an } の任意の部分集合が成り立つ」

が主流となっている．

を 意 味 す る ．個 数 制 約 は 選 択 子 の 両 端 に 選 択 可
能 な 個 数 の 上 下 限 を 付 け た も の で あ る ．例 え ば ，

4 クイーン支配問題の ASP 符号化「a1 , . . . , an“:- not lb {a1 ; . . . ;an } ub.” と書くと，クイーン支配問題を解くための ASP 符号化 (論理のうち，lb 個以上 ub 個以下が成り立つ」を意味する．

プログラム) として，基本符号化と改良符号化を示す．

ま た ，ASP シ ス テ ム clingo に は ，探 索 ヒュー

また，高速化のためのヒント制約と探索ヒューリス

リ ス ティック ス を 容 易 に カ ス タ マ イ ズ で き るティックスのカスタマイズについて述べる．

#heuristic 構 文 が 用 意 さ れ て い る ．例 え ば ，

基本符号化．クイーン支配問題の基本符号化をコー“#heuristic a1 . [3,false]” は，アトム a1 の優

ド 1 に示す．コード中のシンボル n と k は，それぞれクイーングラフ Qn のサイズと支配集合のサイズを†2 https://potassco.org/clingo/†3 失敗による否定ともよばれる．一階論理で定義される
否定 (¬) とは意味が異なる．

表す定数であり，clingo の実行時に与えられる．

1 行目の n(1..n) は，n×n のチェス盤の行あるいンがあるか) を表す補助アトムである．例えば，6 行

1 n(1..n).
2目のルールは，各行 I，各列 J に対して，クイーンが3 % cardinality constraints

行 I のいずれかの列に配置される (q(I,_) が真) な

4 k { q(I,J) : n(I), n(J) } k.

らば，covered(I,J) が真になることを表している．

5
6 covered_r(X):- q(X,_).

最後の 12 行目のルールはクイーン支配問題の支配制

7 covered_c(Y):- q(_,Y).

約を表す．このルールは，各行 I，各列 J に対して，

8 covered_u(X+Y) :- q(X,Y).
9 covered_d(X-Y) :- q(X,Y).

covered(I,J) が成り立つことを，ASP の一貫性制

10約を用いて強制している．

11 % domination constraints

改良符号化．改良符号化をコード 2 に示す．1–4

12 :- not covered_r(I),13

not covered_c(J),行目のルールは基本符号化と同じである．基本符号14

not covered_u(I+J),

化との大きな違いは 6–9 行目である．ここでは，各15

not covered_d(I-J),

16n(I), n(J).

マスがカバーされるかどうかを表す covered/2 の代わりに，各行，各列，各右上がり対角線，各右下

コード 2

クイーン支配問題の改良符号化

がり対角線に対してクイーンの存在の有無を表す補助アトム covered_r/1, covered_c/1, covered_u/1,

covered_d/1 を導入している．例えば，8 行目のルー

1 u(2..2*n).

ルは，クイーンがマス (X,Y) に配置される (q(X,Y)

2 d(1-n..n-1).
3が真) ならば，対応する右上がり対角線上にクイー

4 % hint constraints
5 :- not { covered_r(I) : n(I) } k.

ンが存在することを意味する covered_u(X+Y) が真

6 :- not { covered_c(J) : n(J) } k.

になることを表している．12 行目のルールはクイー

7 :- not { covered_u(U) : u(U) } k.

ン支配問題の支配制約を表す．このルールは，各行

8 :- not { covered_d(D) : d(D) } k.

I，各列 J に対して，covered_r(I), covered_c(J),
コード 3

ヒント制約

covered_u(I+J), covered_d(I-J) の少なくとも 1
つが成り立つことを強制している．
改良符号化は，基本符号化と比較して，基礎化後

1 % heuristic
2 #heuristic q(X,Y). [3,false]の補助アトムの数を少なく抑えられる点が特長である．具体的には，基本符号化は covered/2 の個数が

コード 4

探索ヒューリスティックスのカスタマイズ

n2 であるのに対し，改良符号化は，covered_r/1,
covered_c/1, covered_u/1, covered_d/1 の個数のは列を表すファクトである．n(1..n) は複数のファ

合計が 6n − 2 となる．

クトの略記であり，基礎化の際に，n(1), n(2), . . . ,ヒント制約．改良符号化の高速化のために，クイー

n(n) に展開される．アトム q(I,J) は，マス (I,J)

ンが配置される行数，列数，対角線数に関するヒントにクイーンが配置されるかどうかを表す．4 行目の制約を考案した (コード 3)．1–2 行目の u(2..2*n)

ルールはクイーン支配問題の個数制約を表している．

と d(1-n..n-1) は，それぞれ右上がり対角線と右下

このルールは，各行 I，各列 J に対して，解の候補とがり対角線を表すファクトである．5 行目のルールは，

なる q(I,J) を導入し，そのうち真となる個数がちょクイーンが配置される行数の総和は，入力として与えうど k 個になることを ASP の個数制約を用いて強制られる支配集合のサイズ k 以下でなければならない

している．6–9 行目の covered(I,J) は，マス (I,J)

ことを表している．6,7,8 行目のルールは，それぞれがカバーされているか (そのマスにクイーンが配置さ

列数，各右上がり対角線の数，各右下がり対角線の数れているか，あるいは，そのマスに移動できるクイーに関するヒント制約である．

探索ヒューリスティックスのカスタマイズ．第 2 節の表 1 に示したクイーン支配問題の既知の支配数か

start(1,3).

start(2,3).

start(5,3).

goal(1,1).

goal(3,3).

goal(5,5).

らもわかる通り，n × n のチェス盤に対し，クイーンが置かれるマスの数 k は少ない．そのため，クイー

コード 5

図 2 のクイーン支配遷移問題のスタート状態とゴール状態を表す ASP ファクトンの有無を表すアトム q(I,J) に優先的に偽を割り当てることで，充足可能な問題に対する求解性能が向上する可能性がある．このシンプルなアイデアを

CPU 時間 を太字で記している．表 2 の 24 ≤ n ≤ 26

clingo の#heuristic 文を利用して記述したプログラ

については，すべての符号化が制限時間内に解を求ムをコード 4 に示す．

めることができなかったため省略している．表 3 の20 ≤ n ≤ 26 についても，同様の理由で省略している．

5 実行実験

表 2 の充足可能な場合では，基本符号化と改良符

第 4 節で示した符号化，ヒント制約，探索ヒュー号化が n ≤ 11 まで，改良符号化にヒント制約を追

リスティックスの有効性を評価するために，実行実験

加した手法が n ≤ 14 までしか解けなかった．それにを行なった．ベンチマークには，以下のクイーン支配

対して，改良符号化にヒント制約と探索ヒューリス

問題 (計 34 問) を使用した．

ティックスを追加した手法は，n ≤ 22 までのすべて• クイーングラフには，Qn (10 ≤ n ≤ 26) を使用の問題 (n = 21 を除く) を解くことができた．これにした．n ≤ 9 は短時間で解けるため省略した．

より，この手法の優位性，特に探索ヒューリスティッ• 支 配 集 合 の サ イ ズ k に は ，充 足 可 能 な 場 合
k = γ(Qn ) と充足不能な場合 k = γ(Qn ) − 1の 2 通りを使用した．

クスの有効性が確認できた．
一方，表 3 の充足不能な場合では，改良符号化にヒント制約を追加した手法が，n ≤ 18 までのすべてのなお，γ(Q26 ) は THE ON-LINE ENCYCLOPEDIAOF INTEGER SEQUENCES†4 に掲載されていな問題 (n = 14, 15 を除く) を解き，最も良い性能を示

い．そのため，k として数学的に証明されている上下しか解けておらず，探索ヒューリスティックスは充足限 13 ≤ γ(Q26 ) ≤ 14 をそれぞれ使用した．

不能な問題に対しては求解性能を低下させることが上記のベンチマークに対して，以下の 4 つの ASPした．充足可能な問題に有効であった手法は n = 10

わかった．

符号化を比較した．
基本: 基本符号化 (第 4 節のコード 1)
改良: 改良符号化 (第 4 節のコード 2)

6 クイーン支配遷移問題への拡張
クイーン支配遷移問題 (queen domination recon-

改良+Hint: 改良符号化にヒント制約を追加

ﬁguration problem) は，基となるクイーン支配問題

改良+Hint+Heu: 改良符号化にヒント制約と探とその二つの実行可能解が与えられたとき，一方か

索ヒューリスティックスを追加

ら他方へ，遷移制約を満たしつつ，実行可能解のみ

ASP システムには clingo-5.5.0 (trendy) を使用しを経由して到達可能かどうかを判定する問題である．

た．1 問あたりの制限時間は 1 時間とした．実験環境

本稿では，遷移制約として，各ステップで移動可能なは Mac OS, 3.2GHz Intel Core i7 (6 コア)，64GB

クイーンの数をちょうど 1 つに制限する．

メモリである．

Q5 と k = 3 に対するクイーン支配遷移問題の例を

実験結果を表 2 と表 3 に示す．どちらの表も，左か

図 2 に示す．この例では，スタート状態からゴール

ら順に，Qn のサイズ n，支配集合のサイズ k ，各符号状態まで 3 ステップで到達可能である．各遷移で移化が求解に要した CPU 時間を示している．最も良い

動するクイーンの数は 1 つであり，各ステップは基となるクイーン支配問題の制約を満たしていることが†4 https://oeis.org/A075458

わかる．

表2

クイーン支配問題の実験結果: k = γ(Qn )

n

k

基本

改良

改良+Hint

改良+Hint+Heu

10

5

4.538

6.236

0.221

0.243

11

5

1523.479

598.480

0.916

0.903

12

6

T.O.

T.O.

0.860

0.405

13

7

T.O.

T.O.

4.979

3.635

14

8

T.O.

T.O.

31.269

2.745

15

9

T.O.

T.O.

T.O.

5.173

16

9

T.O.

T.O.

T.O.

18.498

17

9

T.O.

T.O.

T.O.

4.159

18

9

T.O.

T.O.

T.O.

6.821

19

10

T.O.

T.O.

T.O.

619.247

20

11

T.O.

T.O.

T.O.

56.539

21

11

T.O.

T.O.

T.O.

T.O.

22

12

T.O.

T.O.

T.O.

187.200

23

12

T.O.

T.O.

T.O.

T.O.

表3

クイーン支配問題の実験結果: k = γ(Qn ) − 1

n

k

基本

改良

改良+Hint

改良+Hint+Heu

10

4

6.134

8.496

0.089

2265.760

11416.04217.781

0.087

T.O.

12

5

2985.050

3087.633

2.431

T.O.

13

6

T.O.

T.O.

333.590

T.O.

14

7

T.O.

T.O.

T.O.

T.O.

15

8

T.O.

T.O.

T.O.

T.O.

16

8

T.O.

T.O.

2163.442

T.O.

17

8

T.O.

T.O.

441.018

T.O.

18

8

T.O.

T.O.

621.504

T.O.

19

9

T.O.

T.O.

T.O.

T.O.

図 2 のクイーン支配遷移問題のスタート状態とである．コード 6 は，第 4 節のコード 2 で示したク

ゴール状態を表す ASP ファクトをコード 5 に示す．

イーン支配問題の改良符号化の自然な拡張になって

start/2 はスタート状態を，goal/2 はゴール状態をいる．改良符号化からの主な拡張点は，以下の通りで表すアトムである．例えば，1 行目はスタート状態で，ある．

マス (1,3), (2,3), (5,3) にクイーンが配置されることを表している．

• ステップ長を表す定数 t を導入する (2 行目)．
実際の t の値は clingo の実行時に与えられる．

コード 6 に，クイーン支配遷移問題を解くための• ステップを表すファクト t(0..t) を導入する (2ASP 符号化を示す．この符号化は，与えられたクイー

行目)．このファクトは，基礎化の際に，t(0),ン支配遷移問題がステップ長 t で到達可能かどうか判定し，存在する場合はその解を返す論理プログラムt(1), . . . , t(t) に展開される．
• 改良符号化のアトムにステップを表す項 T を引

t=0

t=1

Q

t=2

Q

Q

Q
Q

⇒

Q

Q
Q

⇒

Q

Q
Q

t=3

Q
⇒

Q

Q
Q

スタート状態

Q

Q

Q

Q

Q
ゴール状態

図2

クイーン支配遷移問題の例

数として追加する．例えば，アトム q(I,J,T) は，を考案した．さらに，クイーン支配遷移問題への拡ステップ T において，マス (I,J) にクイーンが張も行なった．クイーン支配遷移問題の ASP 符号化

配置されるかどうかを表す．

は，改良符号化の自然な拡張となっている．

• スタート状態を表すルール (31 行目) とゴール状考案した符号化の有効性を評価するために，n 次の態を表すルール (34 行目) をそれぞれ追加する．

クイーン支配問題 (10 ≤ n ≤ 26) を用いて実行実験• 遷移制約を表すルールを追加する (37–38 行目)．

を行なった．その結果，充足可能な問題について，改31 行目のルールは，スタート状態とステップ 0 で良符号化にヒント制約と探索ヒューリスティックスをのクイーンの配置が一致することを強制する．同様に追加した手法が良い性能を示し，特に探索ヒューリス

して，34 行目のルールは，ゴール状態とステップ t でティックスの有効性が確認できた．一方，充足不能なのクイーンの配置が一致することを強制する．37–38

問題については，改良符号化にヒント制約を追加した

行目の moved_from(X,Y,T) は，ステップ T-1 でマス手法が良い性能を示し，探索ヒューリスティックスは(X,Y) に配置されていたクイーンが，ステップ T で他

求解性能を低下させることがわかった．

のマスへ移動したことを表す補助アトムである．38

今後の課題としては，一般の支配集合問題および支行目のルールは，各ステップで移動するクイーンの数がちょうど 1 つであることを，ASP の個数制約を用

配集合遷移問題への拡張，および，CoRe Challenge
2022 †5 ベンチマーク問題集を用いた評価実験が挙いて強制している．

げられる．また，SAT ソルバーを用いた解法など他のアプローチとの比較も重要な今後の課題の 1 つで7 おわりにある．

本稿では，解集合プログラミング (ASP) を用いた
クイーン支配問題の解法，および，遷移問題への拡張

参 考 文 献について述べた．

[ 1 ] Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving, Cambridge
University Press, 2003.
[ 2 ] de Jaenisch, C.: Applications de l’Analyse
Mathématique au Jeu des Échecs, Vol. 3, Petrograd,1862.
[ 3 ] Garey, M. R. and Johnson, D. S.: Computers
and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman & Co., 1979.
[ 4 ] Gelfond, M. and Lifschitz, V.: The Stable Model
Semantics for Logic Programming, Proceedings ofthe Fifth International Conference and Symposium

クイーン支配問題の ASP 符号化として，基本符号化と改良符号化の 2 種類を考案した．基本符号化は，

ASP 言語の表現力の高さを生かし，クイーン支配問
題の制約を ASP のルール 7 個で簡潔に表現できる．
改良符号化は，チェス盤の各行，各列，各対角線に対してクイーンの有無を表す補助アトムを導入する．
これにより，基本符号化と比較して，基礎化後の補助
アトムの数を削減している点が特長である．また，高速化のためのヒント制約と探索ヒューリスティックス†5 https://core-challenge.github.io/2022/

1 % step length t
2 t(0..t).
3
4 % grid n, up-right diagonal u, down-right diagonal d
5 n(1..n).
6 u(2..2*n).
7 d(1-n..n-1).
8
9 % cardinality constraints
10 k { q(I,J,T) : n(I), n(J) } k :- t(T).
11
12 covered_r(X,T):- q(X,_,T).

13 covered_c(Y,T):- q(_,Y,T).

14 covered_u(X+Y,T) :- q(X,Y,T).
15 covered_d(X-Y,T) :- q(X,Y,T).
16
17 % domination constraints
18 :- not covered_r(I,T),
19

not covered_c(J,T),

20

not covered_u(I+J,T),

21

not covered_d(I-J,T),

22

n(I), n(J), t(T).

23
24 % sum constraints
25 :- not { covered_r(I,T) : n(I) } k, t(T).
26 :- not { covered_c(J,T) : n(J) } k, t(T).
27 :- not { covered_u(U,T) : u(U) } k, t(T).
28 :- not { covered_d(D,T) : d(D) } k, t(T).
29
30 % start configuration
31 :- not q(X,Y,0), start(X,Y).
32
33 % goal configuration
34 :- not q(X,Y,t), goal(X,Y).
35
36 % transition constraints
37 moved_from(X,Y,T) :- q(X,Y,T-1), not q(X,Y,T), t(T), T>0.
38 :- not 1 { moved_from(X,Y,T) } 1, t(T), T>0.

コード 6

クイーン支配遷移問題の ASP 符号化

on Logic Programming, MIT Press, 1988, pp. 1070–
1080.
[ 5 ] Haddadan, A., Ito, T., Mouawad, A. E.,
Nishimura, N., Ono, H., Suzuki, A., and Tebbal, Y.:
The complexity of dominating set reconﬁguration,
Theor. Comput. Sci., Vol. 651(2016), pp. 37–49.
[ 6 ] Haynes, T. W., T.Hedetniemi, S., and J.Slater,
P.: Domination in Graphs Advanced Topics, Marcel
Dekker,inc., 1998.
[ 7 ] Haynes, T. W., T.Hedetniemi, S., and J.Slater,P.: Fundamentals of Domination in Graphs, Marcel
Dekker inc., 1998.
[ 8 ] 井上克巳, 坂間千秋: 論理プログラミングから解集合
プログラミングへ, コンピュータソフトウェア, Vol. 25,
No. 3(2008), pp. 20–32.
[ 9 ] Niemelä, I.:
Logic Programs with Stable
Model Semantics as a Constraint Programming
Paradigm, Ann. Mathematics and Artiﬁcial Intelligence, Vol. 25, No. 3–4(1999), pp. 241–273.
[10] Nishimura, N.: Introduction to Reconﬁguration,
Algorithms, Vol. 11, No. 4(2018), pp. 52.
[11] Östergård, P. R. J. and Weakley, W. D.: Valuesof Domination Numbers of the Queen’s Graph, The
Erectronic Journal of Combinatrix, Vol. 8(2001),
pp. R29.
[12] Suzuki, A., Mouawad, A. E., and Nishimura, N.:
Reconﬁguration of dominating sets, J. Comb. Optim., Vol. 32, No. 4(2016), pp. 1182–1195.
[13] van den Heuvel, J.: The complexity of change,
Surveys in Combinatorics 2013, Blackburn, S. R.,
Gerke, S., and Wildon, M.(eds.), London Mathematical Society Lecture Note Series, Vol. 409, Cambridge University Press, 2013, pp. 127–160.