Topic: Rompicapo delle N Regine  (Letto 2759 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Wicker25

  • python erectus
  • ***
  • Post: 129
  • Punti reputazione: 0
    • Mostra profilo
Rompicapo delle N Regine
« il: Luglio 19, 2007, 16:36 »
Questo invece è uno script che utilizza il Backtracking per risolvere il Rompicapo delle 8(o più) Regine ;)

#------------------------------------------------------------------------------
#           Name: Rompicapo delle n regine.py
#         Author:   wicker25 (http://hackerforum.devil.it/  -  wicker25@tiscali.it)
#        Description: Un algoritmo di I.A. che scova le posizioni in cui le n regine non si "guardano"
#------------------------------------------------------------------------------

from sys import exit

#Disegna scacchiera
def draw(n):
    global file
   
    for y in range(0,n):
        for x in range(0,n):
            if scacchiera[y][x]:   
                file.write("#")
            else:
                file.write("O")
        file.write("\n")
    file.write("-"*(n+3)+"\n")

#Funzione di Verifica della Soluzione
def _control(n):
      for x in range(0,n):
          for y in range(0,n):
              if scacchiera[x][y]:
                  for t in range(0,n):
                      if scacchiera[t][y] and t!=x: return 0
                  for t in range(0,n):
                      if scacchiera[x][t] and t!=y: return 0
                  for t in range(-n,n):
                      if (x-t)>=0 and (y-t)>=0 and (x-t)<n and (y-t)<n:
                          if scacchiera[x-t][y-t] and (x-t)!=x and (y-t)!=y: return 0
                  for t in range(-n,n):
                      if (x-t)>=0 and (y-(-t))>=0 and (x-t)<n and (y-(-t))<n:
                          if scacchiera[x-t][y-(-t)] and (x-t)!=x and (y-(-t))!=y: return 0                 
      return 1

#Funzione Backtracking
def backtracking(n,row):
      if row<0:
          if _control(n):
              draw(n)
          return
      if not _control(n):
          return
      for x in range(0,n):
          if scacchiera[x][row]==0:
              scacchiera[x][row]=1
              backtracking(n,row-1)
              scacchiera[x][row]=0
      return

n=input("Valore n:> ")
path=raw_input("Percorso file:> ")
if n<2:
    print "Impostazioni errate."
    exit()

file=open(path,"w")

#Crea la scacchiera n*n
scacchiera=[]
for t in range(0,n):
      scacchiera.append([0]*n)

print "Elabaorazione in corso.."
backtracking(n,n-1)
print "Operazione terminata."

file.close()

Versione evidenziata: http://wicker25.netsons.org/scripts/Rompicapo_delle_n_regine.py.html
« Ultima modifica: Luglio 19, 2007, 16:38 da Wicker25 »

Offline MiPnamic

  • python erectus
  • ***
  • Post: 128
  • Punti reputazione: 0
    • Mostra profilo
    • MiPnamic contaminated area | Comunicare; Conoscere; Crescere; Condividere;
Re: Rompicapo delle N Regine
« Risposta #1 il: Luglio 19, 2007, 17:41 »
ottimo script direi ^^ poco comprensibile ad esser pignoli... si potrebbe buttare un output in html con delle png per meglio comprendere le soluzioni...

^_^ mi lasci sempre a bocca aperta wicker ^^

Offline Wicker25

  • python erectus
  • ***
  • Post: 129
  • Punti reputazione: 0
    • Mostra profilo
Re: Rompicapo delle N Regine
« Risposta #2 il: Luglio 19, 2007, 17:49 »
LoL :D
Si, l'output non è dei migliori, ma mi sono concentrato più sull'algoritmo in sè ;)

Offline MiPnamic

  • python erectus
  • ***
  • Post: 128
  • Punti reputazione: 0
    • Mostra profilo
    • MiPnamic contaminated area | Comunicare; Conoscere; Crescere; Condividere;
Re: Rompicapo delle N Regine
« Risposta #3 il: Luglio 19, 2007, 17:56 »
a tal proposito, dove posso reperire materiale sulla creazione di "algoritmi" ?

so che sembra una domanda stupida poichè un algoritmo non è nient'altro che un ragionamento matematico... ma dico, va bene anche qualche "esempio di algoritmi" (a quintali possibilmente ^_^)

Offline Wicker25

  • python erectus
  • ***
  • Post: 129
  • Punti reputazione: 0
    • Mostra profilo
Re: Rompicapo delle N Regine
« Risposta #4 il: Luglio 19, 2007, 18:16 »
a tal proposito, dove posso reperire materiale sulla creazione di "algoritmi" ?
Purtroppo non ce molto materiale a riguardo, specie in italiano..
http://en.wikipedia.org/wiki/Minimax
http://it.wikipedia.org/wiki/Backtracking
etc..
Servirebbe altra documentazione.. In ogni caso, non andiamo off-topic ;)