Exclusion de paires alignées (APE)

À connaître auparavant : Notation des candidats · Paires et sous-ensembles · ALS-XZ

APE (Aligned Pair Exclusion) choisit deux cellules de base bleues, associe leurs candidats de toutes les façons possibles, puis rejette les associations qui provoquent une contradiction.

Si un candidat de la base A est impossible avec chacun des candidats de la base B, il peut être supprimé de A.

1. La propriété des ALS utilisée par APE

Un ALS (Almost Locked Set, ensemble presque verrouillé) contient N cellules d'une même ligne, colonne ou région dont l'union des candidats comporte exactement N+1 chiffres.

Si l'ensemble perd un chiffre, il devient un ensemble verrouillé de N cellules et N chiffres. S'il perd simultanément deux chiffres distincts, il ne reste que N−1 chiffres pour remplir N cellules : c'est impossible. APE utilise ce second constat.

2. Quand un ALS rejette une association

Supposons A=p et B=q, avec p ≠ q. Un ALS jaune rend cette association impossible si :

1. p et q appartiennent tous deux à l'union des candidats de l'ALS ;
2. A voit toutes les occurrences de p dans l'ALS ;
3. B voit toutes les occurrences de q dans l'ALS.

A=p supprime tous les p de l'ALS, tandis que B=q supprime tous les q. L'ALS perd deux chiffres différents et ne peut plus remplir ses N cellules. L'association (p, q) est donc impossible. Les cellules ne contenant que d'autres chiffres de l'ALS n'ont pas à être vues par les deux bases, et les chiffres n'ont pas besoin d'être des RCC.

3. Type 1 : les cellules de base se voient

Dans le Type 1, les deux cellules bleues partagent une ligne, une colonne ou une région.

• (x, x) est directement impossible, car un même chiffre ne peut apparaître deux fois dans une maison.
• Une paire distincte (p, q) est rejetée quand A voit tous les p et B tous les q de l'ALS.

Le conflit de chiffres identiques fait donc partie de la preuve du Type 1.

4. Type 2 : les cellules de base ne se voient pas

Dans le Type 2, les deux bases ne partagent aucune maison. Elles peuvent contenir le même chiffre simultanément ; (x, x) doit donc rester possible.

Si les deux cellules contiennent le candidat x, on ne peut pas supprimer x simplement parce que toutes les autres associations sont bloquées. Chaque association rejetée en Type 2 doit comporter deux chiffres distincts et une véritable contradiction ALS.

5. Des associations à l'élimination

Supposons que A contienne 1, 4 et B 1, 6, 8. Pour tester A=4, il faut l'associer à chaque choix de B :

A	B	Contradiction
4	1	l'ALS P perd 4 et 1
4	6	l'ALS Q perd 4 et 6
4	8	l'ALS R perd 4 et 8

Aucun candidat de B ne peut coexister avec A=4, donc 4 peut être supprimé de A. Un même ALS peut rejeter plusieurs associations, ou plusieurs ALS peuvent se partager les preuves. Seule compte la couverture complète. Le même contrôle est effectué dans l'autre sens pour les candidats de B.

6. Couleurs de l'indice

• Cellules bleues : les deux cellules de base.
• Candidats verts : les candidats associés dans les bases.
• Cellules jaunes : les ALS réellement utilisés dans les contradictions.
• Candidats jaunes : les deux chiffres que l'ALS perdrait.
• Candidat rouge : échoue avec tous les choix de l'autre base et peut être supprimé.

7. Erreurs fréquentes

• Rejeter une seule association ne suffit pas : tous les candidats partenaires doivent échouer.
• Chaque base doit voir toutes les occurrences du chiffre qu'elle suppose dans l'ALS ; les cellules sans rapport n'ont pas à être visibles.
• Un ALS doit être formé de N cellules dans une maison avec exactement N+1 chiffres candidats.
• Les chiffres identiques ne sont en conflit direct qu'en Type 1 ; ils restent possibles en Type 2.
• Des candidats incomplets peuvent créer un faux constat « toutes les associations échouent ».
• APE peut recouvrir une élimination de paire, d'aile ou d'ALS-XZ. Plusieurs explications peuvent rester disponibles, mais la technique la plus simple est choisie par défaut.

À retenir : fixer un candidat, épuiser tous les choix de l'autre cellule et ne le supprimer que si aucune voie n'est possible.