Résoudre un Sudoku en Prolog

Sudoku layout
Sudoku layout (Photo credit: Wikipedia)

Prolog est un langage déclaratif qui décrit les problèmes plutôt que d’indiquer à la machine comment trouver la solution. La description se fait à travers l’écriture de prédicats logics et a pour avantage de faire réfléchir le programmeur sur la modélisation du problème…. C’est mon langage préféré mais je n’ai pas l’occasion de m’en servir dans ma vie professionnelle. La faute à ce langage à la mode qu’était Java et avec lequel j’ai débuté ma carrière il y a plus de 10 ans. Dans ce blog donc point de référence à Prolog jusqu’à aujourd’hui et ce billet sera pour corriger ce défaut.

Pour disserter sur Prolog j’ai choisi un exercice facile pour montrer le mécanisme de recherche de Prolog (la base du calcul  des prédicats)  et la programmation par contrainte qui permet de réduire grandement le temps de calcul. Cet exercice est le Sudoku 9×9.

Aperçu de Prolog

Prolog (Programmation Logique) peut être vu comme une base de connaissances où l’on ajoute des prédicats et des règles de déductions entre ces prédicats. Par exemple on peut dire à Prolog que Pierre est un garçon. Pour cela il suffit de décider que garçon(X) est un prédicat qui dit que X est un garçon où X est une variable. On apprend à Prolog que le prédicat garçon(X)  est vrai si X prend la valeur Pierre. En d’autre terme on apprend à Prolog que si X vaut Pierre alors X est un garçon. Ce qui s’écrit

garçon(X) :- X = 'Pierre'

C’est ce qu’on appelle une règle. On peut ajouter autant de règles que l’on veut. On ainsi dire que Paul est un garçon aussi.

garçon(X) :- X = 'Paul'

On peut alors interroger Prolog en lui demandant qui sont les garçons ? i.e on demande à Prolog de rendre vrai le prédicat  garçon(Y) où Y est une variable, alors Prolog répondra que pour cela il faut que Y prenne la valeur de ‘Pierre’ ou ‘Paul’.

Et la programmation dans tous ça ? Si on ajoute un prédicat qui dit que Pierre et Annie sont nos amis. Cela se fait par les instructions suivantes:

ami('Pierre').
ami('Annie')

On peut demander à Prolog les amis qui sont des garçons.
ami(X),garçon(X)

Prolog répond que X doit prendre la valeur de Pierre. On a l’intuition que cette manière de programmer en est bien une, on arrive à résoudre des problèmes via uniquement leur description qui devient alors le seul objectif du programmeur. La résolution c’est le travail de Prolog. Pour terminer de se convaincre on va illustrer par la résolution du sudoku 9×9.

Sudoku 9×9

Nous allons définir les valeurs possibles sur notre grille de sudoku. Il s’agit des nombre de 1 à 9. Les règles suivantes permettent de le faire en utilisant le langage de base et les listes.

takeout(A,[A|B],B).
takeout(A,[B|C],[B|D]):- takeout(A,C,D).
valeur(X):-takeout(X,[1,2,3,4,5,6,7,8,9],_).

Ainsi si on interroge Prolog en lui demandant de rendre vrai le prédicat valeur(X) alors on obtient les réponses

X=1;
X=2;
...
X=9

Ces valeurs doivent être placées dans les carrés 3×3. Nous définissons ainsi un tel carré par

carre([[A,B,C],[D,E,F],[G,H,I]]):-
valeur(A),valeur(B),valeur(C),
valeur(D),valeur(E),valeur(F),
valeur(G),valeur(H),valeur(I)

où la liste en argument contient les valeurs lignes par lignes.

A ce stade une interrogation du prédicat carré(X) nous renvoie toutes les valeurs sans respecter les règles du sudoku. Par exemple X prend la valeur d’une matrice remplie de 1. Pour continuer il faut décrire les règles d’unicité du sudoku.

L’unicité des nombres dans les carrés 3×3 se fait avec les prédicat suivants:

different(_,[]).
different(A,[B|C]):-
A = B,
different(A,C).


tous_differents([]).
tous_differents([A|R]):-
different(A,R),
tous_differents(R).

Un carré 3×3 doit être remplis des valeurs de 1 à 9 mais toutes les valeurs doivent être distinctes. Donc le prédicat carré(X) devient:

