nQueen problem

Page 1 of 1

2 Replies - 390 Views - Last Post: 04 February 2013 - 03:20 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=310805&amp;s=1dc1cf2cbe01b57c20eeca5ad317ec50&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 sistyN

Reputation: 1
• 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

• Pythoneer

Reputation: 786
• Posts: 2,095
• 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.

#3 sistyN

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

Re: nQueen problem

Posted 04 February 2013 - 03:20 PM

atraub, 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)