Global Constraint Catalog: Ck_same

5.209. k_same_modulo

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ and from $𝚔_𝚜𝚊𝚖𝚎$ .

Constraint

$𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘 (𝚂𝙴𝚃𝚂, 𝙼)$

Type

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Arguments

$𝚂𝙴𝚃𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜𝚎𝚝 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$
$𝙼$	$𝚒𝚗𝚝$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

| 𝚂𝙴𝚃𝚂 | > 1

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚂𝙴𝚃𝚂, 𝚜𝚎𝚝)

𝙼 > 0

Purpose

Given a collection of $| 𝚂𝙴𝚃𝚂 |$ sets, each containing the same number of domain variables, the $𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint forces a $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint between each pair of consecutive sets.

Example

(\begin{matrix} 〈\begin{matrix} 𝚜𝚎𝚝 - 〈1, 9, 1, 5, 2, 1〉, \\ 𝚜𝚎𝚝 - 〈6, 4, 1, 1, 5, 5〉, \\ 𝚜𝚎𝚝 - 〈1, 3, 4, 2, 8, 7〉 \end{matrix}〉, 3 \end{matrix})

The $𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint holds since:

The first and second collections of variables are assigned 1 value in ${0, 3, \dots, 3 \cdot k}$ , 3 values in ${1, 4, \dots, 1 + 3 \cdot k}$ and 2 values in ${2, 5, \dots, 2 + 3 \cdot k}$ .
The second and third collections of variables are also assigned 1 value in ${0, 3, \dots, 3 \cdot k}$ , 3 values in ${1, 4, \dots, 1 + 3 \cdot k}$ and 2 values in ${2, 5, \dots, 2 + 3 \cdot k}$ .

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝙼 > 1

Symmetries

Items of $𝚂𝙴𝚃𝚂$ are permutable.
Items of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝$ are permutable.
An occurrence of a value $u$ of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $𝙼$ .

Arg. properties

Contractible wrt. $𝚂𝙴𝚃𝚂$ .

implies: $𝚔_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ .

part of system of constraints: $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ .

used in graph description: $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ .

Keywords

characteristic of a constraint: sort based reformulation, modulo.

combinatorial object: permutation.

constraint type: system of constraints, decomposition.

Arc input(s)

$𝚂𝙴𝚃𝚂$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜𝚎𝚝 1, 𝚜𝚎𝚝 2)

Arc arity

Arc constraint(s)

𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘

(𝚜𝚎𝚝 1 . 𝚜𝚎𝚝, 𝚜𝚎𝚝 2 . 𝚜𝚎𝚝, 𝙼)

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚂𝙴𝚃𝚂 | - 1

Graph model

Parts (A) and (B) of Figure 5.209.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint.

Figure 5.209.1. Initial and final graph of the $𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.209. k_same_modulo

Figure 5.209.1. Initial and final graph of the 𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘 constraint

Figure 5.209.1. Initial and final graph of the $𝚔_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint