440,199 Members | 1,474 Online
Need help? Post your question and get tips & solutions from a community of 440,199 IT Pros & Developers. It's quick & easy.

# Large algorithm issue -- 5x5 grid, need to fit 5 queens plus some squares

 P: n/a Background: The problem I'm trying to solve is. There is a 5x5 grid. You need to fit 5 queens on the board such that when placed there are three spots left that are not threatened by the queen. My thinking: I created a list, named brd, that represents the board. I made it such that brd[1] would be the first square on the grid, and brd[25] would be the bottom right end of the grid. Like this: | 1 | 2 | 3 | 4 | 5 | | 6 | 7 | 8 | 9 |10| |11|12 |13|14 |15| |16|17 |18|19 |20| |21|22 |23|24 |25| Next, I created 4 functions The first named clearbrd() which takes no variables, and will reset the board to the 'no-queen' position. The second function I made was name permute(seq,n) and will create every combination of the placement of 5 queens. The third function is the printbrd() function, which takes no input, and prints the board. The final, and most important function is the affect(u) function, where u is the position of the queen on the grid, and it makes that value 1, then it finds all the places that the queen threatens, and makes those values 3. For example -- If I was to do, affect(1) printbrd() it would output |1|3|3|3|3| |3|3|0|0|0| |3|0|3|0|0| |3|0|0|3|0| |3|0|0|0|3| The last function of my code is where I create a for loop that takes all the combinations of the queens position, and puts them on the board, counts the numbers of zero, and if it's >= 3, it outputs the location of the queens, and the board. Problem: It doesn't output anything. Even when I change the mininum number of 0's to 1, it doesn't output anything. I tried taking it and statically inputing the vars for it to have two zeros, and made the mininum number 2. and it says that it is a correct answer. Then I took permute() and pasted all the output to a file, and it had the combination I tried. So I don't understand why it's not working. Thanks for all of your help guys, Poz The Code: #!/usr/bin/env python brd = [9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0] def clearbrd(): brd = [9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0] a = "|" def permutate(seq,n): if n == 0: yield[] else: for i in range(len(seq)): for subseq in permutate(seq[:i] + seq[i + 1:], n - 1): yield [seq[i]] + subseq def printbrd(): print a,brd[1],a,brd[2],a,brd[3],a,brd[4],a,brd[5],a,"\n" print a,brd[6],a,brd[7],a,brd[8],a,brd[9],a,brd[10],a,"\n" print a,brd[11],a,brd[12],a,brd[13],a,brd[14],a,brd[15],a,"\n" print a,brd[16],a,brd[17],a,brd[18],a,brd[19],a,brd[20],a,"\n" print a,brd[21],a,brd[22],a,brd[23],a,brd[24],a,brd[25],a,"\n" def affect(u): origu = u brd[u] = 1 # Do Diagonal down to the right while u!=5 and u!=10 and u!=15 and u<20: u = u + 6 brd[u] = 3 u = origu # Do Diagonal down to the left while u!=1 and u!=6 and u!=11 and u!=16 and u!=21 and u<22: u = u + 4 brd[u] = 3 u = origu # Do horizontal to the left while u!=1 and u!=6 and u!=11 and u!=16 and u!=21: u = u - 1 brd[u] = 3 u = origu # Do horizontal to the right while u!=5 and u!=10 and u!=15 and u!=20 and u!=25: u = u + 1 brd[u] = 3 u = origu # Do down while u < 21: u = u + 5 brd[u] = 3 u = origu # Do up while u > 5: u = u - 5 brd[u] = 3 u = origu # do Diagonal left up while u>6 and u!=11 and u!=16 and u!=21: u = u - 6 brd[u] = 3 u = origu # do Diagonal right up while u>5 and u!=10 and u!=15 and u!=20 and u!=25: u = u - 4 brd[u] = 3 answeru = origu clearbrd() for v,w,x,y,z in permutate(range(1,26),5): affect(v) affect(w) affect(x) affect(y) affect(z) if brd.count(0) >= 3: print "-----------------" print "Solved",v,w,x,y,z printbrd() clearbrd() Thanks for all of your help guys! Poz Mar 16 '06 #1
