Ouaih, un écran bleu !Informatique

 

Ceci est un écranCeci est une souris"... à la limite, la dernière fois que j'ai vu le soleil, c'était sur le site Internet de Météo France ..."

Biographie d'un Geek

 

 

Dossiers :

- Mes ordinateurs

- L'histoire des jeux vidéo

- La technologie du Compact Disc...

 

Et aussi sur cette page, quelques programmes de jeu / résolution développés en Visual Basic :

- Rubik's Cube
- Sudoku
- Kakuro
- Nurikabe
- Netwalk

 


Rubik's Cube


Vade Retro Satanas !Cela faisait un paquet d'années que je n'avais pas repris en main mon vieux Rubik's Cube, aux couleurs délavées par le soleil, qui traînait sur une étagère avec son collègue Rubik's Magic.
Et l'envie m'a repris, un jour comme ça, de m'y replonger, et de profiter de l'occasion pour voir si je n'avais pas trop perdu la main en codant un programme de résolution automatique.

Avec Internet, il est aujourd'hui facile d'apprendre tous les secrets et méthodes existantes pour résoudre ou s'amuser avec ce cube diabolique et ses copains (site Rubik's officiel dev.rubiks.com).
Mais il en était tout autre à l'époque (86 ? 87 ?) où mon père avait succombé à la tentation.
Afin d'éviter les nuits blanches et les démontages sauvages, il avait acheté un ouvrage que j'ai récupéré par la suite, présentant pas à pas une méthode simple pour résoudre l'objet récalcitrant :

"Yves Mérane, le Rubik's cube, une méthode simple pour réussir", aux éditions SOLARAMA.

 

