In un precedente articolo (qui) ho presentato un algoritmo per la ricerca di tutte le soluzioni del problema scacchistico delle 8 regine: il linguaggio che avevo scelto per l'implementazione era C#. In questo articolo ho voluto implementare lo stesso algoritmo utilizzando Python e in particolare il modulo itertools, già presentato in un altro articolo (qui).
Riepilogando la soluzione presentata nell'articolo precedente, a cui rimando per tutti i dettagli (qui), si tratta di generare tutte le permutazioni semplici di 8 valori (8!, ovvero 40320, possibili schemi); in questo modo si hanno tutte le disposizioni delle 8 regine piazzate idealmente su righe e colonne diverse; l'unico test da eseguire è che le regine si trovino su diagonali diverse.
Per generare i possibili schemi utilizzo il metodo permutations() del modulo itertools e per testare le diagonali ho tradotto la funzione Check_8_regine() che avevo scritto in C#:
import itertools
def check_8_regine(a):
for i in range(0,len(a)):
for j in range(i+1,len(a)):
if(abs(i-j)==abs(a[i]-a[j])):
return False
return True
if __name__ == '__main__':
lst = list(itertools.permutations([1,2,3,4,5,6,7,8]))
for cur in lst:
if check_8_regine(cur):
print("->"+str(cur))
Se si confronta questo codice con la relativa implementazione in C# salta all'occhio il ridotto numero di righe; è vero che la versione C# prevede una routine per il salvataggio su file delle soluzioni ma la differenza è dovuta principalmente all'utilizzo del modulo itertools che esegue la gran parte del lavoro (ovvero generazione delle permutazioni semplici).
Qui sotto, per completezza, l'aggiunta della generazione del file con gli schemi delle soluzioni:
import itertools
def check_8_regine(a):
for i in range(0,len(a)):
for j in range(i+1,len(a)):
if(abs(i-j)==abs(a[i]-a[j])):
return False
return True
def log_soluzione(idx,a):
if(idx==1):
fs = open('regine.txt','w')
else:
fs = open('regine.txt','a')
fs.write("\n")
fs.write("SOLUZIONE #" + str(idx) + "\n")
fs.write("\n")
fs.write(" 1 2 3 4 5 6 7 8 \n")
fs.write(" ---------------------------------\n")
for i in range(0,8):
fs.write(str(i + 1) + " |")
for j in range(0,8):
if (a[j] == (i + 1)):
fs.write(" # |")
else:
fs.write(" |")
fs.write("\n")
fs.write(" ---------------------------------\n")
fs.close()
if __name__ == '__main__':
lst = list(itertools.permutations([1,2,3,4,5,6,7,8]))
cnt=0
for cur in lst:
if check_8_regine(cur):
print("->"+str(cur))
cnt=cnt+1
log_soluzione(cnt,cur)
