Home Original page

5 queens

cf29 fcharlypillai at gmail.com
Sat Dec 22 19:54:03 EST 2007 
On Dec 23, 1:49 am, John Machin <sjmac... at lexicon.net> wrote:
> > > How did you find 184 solutions? Wolfram says there are 91 distinct
> > > solutions for 5-queens on an 8x8 board with no two queens attacking
> > > each other.
>
> It's *91* distinct solutions to what appears to be *exactly* your
> problem:
>
> """
> k queens        nxn     N_u(k,n)
> 5       8       91

Sorry I missed that. Anyway I found 192 solutions now, they include
rotations and mirroring so that gives 24 "unique" solutions. May be
there is a total of 91 unique solutions that would give 91x8 = 728
distinct solutions. I don't know yet.

Sorry for any misunderstanding as English is not my native language.
I'll include my script so you may understand my code better than my
English and tell me where I went wrong. Thanks a lot to everyone for
your patience and kind help to a such newbie I am. I am learning a
lot, I started to learn Python 3 days ago.

the code I wrote so far
-----
# Solutions to the 5 queens problem
# Control all the board with five queens
# that do not attack each other

board = []	# squares list
nbRows = 8	# number of rows
nbCols = 8	# number of columns

# create 64 squares definied by their row, column
# and a 0 meaning that they aren't controlled yet
# ie the 1st square board[0] is [0,0,0], the last one board[63] is
[7,7,0]
for r in range(nbRows):
	for c in range(nbCols):
		board.append([r,c,0])

# control done by a queen on square (sq)
def queenCtrl(sq):
	for c in range(len(board)):
		if (board[c][0] == sq[0] or								# same row
			board[c][1] == sq[1] or								# same col
			(board[c][0] + board[c][1]) == (sq[0] + sq[1]) or	# diagonal1
			(board[c][0] - board[c][1]) == (sq[0] - sq[1])):	# diagonal2
			board[c][2] = 1				# the square is controlled

# count the number of controlled squares
def calcCtrl():
	nbCtrl = 0 # number of controlled squares
	for c in range(len(board)):
		if board[c][2] == 1:
			nbCtrl += 1
	return nbCtrl

# reset controlled squares
def resetCtrl():
	for c in range(len(board)):
		board[c][2] = 0

# all the solutions list
allSolutions = []

# add nbQueens (5) new queens on safe squares
def newQueens(nbQueens=5):
	solution = []						# one solution
	for i in range(len(board)):			# 64 squares
		if len(solution) < nbQueens:	# 5 queens
			if board[i][2]==0:			# free square
				solution.append(i)		# a queen position
				queenCtrl(board[i])		# the queen controls squares
	resetCtrl()							# reset the controled squares
	allSolutions.append(solution)		# add this solution to the list

# testing
newQueens()

for s in allSolutions:
	print s

# this gives me the first solution

# please tell me
# how can I ask newQueens() to find the next new solution
# and add it to the allSolutions list until there is no more ?
More information about the Python-list mailing list