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