2 Replies - 286 Views - Last Post: 04 February 2013 - 03:20 PM Rate Topic: -----

#1 sistyN  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 24-April 09

nQueen problem

Posted 01 February 2013 - 03:21 PM

hi guys , I wrote nQueen but it just work for 5 queens , what is the problem , this really stupid ! even i increase first pop and epoch nothing's changed at all

nqueen cycle :
1- first pop
2- fitnessFunc
3- if collision == 0 finish it else go to step 4
4- crossover
5- sort by fitness
6- truncation selection
7- offspring
8- mutating
9- go to step 2

sry for my bad coding , its my first code in python , it was fun .

import random
board_size = 6 #random.randrange(4,20)
DNA = {}
collision = []
col_key = []
offspringCount = [0]
chroMaking = [0]
epoch = 2000

def board(vec): #printing the board
    '''Translate column positions to an equivalent chess board.

    >>> board([0, 4, 7, 5, 2, 6, 1, 3])
    Q-------
    ----Q---
    -------Q
    -----Q--
    --Q-----
    ------Q-
    -Q------
    ---Q----

    '''
    print
    for col in vec:
        s = [' # '] * len(vec)
        s[col] = ' Q '
        print ''.join(s)
    print

def chromosome(size):
  chromo=()
  for i in range(size):
    gene = (random.randrange(size),)
    chromo = chromo + gene
  return chromo
  
def chromoMaking(size,key):
  for i in range(size):
    DNA[key + i] = chromosome(board_size)

    
    

    
def fitnessFunc(key , size):
  
  for k in key:
            
            count = 0
            
            for i in range( 0 , size ):
                
                for j in range( i+1 , size ):
                    if DNA[k][i] == DNA[k][j]:
                        count += 1
                
                for j in range( i+1 , size ):
                    if DNA[k][i] + i == DNA[k][j] + j:
                        count += 1
                
                for j in range( i+1 , size ):
                    if abs( DNA[k][i]-i ) == abs( DNA[k][j]-j ):
                        count +=1    
            
            if count == 0 :
	      print 'You found The Answer : '
	      print DNA[k]
	      board(DNA[k])
	      return True
            collision.append(count)
            col_key.append(k)
            
            
            





def offspring(parent1 , parent2 , key , size):
    r = random.randrange(1,size)
    child1 = ()
    child1 = parent1[0:r]
    child1 += parent2[r:len(parent2)]
    
    child2 =()
    child2 = parent1[r:len(parent1)]
    child2 += parent1[0:r]
        
    DNA[key] = child1
       
    #print 'ch1 : ' , child1
    DNA[key + 1] = child2
        
    #print 'ch2 : ' , child2
    offspringCount[0] += 2
    
def crossover(size):
  sortFitness(DNA.keys())
  print 'collision : \n',collision
  print 'col_key   : \n',col_key,'\n'
  truncationselection()
  l = DNA.keys()
  l = l[len(l)-1] + 1
  cnt = 1
  if len(collision) > 1:
    for i in range(1,len(col_key)):
      offspring( DNA[col_key[0]] , DNA[col_key[i]] , l , size)
      l += 1
      cnt *= 2
    print '\noffspring of this epoch : ' , cnt
    return True
      
  else :   
    chromoMaking(500,l)
    chroMaking[0] += size
    print '\nNumber of added chromosome : ' , size
    return False
    
   

def sortFitness(key):
        
        for i in range(len(key)):
            for j in range( i , len(key)):
                
                if collision[i] > collision[j] :
                    
                    tmp = collision[i]
                    collision[i] = collision[j]
                    collision[j] = tmp
            
                    tmp = col_key[i]
                    col_key[i] = col_key[j]
                    col_key[j] = tmp

  
  

def truncationselection():
  
  
  bestParent = collision[0] * 2
   
  i = len(collision) -1
  while collision[i] >= bestParent :
    DNA.pop(col_key[i])
    collision.pop()
    col_key.pop()
    i -= 1
  print "top parent's : "  
  print 'collision : ' , collision
  print 'col_key :   ' , col_key 
  
  
                    
def mutation(size):
  for i in DNA.keys() :
    tmp =()
    x = random.randrange(0,size)
    tmp1 = DNA[i][0:x]
    tmp2 = DNA[i][x+1:size]
    z =random.randrange(0,size) 
    tmp = tmp1 + (z,) + tmp2
    DNA[i] = tmp
    
    


def nqueen():
  print 'Board size = ' , board_size , " X " , board_size
  chromoMaking( 10000 , 0 ) #first population
  print "Epoch 0 is first population :\n"
  
  i = 0
  while i <= epoch :
    print 'Epoch ' , i ,' :'
    if fitnessFunc( DNA.keys() , board_size ) :
      print 'YOoHoO'
      return True
           
    
    if crossover(board_size) :
      print "OMG I'm mutating "
      mutation(board_size)
      
    
    
    for w in range(len(col_key)):
      collision.pop()
      col_key.pop()
      
    print '\n--------------------------\n'
          
    i += 1  
    
  else : 
    print 'Maybe next timE'
  print 'summery : '  
  print '	Board = ',board_size,' X ',board_size
  print "	Number's of epoch : " , i
  print "	Offspring's : " , offspringCount[0]
  print "	chromosome  : " , chroMaking[0]
  
  
  
  
 
  
def main():
  print 'nqueen for n = ',board_size
  
  
  if nqueen() :
    print 'GRATZ'  
if __name__ == "__main__" :
	main()




Is This A Good Question/Topic? 0
  • +

Replies To: nQueen problem

#2 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: nQueen problem

Posted 04 February 2013 - 08:37 AM

in what way does it not work for more than 5? does it crash? does it find no solutions? does it only find fake solutions? To anyone unfamiliar with the n-queen problem, here's a wikipedia entry on it.
Was This Post Helpful? 0
  • +
  • -

#3 sistyN  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 24-April 09

Re: nQueen problem

Posted 04 February 2013 - 03:20 PM

View Postatraub, on 04 February 2013 - 08:07 PM, said:

in what way does it not work for more than 5? does it crash? does it find no solutions? does it only find fake solutions? To anyone unfamiliar with the n-queen problem, here's a wikipedia entry on it.


ty man , its just find the answer for 5 queen's (zero collision) , in other modes it just show the best answer(1 collision most of the time)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1