Steven

Juste un petite vidéo pour vous présenté le festival du jeux de Cannes, ou j'ai participation aux bon fonctionnement d'une LAN de 60 PC avec ma promo .

Bon c'est un vidéo officiel de l'école.

Si quelqu'un arrive a me traduire cela dans un francais plus vulgaire, faite le moi savoir. XD

Amusez vous bien !

Je ne connaissais pas le Sudoku. Je viens de découvrir (en diagonale) la littérature sur ce sujet. J'ai eu l'idée d'une méthode, qui s'apparente d'ailleurs à de la programmation par contrainte. Je ne l'ai pas testée, donc je ne sais pas si elle est performante. Par contre, il se peut que dans le cas où la grille n'a qu'une solution, on trouve cette solution sans faire aucune recherche (pas d'essais/erreurs).

L'idée est de transfomer le problème en un système linéaire sur un corps fini, qu'on va résoudre par le pivot de Gauss. Le corps fini en question est GF(2^9), qu'on peut voir comme le quotient de l'anneau des polynômes sur Z/2, qu'on notera Z/2[X] par l'idéal (maximal) engendré par un polynôme irréductible. On a de la chance, car le trinôme X^9+X+1 est irréductible modulo 2 (ce n'est pas le cas pour tous les exposants). Evidemment, il faut implémenter le calcul dans ce corps. Un polynôme peut être représenté par un mot de 9 bits. Ce genre de choses est bien conue en cryptographie.

Maintenant, les solutions d'une grille partiellement remplie sont certaines solutions (pas toutes) d'un système linéaire sur ce corps. On va remplir la grille, non pas avec des chiffres, mais avec des éléments de GF(2^9). Evidemment, les seules solutions valables sont celles pour lesquelles les cases contiennent un monôme non nul (un mot de 9 bits avec un seul 1), qui lui représente un chiffre (l'exposant du monôme). C'est cette restriction qui complique le problème (sinon, il ne serait pas NP-complet).

Le système linéaire a au plus 81 inconnues (en fait il y a autant d'inconnues que le nombre de cases vides au départ) et 27 équations linéaires, qui consistent à dire, par exemple pour une colonne que la somme des cases est le polynôme X+X^2+X^3+...+X^9, c'est à dire le mot de 9 bits 111111111. Une fois le système posé, on peut le résoudre par la méthode du pivot. Pour cela il suffit de savoir inverser les éléments non nul du corps GF(2^9). Bien entendu, on établit la table de multiplication et la table des inverses une fois pour toutes. A chaque pivot, on récupère une équation d'élimination, qui donne la valeur d'une inconnue en fonction des suivantes. Si le problème à au moins une solution, on tombe nécessairement après un certain nombre de pivots sur le système 0=0. Il reste alors éventuellement des inconnues pour lesquelles on n'a pas de formule d'élimination. Il faut donner à chaque inconnue restante chacune des 9 valeurs possibles, et tester à l'aide des formules d'élimination si on obtient des monômes. Ceci va éliminer beaucoup de valeurs, et on a certainement une chance de trouver toutes les solution dans un temps (et une occupation mémoire) raisonnable.

Il faut remarquer que les équations d'élimination qui résultent du pivot de Gauss servent précisément à propager les contraintes.

Evidemment, il y a un peu de travail, à commencer par le calcul dans GF(2^9). Mais ça me paraît faisable.

Je le refais encore une fois, pour que vous voyez ceux qui a changé chez moi.
En plus c'est pas pour faire chier, mais tout le monde ce plein que j'ai changé, alors dites moi en quoi s'il vous plait !!

Nom : Masini. (ça ça change pas normal)
Prénom : Steven. (ça aussi)
Date de naissance :21/06/1990. (pareille vous vous en doutez !)
Lieu de naissance : Toulon (J'aime pas cette ville)(ça non plus ! Hein Nicodecon !!).
Age :18 Ans. (ça oui parcontre normal 1 ans après)
Lieu de résidence : Nice (Beh ouai je suis Niçois maintenant)
Frère et sœur : une sœur qui est trop loin, et un frère qui ne l'est pas assez.. (ça ça a pas changé)
Surnom : Lutin des bois (Mais je sais pas d'où ça vient Oo)
Qualité : Elle est chiante cette question, vous vous attendiez à ce que je réponde quoi ?
Défaut : Pareille que la précédente.
Musique : Principalement du Rock, mais sinon j'écoute un peu de tout.
Loisir : L'informatique (Il n'y a plus que ça dans ma vie, on va dire)
As-tu de véritable amis ? J'espère que oui, j'espère que j'en ai encore.
Quel est la personne qui t'es la plus chère ? (ça ce dit pas ça, non mais dis donc !)
Qu'elles sont tes meilleurs ami(e)s ? Pierre et Manon (parce que ça fait 16 ans que l'on se connais et qu'il ne m'ont jamais laisser tomber) et non plus maintenant ! ça fait 17 ans maintenant !^^
Quel est ton acteur préféré ? J'en préfère pas forcément un plus qu'un autre.
Quel est ton groupe de musique préféré ? Muse, non je déconne spécial dédicace à Nicodecon !

Quel est ton chiffre porte-bonheur ? J'en ai pas, parcontre un porte poisse y a le 42 !!
Quel est ton sport préféré ? Le VTT, même si je peux pas en faire.
Quelle est ta boisson préféré ? Le Coca, ça aide à resté éveillé.
Qu'as-tu envie de faire plus tard ? Être le roi du monde !!
La première chose que tu fait en te levant le matin ? Me mettre des claques pour pas me rendormir, et pour me bougé le cul.
La première chose en rentrant chez toi ? La Vaisselle (Si seulement c'était vrai) XD
La matière que tu aime le moins ? Beh maintenant avec cette école de tordu, j'en sais rien.
La matière que tu aime le plus ? Euh ... (Bon beh finalement ça non plus ça n'a pas changé)

PS : Si le miroir est dégueulasse c'est pas ma faute.

Je vous met, pour ceux qui regarder encore mon blog, une vidéo de mes "Vacance" à la montagne.

Si il y a retenir une chose de cette semaine, c'est que le Snowboard n'est vraiment pas fait pour moi.

Et si l'on me voix pas trop sur la vidéo, c'est parce que c'est moi qui tenait la camera.

PS : Je rectifie on me vois me ramasser à la 5.08 min ainsi que les 5 gamelles qui suivent.

Pour vous expliquer un peu la détresse mentale des étudiants de Epitech, je vous montre l'hymne qui nous réchauffe le cœur lors des coups dur.
Je parle bien sur de la chanson du poireau, version Finlandaise, bien évidemment puisque je sais que vous ne voyez absolument pas de quoi je parle, je vais vous laissez, vous emporter au gré de cette mélodie fantastique.