9 Replies

 P: n/a to**********@gmail.com wrote: The first named clearbrd() which takes no variables, and will reset the board to the 'no-queen' position. (snip) The Code: #!/usr/bin/env python brd = [9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0] def clearbrd(): brd = [9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0] clearbrd() isn't doing what you want it to. It should be written as: def clearbrd(): global brd brd = [9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0] Explanation: http://www.python.org/doc/faq/progra...-in-a-function --Ben Mar 16 '06 #2

 P: n/a It looks like a good start! Some tips- - Index your arrays starting from 0 instead of 1. It will make life easier (and it's the convention in most modern languages) - Try a two dimensional array for the board representation? A list of lists will do: brd = [ [0] * 5 for i in xrange(5) ] Now "brd[row][col]" will give the value of the square at that row and column. The printbrd function becomes: def printbrd(): for row in xrange(5): for col in xrange(5): print brd[row][col], print "" # print automatically adds a newline unless you follow with a comma - Or better yet, you don't even need a board representation. You can only have five queens, as opposed to 25 squares, so instead of storing a whole board, just store a list of the positions of queens. - affect is going to wipe out previous queens "1" with a "3", and you could still get a count of three or more zeros. - Try to generalize the problem from 5 queesn on 5x5 to N queens on NxN. Is 7 possible? How about 8? - the permute function is a nice use of generators Mar 16 '06 #3

 P: n/a to**********@gmail.com wrote: The problem I'm trying to solve is. There is a 5x5 grid. You need to fit 5 queens on the board such that when placed there are three spots left that are not threatened by the queen. when you're done with your homework (?), you can compare it with Guido's solution: http://svn.python.org/view/python/tr...ipts/queens.py Mar 16 '06 #4

 P: n/a Fredrik Lundh wrote: to**********@gmail.com wrote: The problem I'm trying to solve is. There is a 5x5 grid. You need to fit 5 queens on the board such that when placed there are three spots left that are not threatened by the queen. when you're done with your homework (?), you can compare it with Guido's solution: http://svn.python.org/view/python/tr...ipts/queens.py Or, Tim Peters' generator-based one: http://svn.python.org/view/python/tr..._generators.py Michael Mar 16 '06 #5

 P: n/a Thank you very much guys! Just for clarification it wasn't homework, just extra credit :) I can't beleive I didn't realize that I didn't clear the GLOBAL variable :D Mar 16 '06 #6

 P: n/a Em Qui, 2006-03-16 Ã*s 09:20 +0100, Fredrik Lundh escreveu: when you're done with your homework (?), you can compare it with Guido's solution: http://svn.python.org/view/python/tr...ipts/queens.py Just a curiosity. Running the script as the site lists on my computer: \$ time python2.4 /tmp/queens.py -n 12 Found 14200 solutions. real 0m14.177s user 0m13.700s sys 0m0.042s Adding a "import psyco; psyco.full()" clause to the beginning of the file: \$ time python2.4 /tmp/queens.py -n 12 Found 14200 solutions. real 0m3.250s user 0m3.003s sys 0m0.012s At least interesting... Felipe. Mar 16 '06 #7

 P: n/a Sorry to bring this up again, but I decided to try to re-create the program, using the 2d array. However, I ran into a slight problem. How will the permutation function have to be modified? I'm having issues trying to figure out how it works, and how it would need to be modified to use it correctly (I used it from a cookbook, and didn't bother figuring it out) Mar 17 '06 #8

 P: n/a "Fredrik Lundh" wrote: to**********@gmail.com wrote: The problem I'm trying to solve is. There is a 5x5 grid. You need to fit 5 queens on the board such that when placed there are three spots left that are not threatened by the queen.when you're done with your homework (?), you can compare it withGuido's solution: http://svn.python.org/view/python/tr...ipts/queens.py That solves a different problem. The traditional N queens problem would be "place 5 queens so that none of them threatens another". That's very different from his problem specification. It turns out there is only 1 unique (non-rotated, non-reflected) solution to the problem as he posted it. -- - Tim Roberts, ti**@probo.com Providenza & Boekelheide, Inc. Mar 17 '06 #9

 P: n/a "to**********@gmail.com" wrote: Background:The problem I'm trying to solve is.There is a 5x5 grid.You need to fit 5 queens on the board such that when placed there arethree spots left that are not threatened by the queen. I know this wasn't a contest, but here's my solution. This finds 8 solutions, which are all reflections and rotations of each other: rows = ( ( 1, 2, 3, 4, 5 ), ( 6, 7, 8, 9, 10 ), ( 11, 12, 13, 14, 15 ), ( 16, 17, 18, 19, 20 ), ( 21, 22, 23, 24, 25 ), ( 1, 6, 11, 16, 21 ), ( 2, 7, 12, 17, 22 ), ( 3, 8, 13, 18, 23 ), ( 4, 9, 14, 19, 24 ), ( 5, 10, 15, 20, 25 ), ( 16, 22 ), ( 11, 17, 23 ), ( 6, 12, 18, 24 ), ( 1, 7, 13, 19, 25 ), ( 2, 8, 14, 20 ), ( 3, 9, 15 ), ( 4, 10 ), ( 2, 6 ), ( 3, 7, 11 ), ( 4, 8, 12, 16 ), ( 5, 9, 13, 17, 21 ), ( 10, 14, 18, 22 ), ( 15, 19, 23 ), ( 20, 24 ) ) zeros = [ 0 ] * 25 def printme( cells ): for i,j in enumerate(cells): print "%2d" % j, if i % 5 == 4: print def check( queens ): cells = zeros[:] for q in queens: for row in rows: if q in row: for x in row: cells[x-1] = 1 nils = len( [1 for k in cells if not k] ) if nils >= 3: for i in queens: cells[i-1] = 9 print queens printme( cells ) for q1 in range(25): for q2 in range(q1+1,25): for q3 in range(q2+1,25): for q4 in range(q3+1,25): for q5 in range(q4+1,25): check( [q1+1,q2+1,q3+1,q4+1,q5+1] ) -- - Tim Roberts, ti**@probo.com Providenza & Boekelheide, Inc. Mar 17 '06 #10

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

Browse more Python Questions on Bytes