Cela fait un certains temps qu'il est terminé, mais je n'en avais encore jamais parlé. Il s'agit donc d'un programme pour résoudre une grille de sudoku. Capable de résoudre n'importe quelle grille, même si celle ci comporte plusieurs solutions dans la limite du temps que vous lui laissez. Pour résoudre une grille complexe à une solution, le système mettra généralement moins de 200ms sur un système classique, et peut monter jusqu'à 3 milliards d'années (estimation personnelle ), pour résoudre une grille totalement vide.

Le code est disponible avec, sous licence MIT. Je n'ai pas essayé de le compiler sous windows, mais ça devrait fonctionner aussi.
Plusieurs options disponibles, l'affichage des solutions, le simple comptage du nombre de solutions etc ...

Je sais que certains algorithmes existent et fonctionneraient mieux que le miens, mais j'ai voulu chercher par moi même la façon de résoudre la grille. Dans un premier temps on cherche les possibilités de chaque case, en les éliminant selon les règles du sudoku classique.
Puis s'il y a plusieurs possibilités, on passe en brute force, et on recommence selon les règles etc ... Ce qui dans le cas d'un sudoku à plusieurs (millions de) solutions peut s'avérer extrêmement long à calculer.

Télécharger le programme de résolution de sudoku

Ce programme fonctionne simplement en lignes de commandes, n'y cherchez pas d'interface, néophytes abstenez-vous.

Après près d'un an et demi d'inactivité, et une TODO list qui n'a jamais diminuée en volume, voici enfin la version finale de Xinb, renommée Xinb 1.1 pour l'occasion.
Au menu des changements :

• des URLs plus explicites, facilitant l'indexation par les moteurs de recherche
• double hashage (client & serveur) des mots de passe, pour plus de sécurité
• un anti-spam beaucoup plus efficace pour les commentaires
• balise link pour la favicon
• flux RSS pour les messages publiques
• côté admin, un export SQL, une interface d'envoie de commentaires plus user friendly
• correction de nombreux bugs, sur l'album photo, sur la partie "Ajax" de l'envoie d'articles
• nouvelle page de hashage de mot de passe (script Javascript)
• tri dans l'album photo

Toute remarque sur une amélioration possible, bug, incohérence est la bienvenue.

Liste des Finalistes

No more comment .

Aujourd'hui c'était ma demi-finale prologin, au Kremlin Bicêtre, à EPITA, au sud de Paris, après un réveil quelque peu difficile, direction la gare, puis les métros, dans lesquels on voit des étudiants encore endormis en train d'essayer de relire leurs cours, mais aussi des sans abris qui récitent un discours qui fait quelque peu mécanique, enfin bref, peu importe, me revoilà une fois de plus à aller à EPITA .

J'entre par la superbe porte technologique, j'attends ... et je vois un garçon d'une 20e d'années, bien habillé, accompagné de ses parents ... qui attend depuis bien plus longtemps que moi. Au bout d'un temps qui m'a paru presque interminable, on nous accompagne en amphi pour prendre le petit déjeuner, pains au chocolats, jus de fruits à volonté, avant d'entammer la première épreuve de la journée, l'algorithmique. On me donne une feuille, un sujet ... bon évidemment j'ai pas prévu de stylo ... mais je m'en fais gentillement prêter un. Le sujet porte sur le scrabble qui se joue à l'âge de la retraite, pour celà un vieux geek veut tricher avec son appareil auditif .
Les 3 premières questions n'ont pas posé de problème à la majorité des candidats, le 4e portait sur les filtres, trouver dans une liste de mots tout les mots correspondants à un motif (composé de lettres, d'étoiles et de points d'interrogation).
Cette question je l'ai réussie, mais pas parfaitement, mon algo étant un peu foireux pour des motifs barbares.
Les questions 5 et 6 étaient juste clairement infaisables . Puis on me convoque pour un entretiens, dans lesquel on me demande en gros ce que j'ai déjà programmé, quels langages j'utilise, et quels algos de tris je connais.

L'heure de la pause a sonné, moment pour moi de m'apercevoir que nous ne sommes que 34, qu'il y a 340 demi finalistes, et - il me semble - plus d'un millier de postulants à la base, pour une centaine de personnes en finale. Il me faut donc terminer dans les 33% de tête pour avoit de grandes chances d'être en finale.
La pause est assez intéressante, on bavarde, on mange ...
Je remarque un garçon que j'avais déjà vu à UTC, je ne suis pas seul .