carre([[A,B,C],[D,E,F],[G,H,I]]):-
valeur(A),valeur(B),valeur(C),
valeur(D),valeur(E),valeur(F),
valeur(G),valeur(H),valeur(I),
tous_differents([A,B,C,D,E,F,G,H,I]).

On remarque que la première solution met quelques instants avant d’être affichée. Pourquoi ? On touche ici à l’implémentation de la programmation logique sur nos processeur qui sont des machine de turing. En logique classique il n’y a pas de notion de séquence d’execution mais dans l’implémentation de Prolog il y a un ordre d’execution. Dans notre code la valorisation des cases se fait avant l’exécution du prédicat tous_differents/1 donc le programme énumère les carré jusqu’à ce qu’il en trouve un qui vérifie le prédicat tous_différents/1 ! Cela peut être long….

Discriminer au plus tôt

En règle générale il faut aider Prolog à discriminer les solutions potentielles le plus tôt possible. Dans notre cas il faut poser les prédicats qui imposent les règles d’unicité en premier. Notre prédicat devient


carre([[A,B,C],[D,E,F],[G,H,I]]):-
tous_differents([A,B,C,D,E,F,G,H,I]),
valeur(A),valeur(B),valeur(C),
valeur(D),valeur(E),valeur(F),
valeur(G),valeur(H),valeur(I).

Ce code est juste en théorie. Il fonctionne quand on passe des valeurs a carré/1 et qu’on demande de vérifier si le prédicat est vrai. Mais on veut aussi que cela marche en recherche de solution i.e. en passant une variable en argument de carré/1. Là ça coince, le prédicat est toujours faux !

La faute en incombe au test de différence dans

different(A,[B|C]):-
A = B,
different(A,C).

Comme les variables ne sont pas valorisées, le test est faux. On aimerait bien que Prolog pose simplement la contrainte de différence et que, plus tard lors de l’exécution des prédicats de valorisation, les chemins sans solutions soient évités. Pour cela on va utiliser la programmation logique par contrainte.

Programmation logique par contrainte

Le compilateur gprolog est livré en standard avec le module de contrainte sur les domaines finis. Le compilateur multithreadé SWI-Prolog nécessite quant à lui le chargement manuel du module de contrainte sur les domaines finis en faisant:

use_module(library(clpfd)).

On utilise ensuite le prédicat infixé spécial au domaine fini pour spécifier la différence.Ainsi:

different(A,[B|C]):-
A #= B,
different(A,C).

Dès lors prédicat carre/1 est quasi instantané et donne les solutions des carré 3×3.

La solution finale de cet exercice est alors une question réglée:

takeout(A,[A|B],B).
takeout(A,[B|C],[B|D]):- takeout(A,C,D).
valeur(X):-takeout(X,[1,2,3,4,5,6,7,8,9],_).

different(_,[]).
different(A,[B|C]):-
    A #= B,
    different(A,C).

tous_differents([]).
tous_differents([A|R]):-
    different(A,R),
    tous_differents(R).

carre([[A,B,C],[D,E,F],[G,H,I]]):-
    tous_differents([A,B,C,D,E,F,G,H,I]),
    valeur(A),valeur(B),valeur(C),
    valeur(D),valeur(E),valeur(F),
    valeur(G),valeur(H),valeur(I).
concat_trois([A1,B1,C1],[A2,B2,C2],[A3,B3,C3],X):-
    X = [A1,B1,C1,A2,B2,C2,A3,B3,C3].

lignes_differentes([[A1,A2,A3],[B1,B2,B3],[C1,C2,C3]]):-
    concat_trois(A1,B1,C1,L1),
    tous_differents(L1),
    concat_trois(A2,B2,C2,L2),
    tous_differents(L2),
    concat_trois(A3,B3,C3,L3),
    tous_differents(L3).

colonnes_differentes([A,D,G]):-
    A = [[A1,A2,A3],[A4,A5,A6],[A7,A8,A9]],
    D = [[D1,D2,D3],[D4,D5,D6],[D7,D8,D9]],
    G = [[G1,G2,G3],[G4,G5,G6],[G7,G8,G9]],
    tous_differents([A1,A4,A7,D1,D4,D7,G1,G4,G7]),
    tous_differents([A2,A5,A8,D2,D5,D8,G2,G5,G8]),
    tous_differents([A3,A6,A9,D3,D6,D9,G3,G6,G9]).

