Large algorithm issue -- 5x5 grid, need to fit 5 queens plus some squares
totalgeekdom at gmail.com
totalgeekdom at gmail.com
Thu Mar 16 05:55:09 CET 2006
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
More information about the Python-list
mailing list