Prolog:1〜9の2つの整数で和が10になる組み合わせを求める

gprologのマニュアルを見ていると「9 Finite domain solver and built-in predicates」という章がありました。「9.1 introduction」にも「constraint solver」という記述があるので、何らかの制約問題を解いてくれるのかと思い試して見ました。

簡単そうなサンプルとして、以下のような問題を考えてみました。

• A,B　が1〜9の範囲の整数をとる。
• A+Bが10となる組み合わせを考える。
• A>=Bとする。

gplorgの起動

$ gprolog
GNU Prolog 1.4.5 (64 bits)
Compiled Mar 17 2020, 23:55:22 with gcc
By Daniel Diaz
Copyright (C) 1999-2020 Daniel Diaz
| ?- 

１〜9の範囲のA,Bを用意

| ?- fd_domain([A,B],1,9).

A = _#0(1..9)
B = _#17(1..9)

yes

それぞれに値を代入してみる

| ?- fd_domain([A,B],1,9), fd_labeling([A,B]).

A = 1
B = 1 ? ;

A = 1
B = 2 ? ;

A = 1
B = 3 ? 

yes

組み合わせがどんどん出てきます。上記の例では止めていますが、A=9,B=9の組み合わせまで出てきます。

A+Bが10となる制約

| ?- fd_domain([A,B],1,9), A + B #= 10, fd_labeling([A,B]).

A = 1
B = 9 ? a

A = 2
B = 8

A = 3
B = 7

A = 4
B = 6

A = 5
B = 5

A = 6
B = 4

A = 7
B = 3

A = 8
B = 2

A = 9
B = 1

(1 ms) yes

A + B = 10 となる組み合わせが出てきますが、3+7=10, 7+3=10 のような組み合わせを省くため、大小関係の制約を追加します。

大小関係の制約 A >= Bの追加

| ?- fd_domain([A,B],1,9), A + B #= 10, A #>= B, fd_labeling([A,B]).

A = 5
B = 5 ? ;

A = 6
B = 4 ? ;

A = 7
B = 3 ? ;

A = 8
B = 2 ? ;

A = 9
B = 1

(1 ms) yes