sudoku([[A,B,C],[D,E,F],[G,H,I]]):-

    lignes_differentes([A,B,C]),
    lignes_differentes([D,E,F]),
    lignes_differentes([G,H,I]),

    colonnes_differentes([A,D,G]),
    colonnes_differentes([B,E,H]),
    colonnes_differentes([C,F,I]),

    carre(A),carre(B),carre(C),
    carre(D),carre(E),carre(F),
    carre(G),carre(H),carre(I).

Streaming vidéo en mobilité sur N900

Image representing Bambuser as depicted in Cru...
Image via CrunchBase

A la création de Youtube, certain se demandait pourquoi on irait poster ses propres vidéo sur internet, sans contrôle de qui peut voir, sans contrôle de qui télécharge… L’usage à montré que le besoin de diffuser de l’information d’abord textuelle, puis visuelle en image et ensuite en vidéo a trouvé son public.

Mais tous ces usages ont en commun le fait d’être des description à postériori. Il s’agit de récits, de reportage ou de média d’événements passé. Le direct n’est encore à son balbutiement. Ainsi le seul direct qui existe n’est encore au stade du texte avec les services de microblogging comme Status.net (dont l’équivalent plus célèbre mais privateur de liberté est twitter).

Cependant la prochaine étape montre le bout de son nez avec un service de microblog vidéo en streaming. Il s’agit pour tout un chacun de diffuser en direct des vidéos comme il le ferait avec des messages courts. Quel intérêt ? L’actualité, la diffusion d’événement associatifs etc. L’existence des moyens trouvent les usages et non l’inverse.

Le service Bambuser est un exemple de streaming vidéo en mobilité. D’ailleurs pour explorer ce nouvel usage je vous propose de voir en direct le Festival de Cerf-volant en Salle de Grande Synthes le 19 et 20 janvier 2013. J’utiliserai le client pour N900. Les vidéos sont diffusées en temps réel si une connexion est disponible (3G, Wifi) sinon les vidéos sont stockées puis envoyées sur les serveurs de Bambuser. Les spectateurs ont accès au direct mais peuvent également revoir  les vidéos en différées car les vidéos restent accessibles après leur diffusion.

Plus d’historique des messages dans Conversations sur N900

Voici les symptômes:

  • Quand on ouvre l’application Conversations, il n’y a plus aucun message
  • Quand on envoie un SMS, ce dernier reste dans l’état envoi en cours mais en fait il est bien envoyé et le destinataire l’a déjà reçu
  • quand on quitte l’historique d’une conversation puis qu’on y revient, les messages qui étaient en cours d’envoi ont disparu
  • Reception de SMS déjà reçu

Après quelques jours de recherche, j’ai fini par trouver le site www.parorrey.com
Ce dernier indique les manipulations à faire pour réparer la base sqlite des messages reçus mais dans mon cas la solution consistait à repartir d’une base vide.

sudo gainroot
rm -rf /home/user/.rtcom-eventlogger/el-v1.db
killall rtcom-messaging-ui

Un bien mauvais écouteur

Ce billet ne traite ni d’informatique, ni d’internet et même pas de nouvelles technologie. Peut-être faudrait-il que j’ouvre une section shopping sur mon blog et l’inaugurer avec ce billet au sujet de mon dernier achat d’écouteur.

Après avoir usé l’écouteur bluetooth Nokia qui a rendu l’âme au niveau des écouteurs non remplaçables qui ne donnait plus de la voix qu’un d’un seul côté après 3 ans de bon et loyaux services, j’ai utilisé un écouteur bluetooth dont le casque est remplaçable. Bien m’en a pris car au bout d’a peine 2 ans, le casque est devenu aphone d’une côté.

Cette fois-ci je m’étais mis en tête d’opter pour un casque temporaire, le moins cher possible en intra-auriculaire. De passage chez Culture le week-end dernier, je suis tombé sur le modèle suivant de TnB, baptisé ComXtrip:

20130107_001

vendu au prix de 6€90, c’était le moins cher du magasin en intra.

20130107_003

L’écouteur est de piètre qualité. Des bavures sont visibles sur les jointures des pièces de la coque.

20130107_004

L’aspect intra-auriculaire est quelque peu usurpé. L’embout est ouvert et laisse apparaître la membrane interne.

20130107_006

Des imperfections de fabrication au niveau des plastiques sont également visibles.

20130107_005

En ce qui concerne la partie acoustique…. la prestation est égale au prix c’est-à-dire très faible. Le son est creux et sonne bon le plastique. Un vrai supplice pour les oreilles ! Ces écouteurs ne doivent être utilisés que pour le dépannage.