Le Zèbre de Lewis Carroll

Oui très bien

On peut résoudre ce problème par un solveur de problèmes de satisfaction de contrainte. Chaque attribut (“anglais”, “vin”, etc) est une variable. Les domaines sont les entiers de 1 à 5, correspondant au numéro de maison. Deux exception sont les variables “norvégien” et “lait” dont le domaine est un singleton, comme indiqué par les contraintes unaires de l’entrée.

Les autres contraintes sont toutes binaires. On peut modéliser et résoudre le problème comme suit.

#!/usr/bin/env python3

import sys
from constraint_programming import constraint_program

# chaque attribut est une variable
varnames = [
    ["norvégien", "anglais",  "espagnol",  "ukrainien", "japonais"],
    ["bleue",     "rouge",    "verte",     "jaune",     "blanche"],
    ["lait",      "café",     "thé",       "vin",       "eau"],
    ["kools",     "cravens",  "old golds", "gitanes",   "chesterfields"],
    ["chien",     "escargot", "renard",    "cheval",    "zèbre"]
]

# les maisons sont numérotés de 1 à 5
DOM = [1,2,3,4,5]
EQUAL = set((u,u) for u in DOM)
DIFF = set((u,v) for u in DOM for v in DOM if u != v)
SUCC = set((u, u+1) for u in [1,2,3,4])
PREC = set((u+1, u) for u in [1,2,3,4])
NEXT = SUCC | PREC

var = {}
for categorie in varnames:
    for name in categorie:
        var[name] = set(DOM)

# norvégien = 1
var["norvégien"] = {1}

# lait = 3
var["lait"] = {3}

P = constraint_program(var)

# tout différent
for categorie in varnames:
    for a in categorie:
        for b in categorie:
            if a < b:
                P.add_constraint(a, b, DIFF)

# bleue = norvégien + 1
P.add_constraint("bleue", "norvégien", PREC)

# anglais = rouge
P.add_constraint("anglais", "rouge", EQUAL)

# verte = café
P.add_constraint("verte", "café", EQUAL)

# jaune = kools
P.add_constraint("jaune", "kools", EQUAL)

# blanche = verte + 1
P.add_constraint("blanche", "verte", PREC)

# espagnol = chien
P.add_constraint("espagnol", "chien", EQUAL)

# ukrainien = thé
P.add_constraint("ukrainien", "thé", EQUAL)

# japonais = cravens
P.add_constraint("japonais", "cravens", EQUAL)

# old golds = escargot
P.add_constraint("old golds", "escargot", EQUAL)

# gitanes = vin
P.add_constraint("gitanes", "vin", EQUAL)

# (chesterfields = renard + 1) ou (chesterfields = renard - 1)
P.add_constraint("chesterfields", "renard", NEXT)

# (kools = cheval + 1) ou (kools = cheval - 1)
P.add_constraint("kools", "cheval", NEXT)

# P.print_tree = True

sol = P.solve()
for maison in DOM:
    print("%-15i" % maison, end="")
print()
for categorie in varnames:
    for maison in DOM:
        for name in categorie:
            if sol[name] == maison:
                print("%-15s" % name, end="")
    print()

Le programme affiche l’unique solution comme suit.

maison 1	maison 2	maison 3	maison 4	maison 5
norvégien	ukrainien	anglais	japonais	espagnol
jaune	bleue	rouge	verte	blanche
eau	thé	lait	café	vin
kools	chesterfields	old golds	cravens	gitanes
renard	cheval	escargot	zèbre	chien

Le Zèbre de Lewis Carroll

suite