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

[totalgeekdom]

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] + 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 = 1
# Do Diagonal down to the right
while u!=5 and u!=10 and u!=15 and u<20:
u = u + 6
brd = 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 = 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 = 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 = 3
u = origu
# Do down
while u < 21:
u = u + 5
brd = 3
u = origu
# Do up
while u > 5:
u = u - 5
brd = 3
u = origu
# do Diagonal left up
while u>6 and u!=11 and u!=16 and u!=21:
u = u - 6
brd = 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 = 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

 

[Ben Cartwright]

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/programming/#how-do-you-set-a-global-variable-in-a-function

--Ben

 

[Lonnie Princehouse]

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

 

[Fredrik Lundh]

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/trunk/Demo/scripts/queens.py

</F>

 

[Michael Spencer]

when you're done with your homework (?), you can compare it with
Guido's solution:

http://svn.python.org/view/python/trunk/Demo/scripts/queens.py

</F>

Or, Tim Peters' generator-based one:

http://svn.python.org/view/python/trunk/Lib/test/test_generators.py

Michael

 

[totalgeekdom]

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

 

[Felipe Almeida Lessa]

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/trunk/Demo/scripts/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.

 

[totalgeekdom]

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)

 

[Tim Roberts]

when you're done with your homework (?), you can compare it with
Guido's solution:

http://svn.python.org/view/python/trunk/Demo/scripts/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]

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.

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] )