Cliquez pour voir l'image en taille réelleC'est la méthode présentée dans ce petit manuel bien pratique (merci à l'auteur) que j'ai choisi d'adapter dans un petit programme pour Windows en Visual Basic 5, que j'ai simplement baptisé Rubiksor (le shérif de l'espace 3D... hum... désolé...).

L'aspect visuel du résultat n'est pas transcendant, je le reconnais, mais ce n'était pas mon but premier et là encore Internet regorge d'Applets Java 3D qui raviront les plus exigeants en la matière.

Basiquement, quelques clics sur le 'cube à plat' permettent de définir l'état initial, et le bouton 'Resolve' donne quelques secondes plus tard une série de rotations permettant de revenir à l'état 'achevé'. Le désespéré en phase terminal retrouve ainsi un semblant de sérénité.

Le programme possède un minimum de robustesse pour détecter les configurations incohérentes ou 'trafiquées'. Je vous fais confiance pour trouver les failles de programmation :) . Vous pardonnerez aussi l'anglais un peu sommaire que j'ai utilisé...

Cliquez ici pour télécharger l'exécutable rubiksor.exe (120 Ko).

Son utilisation nécessite la librairie msvbvm50.dll (700 Ko) disponible sur le site www.dll-files.com

Epilogue :

J'ai poussé un peu plus loin l'autoflagellation en m'achetant dans la foulée un de ses frères aînés, le Rubik's Revenge (4x4x4), légèrement plus subtil. La programmation de celui-là attendra !...

Le savez-vous ?

Il y a 43 252 003 274 489 856 000 combinaisons possibles du cube 3x3x3.

En 1982, le record du monde pour reconstruire le cube était de ... 22,95s .

La théorie mathématique dit qu'il suffit d'entre 24 et 29 mouvements pour reconstruire le cube à partir de n'importe quelle position. L'algorithme donnant ces mouvements s'appelle algorithme de Dieu, mais n'est pas connu.

Il existe des programmes informatiques qui résolvent la plupart des configurations en moins de 20 mouvements.

source : http://trucsmaths.free.fr/rubik.htm

 


Sudoku


Rien a voir avec Sangoku...Connaissez-vous le Sudoku ? Si vous êtes un habitué des magazines télé, il y a de fortes chances que oui. Pour les autres, il ne s'agit pas d'un nouvel art martial mais bien d'un petit jeu de réflexion qui se joue avec un crayon, une feuille et le problème initial.

Le but du jeu : compléter une grille de 9 x 9 cases, organisée en blocs de 3 x 3 cases, avec des chiffres de 1 à 9, en respectant la règle suivante : chaque ligne, colonne ou bloc de 3x3 de la grille ne doit contenir qu'une et une seule fois chaque chiffre.

Ca n'a l'air de rien comme ça, mais le jeu peut s'avérer très ardu, comme dans l'exemple ci-contre (essayez pour voir, mais sans mettre de blanco sur l'écran, ok ?).

 

Cliquez pour voir l'image en taille réelleLe petit programme Windows en Visual Basic 5 que je vous propose résoudra ces puzzles pour vous.

Sudoku solver combine 3 algorithmes simples pour compléter une grille que vous aurez l'obligeance de pré-remplir. Si jamais le problème n'est pas résoluble (petits coquins !), le programme remplira autant qu'il peut. Toute case problématique est signalée (qu'est-ce qu'il ne faut pas faire, quand même...)

Pour les curieux, les 3 algos sont ceux que vous utilisez naturellement en jouant, à savoir :
- recherche des cases où une seule valeur est possible
- recherche de la case unique possible où placer une certaine valeur pour une ligne, colonne ou bloc donné
- essai d'une valeur dans une case (dernier recours...)

Encore une fois, pardon pour mon anglais sommaire, blablabla...

Cliquez ici pour télécharger l'exécutable sudoku.exe (40 Ko).

Son utilisation nécessite la librairie msvbvm50.dll (700 Ko) disponible sur le site www.dll-files.com

Epilogue :

L'exécutable est en version 2 car la version 1 , dotée de 2 algos seulement, ne résolvait pas le puzzle ci-dessus. C'est comme ça qu'on progresse : par l'échec et la correction !

Sudoku sur le Net : http://www.sudoku-factory.com

 


Kakuro


CAC euro ?...Cousin du Sudoku, le Kakuro se présente sous la forme d'une grille de mots croisés où les définitions sont des nombres.

Le but du jeu : compléter les cases blanches de la grille avec des chiffres de 1 à 9 afin d'obtenir par addition les valeurs sommes verticales/horizontales inscrites en haut et/ou à gauche. De plus, chaque chiffre ne peut être utilisé qu'une et une seule fois dans une somme donnée.

Ainsi, dans l'exemple ci-contre, la somme horizontale 6 située en bas à gauche ne peut être obtenue que par addition des chiffres 1, 2 et 3. Il reste à savoir dans quel ordre ces chiffres doivent être placés. Pour cela, des recoupements doivent être effectués avec les sommes verticales afin d'éliminer les positions impossibles. Dans notre cas, on voit rapidement que le chiffre 1 ne peut pas être placé le plus à gauche, car dans ce cas il ne serait plus possible d'obtenir la somme verticale 11 avec un seul chiffre supplémentaire : 11-1 = 10. Etc...

Légèrement plus hardu que le sudoku, ce jeu n'en est pas moins très sympathique !

Le petit programme Windows en Visual Basic 5 que je vous propose vous permettra :
- de saisir une grille,
- d'y jouer,
- de la résoudre pour vous,
- de sauvegarder/recharger le tout.

Pour la résolution, Kakuro solver combine un algorithme relativement bourrin de détermination des possibilités de combinaisons avec un testeur de valeurs, lorsque le besoin s'en fait sentir (je me comprends).

Cliquez ici pour télécharger l'exécutable kakuro.exe (70 Ko) et voilà 2 fichiers grilles exemples 8x8.kkr 5x11.kkr (faire bouton droit, enregistrer sous)

Son utilisation nécessite la librairie msvbvm50.dll (700 Ko) disponible sur le site www.dll-files.com

Bon jeu !

Kakuro sur le Net : http://fr.wikipedia.org/wiki/Kakuro


Nurikabe


Voila la solution.Autre cousin du Sudoku, le Nurikabe se présente initialement sous la forme d'une grille aux cases grises égrainée de cases blanches contenant un nombre.

Le but du jeu : changer les cases grises en cases blanches ou noires en respectant les règles suivantes :
- les cases blanches doivent être reliées et organisées en 'îles', chaque île contenant une et une seule case blanche numérotée.
- le nombre de cases blanches dans chaque île doit être égal à la valeur de sa case blanche numérotée
- toutes les cases noires doivent être reliées en un seul ensemble ininterrompu
- un bloc de 2x2 cases doit obligatoirement contenir au moins une case blanche


Nota: 2 cases sont dites 'reliées' si elles sont voisines gauche-droite ou haut-bas.

L'ensemble de ces règles permet d'avoir une solution unique pour une grille donnée, comme sur l'exemple ci-contre (passez la souris sur la grille pour voir la solution). Ceci peut paraitre compliqué mais un peu de logique et d'analyse permettent pas à pas de donner à chaque case sa couleur et d'en déduire la couleur de ses voisines.

Ainsi, dans l'exemple ci-contre :
- on dispose d'une case blanche chiffrée 1 qui forme donc une île complète à elle toute seule. Ses quatres cases voisines gauche-droite-haut-bas sont donc obligatoirement noires, sinon l'île serait reliée à une autre île ou serait trop grande ! Etc...
- moins évident : les trois cases les plus en haut à droite ne peuvent pas être blanches car aucun nombre ne permet de faire une ile suffisamment longue pour les inclure. Par conséquent ces cases sont noires et comme il faut au moins une case blanche par bloc de 2x2, alors la case restante est obligatoirement blanche. La seule île pouvant inclure cette case blanche est celle contenant la case chiffrée 7, en faisant une île tout en longueur avec la case chiffrée en extrémité basse. Etc...

Plus logique que mathématique, ce jeu est une bonne alternative au Sudoku et au Kakuro.

Le petit programme Windows en Visual Basic 5 que je vous propose vous permettra :
- de saisir une grille,
- d'y jouer,
- de la résoudre pour vous,
- de sauvegarder/recharger le tout.

La résolution n'est pas instantanée car j'ai du me rabattre sur un algorithme itératif à essais/retours, assez intuitif mais loin d'avoir une vue d'ensemble aussi bonne qu'un être humain. Sur la quinzaine de grilles 9x9 utilisées pendant la mise au point sur un PC Athlon 64 3000+, la plus longue a nécessité 4 secondes pour être résoluée (VB carbure pas trop mal quand même). Pour faire patienter pendant la résolution, les solutions en cours d'essai sont fugitivement affichées à l'écran ;) . Une chose est sûre, si une solution existe, l'algo la trouvera. Dans le cas contraire, il vous le dira aussi...

Cliquez ici pour télécharger l'exécutable nurikabe.exe (63 Ko) et voilà 2 fichiers grilles exemples 5x5.nkb 9x9.nkb (faire bouton droit, enregistrer sous)

Son utilisation nécessite la librairie msvbvm50.dll (700 Ko) disponible sur le site www.dll-files.com

Grilles de Nurikabe 9x9 et 5x5 sur le Net : http://www.logicgamesonline.com/nurikabe/daily.php


Netwalk


Voila la solution.Et on continue ! Netwalk se présente initialement sous la forme d'une grille remplie tout ou partiellement d'éléments d'un réseau informatique : serveur, ordinateurs, et cables.

Le but du jeu : obtenir un réseau informatique pleinement valide, c'est à dire :
- relier tous les ordinateurs au serveur grâce aux cables
-
utiliser tous les bouts de cables et ne laisser aucune extrémité ' nue ' (sans ordinateur ni serveur)
- les bords de grilles rebouclent : gauche<-> droite et haut<->bas

Pour cela, l'utilisateur doit appliquer des rotations de 90 degrés aux cases, autant de fois que nécessaire.

Ces règles permettent d'obtenir une solution unique sur l'exemple ci-contre (passez la souris sur la grille pour voir la solution). Là encore, un peu de logique et d'analyse permettent pas à pas de donner à chaque case sa bonne rotation et de reconstituer le réseau.

Ainsi, dans l'exemple ci-contre, on devine rapidement que le cable rectiligne situé dans la colonne la plus à droite, au milieu, ne peut rester vertical puisque dans ce cas il devrait être relié aux 2 ordinateurs situés au-dessus et au-dessous de lui : aucun d'eux ne serait dès lors relié au serveur ! Ce cable rectiligne doit donc être obligatoirement horizontal dans la solution. Etc...

Ce nouveau programme Windows en Visual Basic 5 permet :
- de saisir une grille ou d'en générer une (avec les 2 boutons de la souris),
- de la mélanger
- d'y jouer (le bouton gauche de la souris permet de tourner les cases, le bouton droit de 'marquer & figer' une case considérée ok pour éviter de la tourner par mégarde),
- de la résoudre (probabilité 99% ... ; nota: les cases préalablement 'marquées & figées' par l'utilisateur sont considérées ok ! )
- de sauvegarder/recharger les grilles.

Le solveur intégré combine un algorithme principal qui élimine petit à petit les positions invalides (par analyse rebouclée des 'croix' de cases voisines) et plusieurs petits mécanismes pour 'lancer' cet algorithme. C'est en effet le démarrage qui est le plus compliqué...

Cliquez ici pour télécharger l'exécutable netwalk.exe (64 Ko) et voilà 2 fichiers grilles exemples 9x9medium.nwk 9x9expert.nwk (faire bouton droit, enregistrer sous)

Son utilisation nécessite la librairie msvbvm50.dll (700 Ko) disponible sur le site www.dll-files.com

Grilles de Netwalk 9x9 sur le Net : http://www.logicgamesonline.com/netwalk/daily.php

 

 

Copyright 2007 @ Calimero Inc.