Ubuntu-fr

Nuliel

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 Nuliel (Le 07/02/2019, à 23:16)

---

[ poster un retour de commande ] [ poster une photo ]

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()

Nuliel

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 Nuliel (Le 08/02/2019, à 10:17)

---

[ poster un retour de commande ] [ poster une photo ]

pingouinux

Re : avis programme python

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

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

Nuliel

Re : avis programme python

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

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 Nuliel (Le 08/02/2019, à 10:54)

---

[ poster un retour de commande ] [ poster une photo ]