Problème 1004
Un damier de trois cases sur une est dessiné avec des traits de contour noirs. Vous désirez surligner en rouge certaines arêtes de manière à permettre de relier, d'une façon et d'une seule, n'importe quel sommet des carrés qui le composent à n'importe quel autre en suivant un tracé rouge.- 1A. De combien de façons différentes peut-on tracer les traits rouges ?
(Note : il y a 15 façons de colorier un damier de deux cases sur une). - 2A. Même question avec un damier de six cases sur une.
- 3A. Même question avec un damier de deux cases sur deux.
L'idée du programme est d'effectuer une énumération exhaustive de toutes les façons de prendre les arêtes, puis de regarder si la configuration obtenue respecte les critères définis, à savoir qu'il existe un unique chemin reliant chaque couple de sommets.
Il y a plusieurs façons de modéliser les sommets et les arêtes, mais étant donné l'aspect statique du graphe et sa topologie de type "mesh 2D", le plus efficace est d'utiliser un tableau à 2 dimensions. Dans ce tableau, certaines cases ont un type arête, et d'autres cases un type sommet.
L'exploration des configurations des arêtes prises s'effectue de manière récursive, en calculant, selon un ordre défini, le coordonnées de la cases contenant l'arête suivante à prendre ou non. Une fois toutes les arêtes prises ou non prises, il faut tester la configuration. Le programme commence par vérifier que tous les sommets sont incidents à une arête prise. Cette étape peut éventuellement être évitée, mais permet de de ne pas effectuer la partie la plus couteuse -- compter les chemins -- sur les configurations où des sommets sont inatteignables.
Enfin, compter les chemins se fait pour tous les couples de sommets (source, destination), de manière récursive, en suivant les arêtes prises dans la configuration pour aller vers les sommets non pris, c'est-à-dire en passant au plus une fois par un sommet. La valeur obtenue par ce comptage n'est pas correcte quand il y a un cycle au milieu du chemin, mais dans ce cas il existera forcément des couples de points pour lesquels il existera plus d'un chemin (cf. figure).
La figure de gauche représente les arêtes prises, en vert, et deux sommets A et B. Lors du comptage du nombre de chemins entre A et B, le programme n'en trouvera qu'un (arêtes en rouge sur la figure de droite) au lieu de 3, car le sommet C ne peut être pris qu'une fois. Néanmoins, dans ce cas (quand il y a un cycle), le programme trouvera deux chemins entre chaque paire de sommets du cycle (par exemple C et D sur la figure). Il y a donc une équivalence entre le fait de compter exactement un chemin entre chaque couple de sommets, et le fait qu'il y ait réellement un unique chemin entre chaque couple de sommets.
Pour avoir le nombre de chemins exacts, il faudrait marquer les arêtes et non les sommets lors du comptage, mais cela augmenterait inutilement le nombre de cas à explorer.
Le code du programme se trouve ici.
Il y a plusieurs façons de modéliser les sommets et les arêtes, mais étant donné l'aspect statique du graphe et sa topologie de type "mesh 2D", le plus efficace est d'utiliser un tableau à 2 dimensions. Dans ce tableau, certaines cases ont un type arête, et d'autres cases un type sommet.
L'exploration des configurations des arêtes prises s'effectue de manière récursive, en calculant, selon un ordre défini, le coordonnées de la cases contenant l'arête suivante à prendre ou non. Une fois toutes les arêtes prises ou non prises, il faut tester la configuration. Le programme commence par vérifier que tous les sommets sont incidents à une arête prise. Cette étape peut éventuellement être évitée, mais permet de de ne pas effectuer la partie la plus couteuse -- compter les chemins -- sur les configurations où des sommets sont inatteignables.
Enfin, compter les chemins se fait pour tous les couples de sommets (source, destination), de manière récursive, en suivant les arêtes prises dans la configuration pour aller vers les sommets non pris, c'est-à-dire en passant au plus une fois par un sommet. La valeur obtenue par ce comptage n'est pas correcte quand il y a un cycle au milieu du chemin, mais dans ce cas il existera forcément des couples de points pour lesquels il existera plus d'un chemin (cf. figure).
La figure de gauche représente les arêtes prises, en vert, et deux sommets A et B. Lors du comptage du nombre de chemins entre A et B, le programme n'en trouvera qu'un (arêtes en rouge sur la figure de droite) au lieu de 3, car le sommet C ne peut être pris qu'une fois. Néanmoins, dans ce cas (quand il y a un cycle), le programme trouvera deux chemins entre chaque paire de sommets du cycle (par exemple C et D sur la figure). Il y a donc une équivalence entre le fait de compter exactement un chemin entre chaque couple de sommets, et le fait qu'il y ait réellement un unique chemin entre chaque couple de sommets.
Pour avoir le nombre de chemins exacts, il faudrait marquer les arêtes et non les sommets lors du comptage, mais cela augmenterait inutilement le nombre de cas à explorer.
Le code du programme se trouve ici.
- 1A : Pour 3 cases sur une, il y a 56 réseaux rouges.
- 1B : Pour 6 cases sur une, il y a 2911 réseaux rouges.
- 1C : Pour un damier 2 × 2, il y a 192 réseaux rouges.