Contenu | Rechercher | Menus

Annonce

La nouvelle clé USB Ubuntu-fr est en prévente
Rendez-vous sur la boutique En Vente Libre

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#1 Le 08/02/2019, à 00:15

Naziel

avis programme python

Bonsoir,

J'aimerais votre avis sur le programme suivant afin de pouvoir l'améliorer.
Le but est de trouver les tableaux 4x4 qui contiennent tous les nombres de 1 à 16 (forcément sans répétition) et tel que la somme de deux nombres côte à côte en horizontal ou vertical (comprendre pas diagonal) soit un nombre premier.

def testCarreMagique(table):
    l=[]
    listePremiers=[2,3,5,7,11,13,17,19,23,29,31]
    for i in range(0,3):
        for j in range(0,3):
            if (table[i][j]+table[i+1][j] not in listePremiers and table[i][j]!=0 and table[i+1][j]!=0) or (table[i][j]+table[i][j+1] not in listePremiers and table[i][j]!=0 and table[i][j+1]!=0):
                return(False)

    for i in range(0,3):
        if table[3][i]+table[3][i+1] not in listePremiers and table[3][i]!=0 and table[3][i+1]!=0:
            return(False)

    for i in range(0,3):
        if table[i][3]+table[i+1][3] not in listePremiers and table[i][3]!=0 and table[i+1][3]!=0:
            return(False)

    return(True)

def fctRecursive(i,j,table,liste):
    if liste==[] and testCarreMagique(table):
        print(table)
        return
    for k in liste:
        table[i][j]=k
        if testCarreMagique(table):
            nvliste=liste[:]
            nvliste.remove(k)
            fctRecursive((i+4*j+1)%4, (i+4*j+1)//4, table,nvliste)
    table[i][j]=0


def carreMagique():
    table = [ [ 0 for i in range(1,5) ] for j in range(1,5) ]
    liste=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
    fctRecursive(0,0,table, liste)


carreMagique()

C'est bien ce qu'on appelle un retour sur trace que j'ai mis en place?
Des idées pour améliorer/simplifier l'algorithme?

Dernière modification par Naziel (Le 08/02/2019, à 00:16)


[ poster correctement un retour de commande ] [ poster correctement une photo ]
Nouvel adhérent FDN
thinkpad x220, Thinkstation E32 modifié: i5-4570, GTX 1060 6 Gb, 16 Gb de RAM, ...
Pour reprendre le contrôle des semences: https://kokopelli-semences.fr/fr/

Hors ligne

#2 Le 08/02/2019, à 10:46

pingouinux

Re : avis programme python

Bonjour Naziel,
Je te propose ceci, qui ne simplifie pas beaucoup l'écriture.
Tu peux donner la taille de la matrice en argument du script, et on s'arrête au premier résultat, car c'est très long à partir de N=5.

import sys
try: N=int(sys.argv[1]) # Tableau N×N
except IndexError: N=4

# Méthode rudimentaire pour faire la liste
listePremiers=list(range(2,2*N*N))
k=2
while k*k<2*N*N:
   n=2
   while n*k<2*N*N:
      if n*k in listePremiers: listePremiers.remove(n*k)
      n+=1
   k+=1

def testCarreMagique(table):
    for i in range(N):
        for j in range(N):
            if table[i][j]!=0 and \
             (
               ( i!=N-1 and table[i][j]+table[i+1][j] not in listePremiers and table[i+1][j]!=0
               ) or \
               ( j!=N-1 and table[i][j]+table[i][j+1] not in listePremiers and table[i][j+1]!=0
               )
             ): return(False)
    return(True)

def fctRecursive(i,j,table,liste):
    if liste==[] and testCarreMagique(table):
        print(table)
        exit() # Arrêt au premier carré magique trouvé
        return
    for k in liste:
        table[i][j]=k
        if testCarreMagique(table):
            nvliste=liste[:]
            nvliste.remove(k)
            fctRecursive((i+N*j+1)%N, (i+N*j+1)//N, table,nvliste)
    table[i][j]=0


def carreMagique():
    table = [ [ 0 for i in range(N) ] for j in range(N) ]
    liste=list(range(1,N*N+1))
    fctRecursive(0,0,table, liste)

carreMagique()

Hors ligne

#3 Le 08/02/2019, à 11:11

Naziel

Re : avis programme python

Merci pingouinux! Ca ressort une solution pour N=5 rapidement au final. Par contre N=6 il patine dans la semoule!

Edit: cela dit, y a t'il seulement une solution pour N=6?

Dernière modification par Naziel (Le 08/02/2019, à 11:17)


[ poster correctement un retour de commande ] [ poster correctement une photo ]
Nouvel adhérent FDN
thinkpad x220, Thinkstation E32 modifié: i5-4570, GTX 1060 6 Gb, 16 Gb de RAM, ...
Pour reprendre le contrôle des semences: https://kokopelli-semences.fr/fr/

Hors ligne

#4 Le 08/02/2019, à 11:24

pingouinux

Re : avis programme python

Naziel a écrit :

cela dit, y a t'il seulement une solution pour N=6?

Oui, j'en obtiens une en un peu plus de 4 minutes.

Hors ligne

#5 Le 08/02/2019, à 11:46

Naziel

Re : avis programme python

Ah, j'ai pas attendu assez longtemps.
Allez, je tente N=7 smile

Edit: ça marche aussi
[[1, 10, 19, 12, 35, 38, 33], [2, 9, 22, 49, 48, 41, 20], [3, 8, 21, 40, 31, 42, 47], [4, 15, 46, 43, 36, 11, 32], [7, 16, 37, 30, 17, 26, 27], [6, 13, 24, 29, 44, 45, 34], [5, 18, 23, 14, 39, 28, 25]]

Dernière modification par Naziel (Le 08/02/2019, à 11:54)


[ poster correctement un retour de commande ] [ poster correctement une photo ]
Nouvel adhérent FDN
thinkpad x220, Thinkstation E32 modifié: i5-4570, GTX 1060 6 Gb, 16 Gb de RAM, ...
Pour reprendre le contrôle des semences: https://kokopelli-semences.fr/fr/

Hors ligne