iZ-C を用いたモデル化

領域変数 (CSint型)

制約解消による問題解決のアプローチは以下の２つの原理に基づいています。

問題を一連の変数と変数間の制約によりモデル化します。問題の解決とは、すべての変数について制約をまもった値を見つけることになります。
.問題解決は、「制約伝播」と呼ばれる機構に基づいて行われます。制約伝播により、解の探索の間、制約は矛盾を検出し、解に含まれない値を変数から除去することができるだけ早く行えるように能動的に使用されます。

問題をモデル化する段階では、問題が「どのようにして」解かれるかを考える必要はありません。この段階では、変数（問題において値を求めるべき対象）と変数間の制約（変数のとりうる値が満たさなければならない制限）により問題を宣言的に表現することを目指します。 iZ-Cでは変数は領域変数と呼ばれ、CSintという型で表現されます。 CSint型の変数のとりうる値の集合を領域といいます。

以下に CSint型変数の生成とその領域の例を示します。(コード例では cs_init, cs_end を省略しています)

コード:

{
  CSint *vint = cs_createNamedCSint(0, 10, "vint"); // 区間(0..10)を領域とするCSint型の
  cs_printf("%T\n", vint);                          // 変数を生成し、その領域を表示する。
}

出力:

vint: {0..10}

コード:

{
  int domain[9] = {-2, 0, 1, 2, 3, 5, 6, 7, 10};     // domain 配列により定義される領域を
  CSint *vint = cs_createCSintFromDomain(domain, 9); // 持つ CSint型の変数を生成し、その
  cs_printf("%T\n", vint);                           // 領域を表示する。
}

出力:

{-2, 0..3, 5..7, 10}

覆面算

例として、「覆面算」を取り上げてみましょう。A～T までの文字を0～9の数字に置き換えたときに以下の乗算の結果が正しくなるような文字と数字の対応を見つけることが問題です。また、0～9の数字は各々2回ずつ出現するものとします。

    A B C   (L1)
 *  D E F   (L2)
 ----------
    G H I   (L3)
  J K L     (L4)
M N O       (L5)
-----------
P Q R S T   (L6)

この問題の解はCSint型の変数 A, B, ..., T の値で表現されます。
変数の間の制約は、以下の通りです。

a). L6 = L1 * L2
b). L3 = F * L1
c). L4 = E * L1
d). L5 = D * L1
e). L6 = 100 * L5 + 10 * L4 + L3
f). A \(\neq\) 0, D \(\neq\) 0, G \(\neq\) 0, J \(\neq\) 0, M \(\neq\) 0, P \(\neq\) 0
g). 0 ～ 9 の数字は、{A, B, ..., T} 中にそれぞれちょうど2回ずつ出現します。

なお、L1, L2, ..., L6は以下のように定義されます。

d1). L1 = 100 * A + 10 * B + C;
d2). L2 = 100 * D + 10 * E + F;
d3). L3 = 100 * G + 10 * H + I;
d4). L4 = 100 * J + 10 * K + L;
d5). L5 = 100 * M + 10 * N + O;
d6). L6 = 10000 * P + 1000 * Q + 100 * R + 10 * S + T.

では、この問題をiZ-Cを用いて記述してみましょう。

#include "iz.h"

#define NB_DIGITS 20
CSint **Digit;  // Digit is an array of 20 CSint variables
CSint *L1, *L2, *L3, *L4, *L5, *L6;

// Digit[a] = A, Digit[b] = B, ..., Digit[t] = T
enum {a = 0, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t};

void constraints()
{
  int val;

  Digit = cs_createCSintArray(NB_DIGITS, 0, 9);

  L1 = cs_VScalProd(3, Digit[a], Digit[b], Digit[c], 100, 10, 1);  // (d1)
  L2 = cs_VScalProd(3, Digit[d], Digit[e], Digit[f], 100, 10, 1);  // (d2)
  L3 = cs_VScalProd(3, Digit[g], Digit[h], Digit[i], 100, 10, 1);  // (d2)
  L4 = cs_VScalProd(3, Digit[j], Digit[k], Digit[l], 100, 10, 1);  // (d3)
  L5 = cs_VScalProd(3, Digit[m], Digit[n], Digit[o], 100, 10, 1);  // (d4)
  L6 = cs_VScalProd(5, Digit[p], Digit[q], Digit[r], Digit[s], Digit[t], // (d5)
                    10000, 1000, 100, 10, 1);

  cs_Eq(L6, cs_Mul(L1, L2));        // (a)
  cs_Eq(L3, cs_Mul(Digit[f], L1));  // (b)
  cs_Eq(L4, cs_Mul(Digit[e], L1));  // (c)
  cs_Eq(L5, cs_Mul(Digit[d], L1));  // (d)
  cs_Eq(L6, cs_VScalProd(3, L5, L4, L3, 100, 10, 1)); //(e)

  // (f)
  cs_NEQ(Digit[a], 0);
  cs_NEQ(Digit[d], 0);
  cs_NEQ(Digit[g], 0);
  cs_NEQ(Digit[j], 0);
  cs_NEQ(Digit[m], 0);
  cs_NEQ(Digit[p], 0);

  // (g)
  for (val = 0; val <= 9 ; val++) {
      cs_OccurConstraints(CSINT(2), val, Digit, NB_DIGITS);
  }
}