2. Trouver toutes les solutions par programmation
Nous avons vu en travaillant manuellement qu'il faut parfois tenter des pistes puis revenir en arrière si on rencontre des culs-de-sacs. Rien ne nous dit que nous ayons explorer toutes les chemins possibles. Nous allons donc essayer de le faire maintenant.
Commençons par simplifier le graphique initial en soudant les blocs de nombres dont on est sûr qu'ils sont en séquence.
Mais attention ! Il va nous falloir être plus rigoureux que lors de notre recherche manuelle, car nous avons fait des hypothèses fausses pour gagner du temps. Alors, comme cette fois-ci nous voulons trouver toutes les solutions, il faut se pencher sur la simplification. L'outil puissant de la coloration des liens en verts lorsqu'ils sont connecté à un noeud qui n'en possède que 2 est à remettre en question. En effet, 2 n'est pas le nombre minimal de liens pour un noeud. Si c'est un noeud placé à une extrémité, on peut n'en avoir qu'un ! C'est le cas du 18, par exemple. Et il en existe donc un autre
Pour le moment, seul le lien entre 18 et 7 est certain. On ne sait pas encore quel autre noeud peut être une extrémité de la chaîne recherchée, mais on peut utiliser les contraintes pour trouver tous les noeuds qui ne peuvent pas en être.
En effet, pour être une extrémité, un noeud doit être :
- soit à une distance de 4 du 20,
- soit à une distance de 5 du 13.
Nous allons donc écrire un algorithme qui teste tous les chemins de longeur 4 partant de 20 et tous les chemins de longeur 5 partant de 13. Les noeud à l'extrémités de ces chemins, sont potentiellement des noeuds à l'extrémité de la chaîne recherchée. On pourra exclure tous les autres et appliquer sur eux seulement la méthode du lien vert.
Voici tout d'abord l'algorithme qui construit le graphe :
# -*- coding: utf-8 -*-
def graph():
"""
Retourne un graphe sous forme de tableau de 26 éléments dont le
premier est inutile. Chaque élément est une liste des nombres vers
lesquels on peut aller.
Par exemple, le 7 est relié au 2, 9 et 18. Donc on aura
g[7] = [2, 9, 18]
"""
g = [[]]
# Liste des seuls carrés possibles par addition de deux nombres
# entiers compris entre 1 et 25.
C = [4, 9, 16, 25, 36, 49]
for i in range(1, 26):
x = []
for n in range(1, 26):
if n != i and (n + i) in C:
x.append(n)
g.append(x)
return g
Et ensuite l'algorithme de recherche des extrémités de chemins.
# -*- coding: utf-8 -*-
def find_end_node(graph, start, length, nodes):
"""
Trouve tous les noeuds qui se trouvent à une distance "length" de
"start".
Arguments :
- graph : le graphe des noeuds.
- start : le noeud de départ (un entier compris entre 1 et 25).
- length : longeur du chemin à parcourir.
- nodes : ensemble des noeuds trouvés.
"""
fringe = [[start]]
while len(fringe) > 0:
path = fringe.pop()
if len(path) == length:
nodes.add(path[-1])
else:
successors = graph[path[-1]]
for successor in successors:
if successor not in path:
newpath = path[:]
newpath.append(successor)
fringe.append(newpath)
return nodes
En utilisant ces algorithmes, on trouve que tous les noeuds peuvent être des extrémités ! Ceci ne nous aide pas beaucoup.
On peut alors détailler, pour chaque type de chemin, les extrémités possibles :
- 20 (4) : 2, 13, 15, 18, 22, 24
- 20 (5) : 1, 3, 7, 10, 12, 14, 23, 25
- 13 (4) : 2, 3, 8, 9, 10, 11, 12, 15, 17, 18, 20, 21, 22, 25
- 13 (5) : 1, 3, 4, 5, 6, 7, 8, 10, 11, 14, 16, 17, 19, 21, 22, 23, 25
Bingo ! On a là un point très intéressant : le 18 est forcément du côté du 20 puisque s'il était plus proche du 13, cela violerait la condition disant que 13 doit être à une distance de 5 de son extrémité. Cela nous donne une information sur le sens de notre chaîne et on peut relancer l'algorithme de recherche uniquement sur les noeuds qui sont à une distance de 5 du 13. En effet, l'autre extrémité est forcément 18.
On en déduit que les noeuds 2, 9, 12, 13, 15 et 24 ne peuvent pas être des extrémités et donc que leur nombre minimal de connexion est égal à 2.
Sur le graph ci-dessous, on représente par des carrés ce genre de noeud.
Nous avons fait comme si les noeuds 7 et 16 ne pouvaient pas être des extrémités. Une petite justification s'impose concernant le groupe [18,7,9,16,20,5].
Cela est possible, car si ces noeuds avaient été des extrémités, ils se seraient trouvés à une distance trop proche de l'autre extrémité qui est 18. En effet, même si cette contrainte n'est pas explicite, il faut avancer de 24 noeuds pour aller d'une extrémité à l'autre.
Ceci nous amène à une nouvelle idée. Pour qu'un noeud soit une extrémité, il doit être à :
Les seules extrémités possibles sont donc : 3, 4, 8, 10, 11, 22 et 23.
A partir de là, on peut faire tourner notre alrogithme et trouver les 3 solutions suivantes :
- 18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 22, 3.
- 18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 3, 22, 14, 2, 23.
- 18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 8, 17, 19, 6, 3, 22, 14, 2, 23, 13, 12, 4, 21, 15, 10.
# -*- coding: utf-8 -*-
class Node:
def __init__(self, name):
self.name = name
self.links = []
self.surelinks = []
def add_link(n1, n2, sure=False):
if sure:
if n2 not in n1.surelinks:
n1.surelinks.append(n2)
if n1 not in n2.surelinks:
n2.surelinks.append(n1)
if n2 not in n1.links:
n1.links.append(n2)
if n1 not in n2.links:
n2.links.append(n1)
def search():
fringe = [[n[18]]]
while len(fringe) > 0:
currentList = fringe.pop()
if len(currentList) == 25 and currentList[19].name == '13':
print(", ".join([x.name for x in currentList]))
else:
for successor in currentList[-1].links:
if successor not in currentList:
nextList = currentList[:]
nextList.append(successor)
fringe.append(nextList)
n = [None]
for i in range(1, 26):
n.append(Node("{0:2}".format(i)))
add_link(n[1], n[3])
add_link(n[1], n[8])
add_link(n[1], n[15])
add_link(n[1], n[24])
add_link(n[2], n[14], True)
add_link(n[2], n[23], True)
add_link(n[3], n[6])
add_link(n[3], n[13])
add_link(n[3], n[22])
add_link(n[4], n[5])
add_link(n[4], n[12])
add_link(n[4], n[21], True)
add_link(n[5], n[11])
add_link(n[5], n[20], True)
add_link(n[6], n[10])
add_link(n[6], n[19], True)
add_link(n[7], n[9], True)
add_link(n[7], n[18], True)
add_link(n[8], n[17], True)
add_link(n[9], n[16], True)
add_link(n[10], n[15])
add_link(n[11], n[14])
add_link(n[11], n[25], True)
add_link(n[12], n[13])
add_link(n[12], n[24])
add_link(n[13], n[23])
add_link(n[14], n[22])
add_link(n[15], n[21], True)
add_link(n[16], n[20], True)
add_link(n[17], n[19], True)
add_link(n[24], n[25], True)
search()