Puis direction l'épreuve machine, 3 bureaux, possibilité d'avoir un terminal, firefox, emacs ...
Les claviers sont en qwerty, mais je m'étais beaucoup entrainé à coder sur une disposition qwerty, je n'arrive d'ailleurs plus à coder sur un azerty .
Ces outils me sont familier, mais je reconnais que quelqu'un n'ayant jamais vu de Linux de sa vie, n'ayant jamais tapé de commande, a du se sentir un peu perdu, d'autant plus que l'aide des organisateurs était succinte. Premiers algos, afficher 42 sur la sortie standard, puis un petit machin avec quelques boucles (mais surtout de la réflexion), puis deux bons gros exos.
Le premier étant assez classique mais faisant appel à de la récursivité, et produisant des arbres assez gros, avec des branches très longues. Mes tests fonctionnaient en local, mais sur le serveur de validation celà ne fonctionnait pas, car j'avais oublié d'initialiser une variable, et forcément, j'ai passé plus de 40 minututes à chercher mon problème là où valgrind (un logiciel merveilleux) l'aurait trouvé en quelques secondes .

Une fois l'erreur corrigée, mon algorithme accusait de grosses lenteurs (du genre 4^50 appels de fonction :p), que j'ai donc allégé, le tout m'ayant fait perdre 15 points, plus 5 points de perdus sur le 2e exo (erreur à la con, pas lu assez l'énoncé), je me sentais mal parti.
Puis j'obtiens un exo qui au premier abord parait très compliqué, on dispose d'une matrice où un caractère représente de la terre, un autre de l'eau, et on doit trouver la profondeur maximale de l'eau (le milieu d'un lac par exemple), là encore il s'agissait de récursivité, et bien plus complexe.
Première surprise, l'algo ne comportait que 3 bugs mineurs vites repérés, et j'ai eu la totalité des points une fois l'algo validé. Deuxième surprise, je me retrouve de ce fait propulsé 3e du classement. Dernier exo en vu, énoncé beaucoup trop long, une grosse flemme ... et très compliqué. Je ne l'ai donc pas fait, ce qui ne m'a pas ôté ma troisème place, personne n'ayant réussi à le valider. J'ai donc sans doute toutes mes chances pour accéder à la finale, qui se compose de 36 heures de code non stop, où nos programmes s'affrontent dans une ambiance festive, suivi le lendemain matin d'une LAN de Quake.

Avant hier, convocation pour les demi finales Prologin 2007, au menu ptit dej, 3 heures d'algo sur papier, 20 minutes d'entretiens, 4 heures de prog sur PC (avec emacs, le meilleur des éditeurs au monde ... enfin le seul éditeur au monde ).
Je me rend donc au Kremlin Bicêtre, à EPITA le Samedi 17 février 2007, maintenant faut viser la finale .

Voilà, c'est maintenant avec une grande fierté que j'ai terminé le dernier exercice pour le concours nationnal d'informatique : Prologin.
Mon algorithme était trop lent et consommait trop de mémoire, j'ai donc passé 4 heures à modéliser des graphiques (grâce à PHP et la GD2) pour trouver une solution plus mathématique ou du moins plus directe, plus rapide, plus belle, plus forte ... toussa ...
Ça donne un code très petit, la partie intéressante de l'algorithme fait ... 3 lignes, alors que le précédent en faisait bien 20 pour la partie intéressante.
Si c'est quand même pas incroyable de réfléchir pendant si longtemps pour pondre 3 lignes au final ...

Si vous souhaitez passer des bonnes fêtes de fin d'année je vous conseille aussi de participer au concours, ça ne prend que quelques heures de réfélexion, éventuellement un peu d'énervement et de "j'y arriverai jamais", mais quand on finit par y arriver ...
Sur ce bonne nuit et bonnes fêtes.

Un projet est né, mardi en amphi, devant un cours de PS01, Vincent et moi décidâmes de créer un Pong 3D en C, tournant aussi bien sous Linux que sous Windows (et éventuellement d'autres systèmes), utilisant la bibliothèque OpenGL.
Ci dessous les prototypes des fonctions à coder (dans des fichiers séparés) :

• int main(void); Doit appeler toutes les autres fonctions
• void init(??); Initialise la fenêtre, les scores, les positions ...
• void rebond(??); Calcule le rebond (contre un mur ou une raquette)
• void score(??); Fonction appelée en fin de boucle principale, pour mettre à jour le score et éventuellement appeler "end_game"
• void dpl_camera(); Permettre le déplacement de la caméra avec la souris (lookAt = point fixe)
• void end_game(void); Fin du jeu, proposer à l'utilisateur une nouvelle partie ...

Il faut également créer un fichier .h, qui contiendra les prototypes et le(s) typedef(s).
Sources de la dernière avancée téléchargeables à cette adresse : http://prog.bezut.info/Pong3D/.